- •Оглавление
- •Введение
- •Общий вид задачи линейного программирования
- •Решение задачи линейного программирования графическим методом.
- •.Решение задачи линейного программирования симплекс-методом.
- •Симплекс-метод, решение задачи с искусственным базисом
- •Двойственная задача.
- •Задачи для самостоятельного решения
- •Составить математическую модель задачи
- •Решить задачу линейного программирования графическим способом
- •Решить злп симплекс-методом
- •Контрольные вопросы
- •Заключение
- •Литература
Двойственная задача.
Двойственная задача (ДЗ) – это вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными, чем при ПЗ. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Для перехода к ДЗ необходимо, чтобы прямая задача была записана в стандартной канонической форме. При представлении ПЗ в стандартной форме в состав переменных включаются также избыточные и остаточные переменные.
Двойственная задача имеет:
m переменных, соответствующих числу ограничений прямой задачи; (Каждому ограничению ПЗ соответствует переменная ДЗ);
n ограничений, соответствующих числу переменных прямой задачи(Каждой переменной ПЗ соответствует ограничение ДЗ);
Коэффициенты при в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;
Коэффициенты при в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;
Постоянные ограничений ПЗ становятся коэффициентами целевой функции ДЗ.
Неравенства в системах ограничений имеют противоположный смысл(знаки неравенств меняются на противоположные);
Целевые функции в задачах имеют противоположный смысл: в первой –max, во второй – min.
Рассмотрим пример составления двойственной задачи:
Прямая задача
Двойственная задача
Рассмотрим пример составления ДЗ.
Прямая ЗЛП
ЦФ F(x)=x1+4x2+3x3+2x4 max
О граничения
-x1+3x2+2x3=6
3x2+2x4<=3
2x2-x3>=4
2x1-3x3+2x4<=8
Обратная(ДЗ) ЗЛП
ЦФ T(y)=6y1+3y2+4y3+8y4 min
О граничения
-y1+2y4=1
3y1+3y2+2y3>=4
2y1-y3-3y4<=3
2y2+2y4>=2
Дана следующая задача линейного программирования (ЗЛП).
,
Для решения используем ранее приведённый алгоритм.
1. Переход от неравенств к равенствам по правилам введения дополнительных переменных. Исходную задачу необходимо привести к стандартной форме: введем замену по переменной , и дополнительные переменные:
,
Полученный вид ЗЛП не позволяет сформировать начальный допустимый базис, т. к. нельзя выделить единичные орты во втором и третьем равенствах. Для получения начального допустимого базиса введём искусственные переменные. В результате получим:
,
2. Общее число переменных определим по формуле: N=2+3+2=7, где - число искусственных переменных. Число базисных переменных определяется числом ограничений, т. к. , то система имеет три базисные переменные и небазисные переменные .
3. Получение - строки для СТ (0). Приведём целевую функцию к виду
.
Выразим R1 и R2
,
Подставим
4. Формирование симплекс – таблицы на первом шаге:
СТ (0)
|
|
|
|
|
|
|
|
|
свободные члены |
|
1 |
-1-4M |
3+3M |
-3M-3 |
M |
0 |
0 |
0 |
-12M |
|
0 |
1 |
2 |
-2 |
0 |
1 |
0 |
0 |
4 |
|
0 |
3 |
-4 |
4 |
0 |
0 |
1 |
0 |
12 |
|
0 |
1 |
1 |
-1 |
-1 |
0 |
0 |
1 |
0 |
5. Определение разрешающего столбца.
При решении задачи максимизации выбираем в - строке максимально отрицательный коэффициент: - включаемая переменная.
6. Определение разрешающей строки: – исключаемая переменная.
7. Разрешающий элемент РЭ = 1.
8. Получение матрицы перехода
, где В(0) - матрица перехода
9. Определение элементов таблицы СТ(1) = В(0) СТ(0);
10. Исследование z-строки СТ(1) на условие оптимальности:
С Т(1)
|
z |
|
|
|
|
|
|
|
свободные члены |
z |
1 |
0 |
4+7M |
-7M-4 |
-3M-1 |
0 |
0 |
1+4M |
-12M |
|
0 |
0 |
1 |
-1 |
1 |
1 |
0 |
-1 |
4 |
|
0 |
0 |
-7 |
7 |
3 |
0 |
1 |
-3 |
12 |
|
0 |
1 |
1 |
-1 |
-1 |
0 |
0 |
1 |
0 |
СТ(2)
|
z |
|
|
|
|
|
|
|
Свободные члены |
z |
1 |
0 |
0 |
0 |
5/7 |
0 |
M+4/7 |
M-5/7 |
48/7 |
|
0 |
0 |
0 |
0 |
10/7 |
1 |
1/7 |
-10/7 |
40/7 |
|
0 |
0 |
-1 |
1 |
3/7 |
0 |
1/7 |
-3/7 |
12/7 |
|
0 |
1 |
0 |
0 |
-4/7 |
0 |
1/7 |
4/7 |
12/7 |
СТ(2) – оптимальная, т. к. коэффициенты в z строке .
, , .
Двойственная задача.
Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений :
Прямая задача
Двойственная задача
(А)
(В)
Итак, получено: , , .
Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки: .
Для удобства решения свернём ограничения (А) и (В) в одно со знаком равенства, а также введем в ограничения и целевую функцию избыточные, остаточные и искусственные переменные.
Решим ДЗ симплекс методом:
выразим
выразим:
С Т(0)
|
W |
|
|
|
|
|
|
|
свободные члены |
W |
1 |
-4-M |
7M-12 |
12-7M |
0 |
-M |
0 |
0 |
4M |
|
0 |
1 |
3 |
-3 |
-1 |
-1 |
1 |
0 |
1 |
|
0 |
-2 |
4 |
-4 |
1 |
0 |
0 |
1 |
3 |
СТ(1)
|
W |
|
|
|
|
|
|
|
Свободные члены |
W |
1 |
-10/3M |
0 |
0 |
7/3M-4 |
4/3M-4 |
-7/3M+4 |
0 |
5/3M+4 |
|
0 |
1/3 |
1 |
-1 |
-1/3 |
-1/3 |
1/3 |
0 |
1/3 |
|
0 |
-10/3 |
0 |
0 |
7/3 |
4/3 |
-4/3 |
1 |
5/3 |
СТ(2)
-
W
свободные члены
W
1
-40/7
0
0
0
-12/7
-7/3M+4
-M+12/7
48/7
0
-1/7
1
-1
0
-1/7
1/3
1/7
4/7
0
-10/7
0
0
1
4/7
-4/3
-3/7
5/7
СТ(2) – оптимальная, т. к. коэффициенты в z строке <=0
, ,