Московский государственный технический университет им.
Калужский филиал
Домашнее задание №1
«Задача линейного программирования»
Вариант 7
Выполнил: студент группы ЭВМ-71
Проверил: ,
Калуга, 2012
Условие варианта
№ | a11 | a12 | a21 | a22 | a31 | a32 | b1 | b2 | b3 | C1 | С2 | Вид опер. | Знак отнош. 1. | Знак отнош. 2 | Знак отнош. 3 | Обл. изм. x1 | Обл. изм. x2 |
7 | 2 | 1 | 2 | 5 | -1 | 1 | 8 | 10 | 3 | 1 | 1 | min |
| = |
|
|
|
По данным таблицы составим задачу линейного программирования (ЗЛП):
1. Решение ЗЛП графически
Т. к. 
, а 
, область допустимых решений (ОДР) будет ограничена I и II квадрантами.
Рис. 1. Решение ЗЛП графически
Из рисунка видно, что ОДР является отрезок АВ. Точка А – оптимальная. Найдем ее координаты:
Определение пределов изменения ресурсов
Дефицитные ресурсы: 
и 
.
Недефицитные ресурсы: 
.
Пределы изменения ресурса 
.
Пределы изменения ресурса 
.
Пределы изменения ресурса 
.
Определение базисных и небазисных переменных (БП и НБП) в каждой вершине.
Приведём заданную модель к стандартной форме. При этом учтем, что переменная 
не ограничена в знаке. Представим в виде: 
, где 
. Такую подстановку следует использовать во всех ограничениях, содержащих эту переменную, а также в выражении для целевой функции.
Введём в ограничения (1) остаточную переменную 
со знаком «+», а в ограничение (3) остаточную переменную 
со знаком «+».
Теперь определим базисные и небазисные переменные в т. А и т. В.
Точки | БП | НБП |
А |
|
|
Б |
|
|
, 
, 
, 
2. Решение ЗЛП симплекс-методом. Прямая задача
Рассмотрим стандартную форму ЗЛП, полученную при графическом решении:
Полученный вид ЗЛП не позволяет сформировать НДБ, т. к. нельзя выделить единичный орт во втором равенстве. Для получения НДБ введём искусственные переменные:
Общее число переменных определяется:
БП | НБП |
|
|
, Получим z-строку для СТ(0): 
Из (2) : 
.
Тогда: 
Сформируем симплекс-таблицу на первом шаге:
СТ(0):
|
| ||||||||
|
|
|
|
|
|
| ПЧ | ||
| 1 | -1 + 2М | 1 - 2М | -1 + 5М | 0 | 0 | 0 | 10М | |
| 0 | 2 | -2 | 1 | 1 | 0 | 0 | 8 | 8/1 = 8 |
| 0 | 2 | -2 | 5 | 0 | 1 | 0 | 10 | 10/5=2 |
| 0 | -1 | 1 | 1 | 0 | 0 | 1 | 3 | 3/1 = 3 |
НДБ
Составим матрицу перехода:
Сформируем симплекс-таблиц на втором шаге:
СТ(1) = В(0)*СТ(0)
СТ(1):
|
| |||||||
|
|
|
|
|
|
| ПЧ | |
| 1 | -3/5 | 3/5 | 0 | 0 | 1/5 - М | 0 | 2 |
| 0 | 8/5 | -8/5 | 0 | 1 | -1/5 | 0 | 6 |
| 0 | 2/5 | -2/5 | 1 | 0 | 1/5 | 0 | 2 |
| 0 | -7/5 | 7/5 | 0 | 0 | -1/5 | 1 | 1 |
НДБ
Составим матрицу перехода:
Сформируем симплекс-таблиц на третьем шаге:
СТ(2) = В(1)*СТ(1)
СТ(2):
| ||||||||
|
|
|
|
|
|
| ПЧ | |
| 1 | 0 | 0 | 0 | 0 | 2/7 - М | -3/7 | 11/7 |
| 0 | 0 | 0 | 0 | 1 | -3/7 | 8/7 | 50/7 |
| 0 | 0 | 0 | 1 | 0 | 1/7 | 2/7 | 16/7 |
| 0 | -1 | 1 | 0 | 0 | -1/7 | 5/7 | 5/7 |
НДБСТ(2) – оптимальная, т. к. коэффициенты при базисных переменных равны 0, а при небазисных переменных меньше 0.
Проверка правильности графического решения
Задачу линейного программирования для любой вершины в компактной форме можно представить в виде: 
.
Составим симплекс-таблицу для оптимальной точки А.
Выделим базисные переменные: 
. Для определения значений базисных переменных необходимо определить 
.
Таким образом:
Отсюда имеем:
Составим z-строку:
Подставим в Z – строку базисные переменные 
и 
, отличные от нуля.
Полученные результаты внесём в таблицу CT(*). Расположение базисных переменных произвольное.
СТ(*)
|
|
|
|
|
|
| ПЧ | |
| 1 | 0 | 0 | 0 | 0 | 2/7 - М | -3/7 | 11/7 |
| 0 | 0 | 0 | 1 | 0 | 1/7 | 2/7 | 16/7 |
| 0 | -1 | 1 | 0 | 0 | -1/7 | 5/7 | 5/7 |
| 0 | 0 | 0 | 0 | 1 | -3/7 | 8/7 | 50/7 |
Полученная оптимальная симплекс-таблица совпадает с ранее полученным решением, следовательно, графическое решение является верным.
3. Решение ЗЛП симплекс-методом. Двойственная задача
Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:
ПЗ | ДЗ |
|
|
На основании полученных ОДР двойственных переменных введём необходимые подстановки:
Полученный вид ДЗЛП не позволяет сформировать НДБ, т. к. нельзя выделить единичный орт в одном из неравенств (после свертки ограничений (1) и (2) в одно со знаком «=»). Для получения НДБ введём искусственные переменные:
Общее число переменных определяется:
БП | НБП |
|
|
, 
, 
, 
Получим w-строку для СТ(0): 
.
Выразим R : 
.
Тогда: 
Составим симплекс-таблицу на первом шаге:
СТ(0):
| НДБ
| ||||||||
|
|
|
|
|
|
| ПЧ | ||
| 1 | 8 + 2М | М | 10 + 2М | 3-М | 0 | 0 | -М | |
| 0 | -2 | 2 | -2 | 1 | 1 | 0 | 1 | 1/2 |
| 0 | -1 | 5 | -5 | -1 | 0 | 1 | 1 | 1/5 |
Составим матрицу перехода:
Составим симплекс-таблицу на втором шаге:
СТ(1) = В(0)*СТ(0)
СТ(1):
|
| |||||||
|
|
|
|
|
|
| ПЧ | |
| 1 | 6 + (8/5)М | 0 | 0 | 1 - (7/5)М | 0 | 2 + (2/5)М | 2 - (3/5)М |
| 0 | -8/5 | 0 | 0 | 7/5 | 1 | -2/5 | 3/5 |
| 0 | -1/5 | 1 | -1 | -1/5 | 0 | 1/5 | 1/5 |
НДБ
Составим матрицу перехода:
Составим симплекс таблицу на третьем шаге:
СТ(2) = В(1)*СТ(1)
СТ(2):
НДБ
| ||||||||
|
|
|
|
|
|
| ПЧ | |
| 1 | 50/7 | 0 | 0 | 0 | -5/7 + М | 16/7 | 11/7 |
| 0 | -8/7 | 0 | 0 | 1 | 5/7 | -2/7 | 3/7 |
| 0 | -3/7 | 1 | -1 | 0 | 1/7 | 1/7 | 2/7 |
СТ(2) – оптимальная, т. к. коэффициенты при базисных переменных равны 0, а при небазисных переменных больше 0.
4. Соотношения двойственности
Оптимальное решение прямой задачи:
|
|
|
|
|
| |||
|
|
|
|
|
|
| ПЧ | |
| 1 | 0 | 0 | 0 | 0 | 2/7 - М | -3/7 | 11/7 |
| 0 | 0 | 0 | 0 | 1 | -3/7 | 8/7 | 50/7 |
| 0 | 0 | 0 | 1 | 0 | 1/7 | 2/7 | 16/7 |
| 0 | -1 | 1 | 0 | 0 | -1/7 | 5/7 | 5/7 |
Целевая функция прямой задачи:
Оптимальное решение двойственной задачи:
|
|
|
|
|
| |||
|
|
|
|
|
|
| ПЧ | |
| 1 | 50/7 | 0 | 0 | 0 | -5/7 + М | 16/7 | 11/7 |
| 0 | -8/7 | 0 | 0 | 1 | 5/7 | -2/7 | 3/7 |
| 0 | -3/7 | 1 | -1 | 0 | 1/7 | 1/7 | 2/7 |
Целевая функция двойственной задачи:
1. Вектора переменных прямой и двойственной задачи
; 
; 
2. Матрицы коэффициентов целевой функции прямой и двойственной задачи
; 
; 
3. Соотношения прямой и двойственной задачи
3.1. 
3.2. 
3.3. 
3.4. 
3.5. 
3.6. 
3.7. 
3.8. 
4. Соотношения двойственности:
4.1. Оптимальные значения двойственных переменных:
Значения коэффициентов 
берутся из z-строки оптимального решения, 
из целевой функции прямой задачи
4.2. Оптимальные значения переменных:
Значения коэффициентов 
берутся из w-строки оптимального решения, 
из целевой функции двойственной задачи
5. Проверка оптимального решения прямой задачи на чувствительность к изменению дефицитных и недефицитных ресурсов
– недефицитный ресурс;
– дефицитные ресурсы.
Приращение целевой функции определяется по формуле:
.
Рассмотрим ресурс : 
Для улучшения целевой функции 
должно быть меньше нуля (
).
при 
.
Таким образом, 
.
Рассмотрим ресурс : 
Для улучшения целевой функции 
должно быть больше нуля (
).
при 
.
Полученные значения не приводят к улучшению целевой функции, поэтому 
.
Рассмотрим ресурс : 
при 
. Таким образом, 
.
6. Проверка оптимального решения прямой задачи на чувствительность к изменению коэффициентов целевой функции при переменных оптимального базиса
при 
и 
.
при 
и 
.
Выбираем значение 
, которое по модулю наиболее приближено к нулю, т. е. 
.
