Решение - Симплекс метод и двойственная задача - файл n1.docx
приобрестиРешение - Симплекс метод и двойственная задачаскачать (142.5 kb.)
Доступные файлы (1):
n1.docx





Решить задачу линейного программирования симплекс методом, затем найти решение двойственной задачи.
Решение.
Решим задачу на максимум.
Математическая модель данной задачи имеет вид:
при ограничениях
Преобразуем задачу к каноническому виду. Введем три (по количеству ограничений) дополнительных неотрицательных переменных

и добавим по одному из них к левым частям неравенств, преобразуя их в равенства. Получаем задачу:
при ограничениях
Каждая из переменных
входит только в одно из уравнений системы. Возьмем эти переменные в качестве базисных, а переменные
в качестве свободных. Составляем первую симплекс-таблицу:
3
4
1
0
0
0
0
2
4
-5
1
0
0
14
3,5
0
9
5
1
0
1
0
27
5,4
0
0
1
1
0
0
1
5
5
-3
-4
-1
0
0
0
0
В столбце БП записаны базисные переменные, включаемые в план; в С
б – прибыль единицы продукции, которая вводится в план, т.е. коэффициенты при базисных переменных в целевой функции; в столбце В – свободные величины; в правом крайнем столбце будем записывать промежуточные симплексные отношения; в остальных – коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.
В нижней строке (целевой) записываются получаемые расчетным путем показатели: в столбце В – суммарная прибыль планового выпуска, в остальных столбцах – прибыль единицы продукции с отрицательным знаком.
Запишем начальный опорный план:


,

. Этот план не является оптимальным, так как в индексной строке есть отрицательные элементы.
Чтобы получить новый опорный план, выполним симплексные преобразования таблицы 1. Введем в базис переменную

, которой соответствует наибольшая по модулю отрицательная индексная оценка, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять 2-й столбец. Чтобы определить переменную, выводимую из базиса, составим симплексные отношения (элементы столбца В делим на соответствующие элементы разрешающего столбца) и выберем наименьшее из них:

Следовательно, из базиса надо исключить переменную
. На пересечении разрешающих столбца и строки находится разрешающий элемент

, относительно которого выполнятся симплексные преобразования. При переходе к новой симплексной таблице будем пользоваться следующими правилами:

.
Аналогично определяются элементы индексной строки и столбца свободных членов.
В результате приходим к таблице 2:
Таблица 2
3
4
1
0
0
0
4
1/2
1
-5/4
1/4
0
0
7/2
-
0
13/2
0
29/4
-5/4
1
0
19/2
38/29
0
-1/2
0
9/4
-1/4
0
1
3/2
2/3
-1
0
-6
1
0
0
14
Выпишем опорный план:


,

. Однако этот план не является оптимальным, так как в индексной строке есть отрицательные элементы.
Чтобы получить новый опорный план, выполним симплексные преобразования таблицы 2.
Введем в базис переменную

, которой соответствует отрицательная индексная оценка, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять 3-й столбец. Cоставим симплексные отношения и выберем наименьшее из них:

Следовательно, из базиса надо исключить переменную
. На пересечении разрешающих столбца и строки находится разрешающий элемент

, относительно которого выполнятся симплексные преобразования.
Получим таблицу 3.
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
3 | 4 | 1 | 0 | 0 | 0 |
 | 4 | 2/9 | 1 | 0 | 1/9 | 0 | 5/9 | 13/3 | 39/2 |
 | 0 | 73/9 | 0 | 0 | -4/9 | 1 | -29/9 | 14/3 | 42/73 |
 | 1 | -2/9 | 0 | 1 | -1/9 | 0 | 4/9 | 2/3 | - |
 | -7/3 | 0 | 0 | 1/3 | 0 | 8/3 | 29 |
|
Выпишем опорный план:



,

.
Однако этот план не является оптимальным, так как в индексной строке есть отрицательные элементы.
Чтобы получить новый опорный план, выполним симплексные преобразования таблицы 3.
Введем в базис переменную

, которой соответствует отрицательная индексная оценка, т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять 1-й столбец. Cоставим симплексные отношения и выберем наименьшее из них:

Следовательно, из базиса надо исключить переменную
. На пересечении разрешающих столбца и строки находится разрешающий элемент

, относительно которого выполнятся симплексные преобразования.
Получим таблицу 4.
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
3 | 4 | 1 | 0 | 0 | 0 |
 | 4 | 0 | 1 | 0 | 9/73 | -2/73 | 47/73 | 307/73 |
|
 | 3 | 1 | 0 | 0 | -4/73 | 9/73 |
 | 42/73 |
|
 | 1 | 0 | 0 | 1 | -9/73 | 2/73 | 26/73 | 58/73 |
|
 | 0 | 0 | 0 | 15/73 | 21/73 | 127/73 | 2215/73 |
|
Так как в индексной строке нет отрицательных элементов, то полученный план является оптимальным, а соответствующее ему значение целевой функции будет максимальным.
Ответ:
Составим математическую модель двойственной задачи.
Напишем матрицу исходной задачи:
и транспонируем ее. В результате получим матрицу двойственной задачи:
При этой матрице напишем модель задачи, двойственной к исходной задаче:

;

.
Из теоремы двойственности следует, что если решена одна из пары двойственных задач, то одновременно найдено решение и другой задачи. Компоненты оптимального плана двойственной задачи находятся в индексной строке последней симплексной таблицы уже решенной задачи.
Запишем каноническую форму математической модели двойственной задачи, введя дополнительные (базисные) переменные

.

;

.
Соответствие между переменными двойственных задач примет вид (СП – свободные переменные, БП – базисные переменные):
В данном случае:

Следовательно, оптимальный план двойственной задачи имеет вид

. Из теоремы двойственности следует, что экстремальные значения целевых функций разрешимых двойственных задач совпадают, поэтому
