x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Предупреждение

Очистить все ячейки?

Закрыть Очистить

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

Примеры решения ЗЛП симплекс методом

Пример 1. Решить следующую задачу линейного программирования:

Правая часть ограничений системы уравнений имеет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x при . min (40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x 3 . Сделаем исключение Гаусса для столбца x 2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x 1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x 4 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F (X )=.

Пример 2. Найти максимум функции

Р е ш е н и е.

Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x 2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x 2 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x 3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x 5 . Сделаем исключение Гаусса для столбца x 3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

Пример 2. Найти оптимальный план задачи линейного программирования:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

Так как есть три единичных вектора, то
можно сразу записать опорный план
Х=(0,0,0,360,192,180).
Составим нулевую симплекс-таблицу

Полученный опорный план проверяем
на оптимальность.
Вычисляем значение целевой функции и
симплекс-разности.
F0 c P0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

Как видно из 0-й таблицы отличными от нуля
являются переменные x4 , x5 , x6 , а x , x , x
1
2
3
равны нулю, т.к. они небазисные, а свободные.
Дополнительные же переменные x4 , x5 , x6
принимают свои значения в соответствии с
ограничениями.
Эти значения переменных отвечают такому
«плану», при котором ничего не производится, сырье
не используется и значение целевой функции равно
нулю, т. е. стоимость произведенной продукции
отсутствует.
Такой план, конечно, не является оптимальным.
Это видно и из 4-й строки таблицы, в которой
имеется три отрицательных оценки -9, -16 и -10.

10.

Отрицательные числа не только
свидетельствуют о возможности увеличения
общей стоимости производимой продукции (в
столбцах над отрицательными оценками
стоят положительные числа), но и
показывают, на сколько увеличится эта сумма
при введении в план единицы того или иного
вида продукции.
Так, число -9 означает, что при включении в
план производства одного изделия А
обеспечивается увеличение стоимости
продукции на 9 д.е.

11.

Если включить в план производства по
одному изделию В и С, то общая стоимость
изготовляемой продукции возрастет
соответственно на 10 и 16 д.е. Поэтому с
экономической точки зрения целесообразным
является включение в план изделий С.
Это же необходимо сделать и с той точки
зрения, что -16 является наименьшей
отрицательной оценкой. Значит, в базис
введем вектор P3 .

12.

Найдем число Q .
360 192 180
Q min
;
;
min 30; 24;60
3
12 8
Введем его в последний столбец таблицы.
Число 24 соответствует вектору P5 .
192/8=24 с экономической точки зрения
означает, какое количество изделий С
предприятие может изготовлять с учетом
норм расхода и имеющихся объемов сырья
каждого вида.

13.

Так как сырья каждого вида имеется
соответственно 360, 192 и 180 кг, а на одно
изделие С требуется затратить сырья каждого
вида 12, 8 и 3 кг, то максимальное число
изделий С, которое может быть изготовлено
предприятием равно
min{360/12,192/8,180/3}=192/8=24, т.е.
ограничивающим фактором для производства
изделий С является имеющийся объем сырья
2-го вида. С учетом его предприятие может
производить 24 изделия С.При этом сырье 2го вида будет полностью использовано и,
значит, вектор подлежит исключению из
P5
базиса.

14.

Составляем следующую таблицу. В ней
разрешающей является вторая строка,
а разрешающим столбцом –третий. На
их пересечении стоит элемент 8.
Разделим вторую строку на 8, а затем
обнулим по методу Жордана- Гаусса
или по формулам треугольника третий
столбец.

15.

16.

Подсчитаем симплекс-разности и заполним 4ю строку таблицы.
При данном плане производства
изготовляется 24 изделия С и остается
неиспользованным 72 кг сырья 1-го и 108 кг
сырья 3-го вида. 2-й вид сырья использован
полностью. Стоимость всей продукции при
этом плане составляет 384 д.е. Указанные
числа записаны в столбце План. Это опять
параметры задачи, но они претерпели
изменения. Изменились и данные других
столбцов. Их экономическое содержание
стало еще более сложным.

17.

Имеется одна отрицательная оценка -2.
План можно улучшить. Введем в базис
вектор P2 . Вычислим
72 24 108
Q min ;
;
min 8; 48;72 8.
9 1/ 2 3 / 2
.
Выводим из базиса P4 .

18.

Разрешающими будут 1-я строка и 2-й
столбец. Разрешающий элемент 9.
Разделим на 9 1-ю строку, заполним
1-ю строку новой таблицы, затем
обнулим 2-й столбец. Для этого
умножим 1-ю строку на (-1/2) и
прибавим ко 2-й, а затем умножим 1-ю
строку на (-3/2) и прибавим к 3-й строке.
Заполним таблицу 2.

19.

20.

В этом мы убеждаемся,
вычисляя симплекс-разности
1 cP1 c1 10 1 16 0.25 9 5,
2 cP2 c2 10 1 16 0 10 0,
3 cP3 c3 10 0 16 1 0 0 16 0,
4 cP4 c4 10 1/ 9 16 1/ 8 0 (1/ 6) 2 / 9,
5 cP5 -c5 =10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

Оптимальным планом производства не
предусмотрен выпуск изделий А. Введение в
план выпуска продукции вида А привело бы к
уменьшению указанной общей стоимости.
Это видно из 4-й строки столбца, где число 5
показывает, что при данном плане включение
в него выпуска единицы изделия А приводит
лишь к уменьшению общей величины
стоимости на 5 д.е.
Итак, план предусматривает выпуск 8 изделий
В и 20 изделий С. Сырье видов 1 и 2
используется целиком, а вида 3неиспользованным остается 96 кг.

22. ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Каждой ЗЛП можно поставить в соответствие
задачу, называемую двойственной к исходной
задаче.
Рассмотрим задачу об использовании
ресурсов. Предположим, что предприятие А
производит n видов продукции, величина
выпуска которых определяется переменными
x1 , x2 , ..., xn
.
В производстве используются m различных
видов ресурсов, объем которых ограничен
величинами b1 , b2 , ..., bn .

23.

Известны нормы затрат каждого ресурса на единицу
каждого вида продукции, образующие матрицу,
a11
a21
A
...
am1
a12
a22
...
am 2
... a1n
... a2 n
... ...
... amn
а также стоимость единицы продукции каждого вида
c1 , c2 , ..., cn
Требуется организовать производство так, чтобы
предприятию А была обеспечена максимальная
прибыль.

24.

Задача сводится к нахождению
неотрицательных переменных
x1 , x2 , ..., xn ,
при которых расход ресурсов не
превышает заданного их количества, а
стоимость всей продукции достигнет
максимума.

25.

В математической форме задача
записывается следующем виде:
F c1 x1 c2 x2 ... c j x j ... cn xn max
при условиях
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
a x a x ... a x ... a x b
mj j
mn n
m
m1 1 m 2 2
x j 0, j 1, n.

26.

По этим же исходным данным может быть
сформулирована другая задача.
Предположим, что предприятие В решило закупить
все ресурсы, которыми располагает предприятие А. В
этом случае предприятию В необходимо установить
оптимальные цены на эти ресурсы, исходя из
следующих условий:
общая стоимость ресурсов для предприятия В
должна быть минимальной;
за каждый вид ресурса предприятию А надо
уплатить не менее той суммы, которую это
предприятие может получить при переработке
данного вида ресурса в готовую продукцию.

27.

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

28.

т.е.какова должна быть оценка единицы
каждого из ресурсов y1 , y2 , ..., yn ,
чтобы при заданных объемах
имеющихся ресурсов bi , при заданных
стоимостях c j (j 1, n) единицы
продукции и нормах расходов aij
минимизировать общую оценку затрат
на всю продукцию.

29. Мат. модель двойственной задачи

В математической форме задача
записывается в виде:
*
F b1 y1 b2 y2 ... bm ym min
при ограничениях
a11 y1 a21 y2 ... am1 ym c1 ,
a y a y ... a y c ,
m2 m
2
12 1 22 2
..................................................
a y a y ... a y c ,
mn m
n
1n 1 2 n 2
yi 0, i 1, 2,..., m.

30. Экономический смысл переменных двойственной задачи

Переменные yi двойственной задачи в литературе
могут иметь различные названия:учетные, неявные,
теневые, объективно обусловленные оценки,
двойственные оценки или «цены» ресурсов.
Эти две задачи образуют пару взаимно
двойственных задач, любая из которых может
рассматриваться как исходная. Решение одной
задачи дает оптимальный план производства
продукции, а решение другой – оптимальную
систему оценок сырья, используемого для
производства этой продукции.

31.

Двойственные задачи линейного
программирования называют
симметричными, если они удовлетворяют
следующим свойствам:
число переменных в двойственной задаче
равно числу ограничений исходной задачи, а
число ограничений двойственной задачи
равно числу равно числу переменных в
исходной;
в одной задаче ищется максимум целевой
функции, в другой – минимум;
коэффициенты при переменных в целевой
функции одной задачи являются свободными
членами системы ограничений другой задачи;

32.

в каждой задаче система ограничений задается в
виде неравенств, причем, в задаче на отыскание
максимума, все неравенства вида «≤», а в задаче на
отыскание минимума, все неравенства вида «≥»;
матрица коэффициентов системы ограничений
получается одна из другой путем транспонирования;
каждому ограничению одной задачи соответствует
переменная другой задачи, номер переменной
совпадает с номером ограничения;
условия не отрицательности переменных
сохраняются в обеих задачах;

33. Решение симметричных двойственных задач

Первая теорема двойственности.
Если одна из двойственных задач
имеет оптимальное решение, то
оптимальное решение имеет и другая
задача, при этом значения целевых
функций задач равны между собой.
Если целевая функция одной из
задач не ограничена, то другая задача
вообще не имеет решения

34. Экономическое содержание первой теоремы двойственности

Если задача определения оптимального плана,
максимизирующего выпуск продукции, разрешима, то
разрешима и задача определения оценок ресурсов.
Причем цена продукта, полученного в результате
реализации оптимального плана, совпадает с
суммарной оценкой ресурсов.
Совпадения значений целевых функций для
соответствующих решений пары двойственных задач
достаточно для того, чтобы эти решения были
оптимальными.
Решая ЗЛП симплекс-методом, мы одновременно
решаем и исходную и двойственную задачи.

35. Метод одновременного решения пары двойственных задач

Исходная задача: Двойственная задача:
F c1x1 c2 x2 ... c j x j ... F * b1 y1 b2 y2 ...
cn xn max
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
a x a x ... a x x b ,
mn n
n m
m
m1 1 m 2 2
x j 0, j 1, 2,..., n m.
bm ym min,
a11 y1 a21 y2 ... am1 ym ym 1 c1 ,
a y a y ... a y y c ,
m2 m
m 2
2
12 1 22 2
.............................................................
a y a y ... a y y c ,
mn m
m n
n
1n 1 2 n 2
yi 0, i 1, 2,..., m n.

36.

Число переменных в задачах одинаково
и равно m + n. В исходной задаче
базисными переменными являются

переменные xn 1 , xn 2 , ..., xn m
,
а в двойственной задаче –
вспомогательные неотрицательные
переменные yn 1 , yn 2 , ..., yn m .
Базисным переменным одной задачи
соответствуют свободные переменные
другой задачи, и наоборот.

37.

38.

При решении ЗЛП табличным симплексметодом решение двойственной задачи
содержится в последней строке таблицы.
Это j.
Причем основные переменные двойственной

соответствующих дополнительным
переменным исходной задачи, а
дополнительные переменные двойственной
задачи содержатся в столбцах,
соответствующих основным
(первоначальным) переменным исходной
задачи.

39. Пример.

Сформулируем модель задачи, двойственной
к задаче из примера 2 (начало лекции):
Найти максимум функции

40.

41.

Переменные исходной задачи x1 , x2 , x3 это количество изделий А,В и С. Введем
переменные двойственной задачи y1 , y2 , y3
Найти минимум функции
F * 360 y1 192 y2 180 y3 min
при ограничениях
18 y1 6 y2 5 y3 9,
15 y1 4 y2 3 y3 10,
12 y 8 y 3 y 16,
2
3
1
y1 , y2 , y3 0.

42. Рассмотрим последнюю таблицу исходной задачи

43.

Значение y1 в последней строке столбца P4 ,
т.е. y1 2 ;
9y 5
значение 2 3 в последней строке столбца P5,
значение y3 0 в последней строке столбца P6 .
Остальные значения находим в столбцах 1,2,3.
2 5
Y (; ;0;5;0;0)
9 3
При этом
2
5
F 360 192 180 0 0 5 0 0 0 0 400
9
3
*
-это минимальные затраты на всю продукцию.
2/9 и 5/3 –это теневые цены сырья 1-го и 2-го
видов соответственно.

Краткая теория

Заполняем симплексную таблицу 0-й итерации.

БП

Симплексные отношения

8

6

4

0

0

0

0

520

16

18

9

1

0

0

65/2

0

140

7

7

2

0

1

0

20

0

810

9

2

1

0

0

1

90

0

-8

-6

-4

0

0

0

Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.

Переход к следующей итерации осуществляем следующим образом:

Ведущий столбец соответствует .

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

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

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .

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

Получаем таблицу 1-й итерации:

БП

Симплексные отношения

8

6

4

0

0

0

0

200

0

2

31/7

1

-16/7

0

1400/31

8

20

1

1

2/7

0

1/7

0

70

0

630

0

-7

-11/7

0

-9/7

1

-

160

0

2

-12/7

0

8/7

0

Ключевой столбец для 1-й итерации соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 31/7.

Вектор выводим из базиса и вводим вектор .

Получаем таблицу 2-й итерации:

БП

Симплексные отношения

8

6

4

0

0

0

4

1400/31

0

14/31

1

7/31

-16/31

0

8

220/31

1

27/31

0

-2/31

9/31

0

0

21730/31

0

-195/31

0

11/31

-65/31

1

7360/31

0

86/31

0

12/31

8/31

0

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

Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.

Постановка задачи

Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой:

Прямая:

F(x)=c 1 x 1 + c 2 x 2 +…+ c n x n →max

a 11 x 1 + a 12 x 1 +…+ a 1n x n ≤b 1 ,

a 21 x 1 + a 22 x 1 +…+ a 2n x n ≤b 2 ,

………………………………

a k1 x 1 + a k2 x 1 +…+ a kn x n ≤b k ,

a k+1,1 x 1 + a k+1,2 x 1 +…+ a k+1,n x n =b k+1 ,

………………………………

a m1 x 1 + a m2 x 1 +…+ a mn x n= b m ,

Двойственная:

F*(Y)=b 1 y 1 + b 2 y 2 +…+ b m y m →min

a 11 y 1 + a 21 y 2 +…+ a m1 y m ≥c 1 ,

a 12 y 1 + a 22 y 2 +…+ a m2 y m ≥c 2 ,

………………………………

a 1l y 1 + a 2l y 1 +…+ a ml y m ≤c l ,

a 1,l+1 y 1 + a 2,l+1 y 2 +…+ a m,l+1 y m =c l+1 ,

………………………………

a 1n y 1 + a 2n y 1 +…+ a mn y m= c m ,

Двойственная задача по отношению к исходной составляется согласно правилам:

1. Целевая функция исходной задачи задается на максимум, а двойственной на минимум.

2. Матрица из коэффициентов при неизвестных исходной задачи и аналогичная матрица двойственной задачи получаются друг из друга транспонированием.

3. Число переменных в двойственной задаче равно числу соотношений в системе ограничений исходной задачи, а число ограничений двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в системе ограничений двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная хj исходной задачи может принимать только лишь положительные значения, то j- e условие в системе ограничений двойственной задачи является неравенством вида "≥ ". Если же переменная хj может принимать и отрицательные значения, то j -e соотношение в двойственной задаче будет равенством. Если i -e соотношение в исходной задаче является неравенством, то і- я переменная двойственной задачи yi≥0. В противном случае yi может принимать как положительные, так и отрицательные значения.

Двойственные пары задач подразделяются на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой и двойственной задач могут принимать лишь неотрицательные значения.

Связь между решениями прямой и двойственной задач.

Если основная задача линейного программирования имеет оптимальный план Х*, то Y*= C δ . является оптимальным планом двойственной задачи. Здесь C δ - вектор-строка коэффициентов целевой функции при базисных переменных оптимальной симплекс-таблицы прямой задачи, а - матрица обратная матрице, составленной из компонентов векторов, входящих в последний базис, при котором получен оптимальный план. Если прямая задача приведена к единичному базису при неотрицательных свободных членах уравнений, вычисление обратной матрицы не требуется, так как будет состоять из столбцов оптимальной симлекс-таблицы, полученных на месте единичных столбцов исходной таблицы.

Пример 1.

Задана прямая задача:

х 1 , х 2 ≥0

Составить двойственную задачу.

Решение:

Прежде всего третье ограничение умножим на "-1", так как оно имеет знак «≥». Это ограничение примет вид

-5х 1 +3х 2 -6х 3 ≤-19

Матрица из коэффициентов при неизвестных в ограничениях будет:

Запишем транспонированную к ней матрицу:

Тогда двойственная задача запишется:

у 1 , у 3 ≥0

Так как в прямой задаче второе ограничение имеет знак "=", то переменная y 2 не имеет ограничения на знак. Третье ограничение двойственной задачи имеет знак "=" так как переменная х 3 не имеет ограничения на знак.

Пример 2.

Прямая задача

х 1 , х 4 ≥0

Двойственная задача

	Баз. вект	С баз	А 0
	А 1	А 2	А 3	А 4	А 5
	А 3				-1
←	А 5						-1
		∆		-1	-5		-3

	Баз. вект	С баз	А 0
	А 1	А 2	А 3	А 4	А 5
←	А 3		14/3	10/3			8/3	1/3
	А 2		5/3	1/3			-1/3	1/3
		∆	34/3	5/3			-14/3	5/3

Баз. вект	С баз	А 0
А 1	А 2	А 3	А 4	А 5
А 4		7/4	5/4		3/8		1/8
А 2		9/4	3/4		1/8		3/8
	∆	78/4	15/2		7/4		9/4

Из последней таблицы получим оптимальный план:

Х опт =(0, 9/4, 0, 7/4);

Данные этой же таблицы используются для определения оптимального решения двойственной задачи.

Вектор С опт =(С 4 , С 2)=(6,4) . Матрица Ах состоит из векторов А 4 А 2 , взятых из ограничений по которым составляется двойственная задача:

А х =(А 4 А 2)=

Обратная матрица будет:

Тогда:

F min =

Примечание: Так как исходная задача приведена к единичному базису при неотрицательных свободных членах уравнений, то обратная матрица Ах -1 состоит из компонентов векторов А 3 и А 5 последней симплекс- таблицы.

3. Варианты заданий

К данной задаче составить сопряженную, решить одну из них и по найденному решению получить решение второй.

1)	F=x 1 +x 2 →max		2)	F=3x 1 +x 2 →min
3)	F=3x 1 +3x 2 →min		4)	F=6x 1 -5x 2 →max
5)	F=8x 1 +2x 2 →max		6)	F=x 1 +2x 2 →max
7)	F=14x 1 +10x 2 +14x 3 +14x 4 →max		8)	F=2x 1 +3x 2 →min

Симплекс-метод является универсальным. С его помощью может быть решена любая задача линейного программирования. Однако в силу своей универсальности, он не свободен от некоторых недостатков. В ряде случаев для решения задач линейного программирования более подходящими оказываются так называемый двойственный метод. Этот метод базируется на теории двойственности, одной из важнейших составных частей общей теории линейного программирования.

Теория двойственности используется для разработки методов решения многих практически важных классов линейных оптимизационных задач: задач транспортного типа, линейных целочисленных задач и т.д. Рассмотрим основные положения этой теории.

Каждой задаче линейного программирования соответствует другая задача, в определенном смысле ей противоположная. Если первая задача называется прямой, то противоположная - двойственной. Так как двойственная по отношению к двойственной задаче - это исходная прямая задача, то неважно, какую из задач назвать прямой, а какую двойственной. Поэтому прямую и двойственную задачи называют задачами двойственной пары.

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

Выделяют симметричные, несимметричные и смешанные двойственные задачи. В симметричных задачах ограничения прямой задачи имеют вид . В ограничениях несимметричной задачи в ограничениях прямой задачи используются знаки равенства. В смешанных задачах используются оба вида отношений «меньше или равно» и «Равно». В несимметричных и смешанных задачах на вновь вводимые переменные не накладывается требование их неотрицательности.

Вычисления, основанные на соотношениях двойственности, начинаются с приведения прямой и двойственной задачи к стандартной форме. Поэтому можно ограничиться формулировкой правил образования задачи двойственной по отношению к стандартной задаче линейного программирования. Правила получения двойственной задачи для других видов задачи ЛП могут быть получены из данных правил.

Запишем задачу ЛП в стандартной форме:

,

,

i=1,..,m; j=1,..,n.

Назовем эту задачу прямой. Тогда двойственной по отношению к ней будет задача:

,

i=1,..,m; j=1,..,n.

Проанализировав задачи, можно сделать следующие выводы:

1. Каждому ограничению прямой задачи соответствует переменная двойственной задачи.

2. Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

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

4. Вид экстремума двойственной задачи противоположен виду экстремума прямой задачи;

5. Векторы В и С в прямой и двойственной задачах меняются местами;

6. Матрица A двойственной задачи получается путем транспонирования матрицы А прямой задачи;

7. Все ограничения двойственной задачи имеют вид для задачи максимизации и вид для задачи минимизации линейной формы.

Для случая симметричной двойственной задачи:

Для случая несимметричной задачи:

Двойственная задача имеет вид:

Смешанные задачи содержат ограничения в виде равенств и неравенств. При составлении двойственной задачи необходимо использовать правила перехода для симметричной и несимметричной задач.

Приведенные ниже примеры служат иллюстрацией правил получения двойственных задач.

Пример Дана задача линейного программирования (слева от каждого ограничения стоит ассоциированная с ним двойственная переменная). Данная задача относится к несимметричной.

,

Сформулируем для этой задачи двойственную задачу. Целевая функция двойственной задачи представляет собой линейную форму, полученную как произведение вектора b=(10,20,60,80) на вектор переменных двойственной задачи Y =(). Кроме того, поскольку в прямой задаче целевая функция максимизируется, в двойственной она минимизируется. С учетом сделанных замечаний получим,

Левая часть первого ограничения двойственной задачи представляет собой произведение вектора системы ограничений прямой задачи, ассоциированного с переменной , на вектор переменных двойственной задачи. Правая часть этого ограничения равна коэффициенту при переменной , в целевой функции прямой задачи.

А поскольку к тому же, прямая задача является задачей поиска максимума, то первое ограничение имеет вид:

Рассуждая аналогично, получим второе ограничение двойственной задачи: . Отсутствие переменной в этом ограничении связано с тем обстоятельством, что во втором ограничении прямой задачи нет переменной .

Переменная , ассоциированная с третьей переменной двойственной задачи, встречается только в первом ограничении прямой задачи. По этой причине для третьего ограничения получим . Рассуждая по аналогии, получим четвертое, пятое и шестое ограничения: .

Таким образом, не смотря на то, что на переменные двойственной задачи условие не отрицательности специально не накладывалось, тем не менее, для всех их оно оказалось выполненным.

Пример Дана задача линейного программирования в нестандартной форме

,

,

,

Не ограничена в знаке, .

Запишем эту задачу в стандартной форме. Для этого сделаем замену переменных , введем во второе ограничение избыточную переменную , а в третье - добавочную переменную . Получим

,

.

Сформулируем двойственную задачу. Поскольку в прямой задаче целевая функция минимизируется, целевая функция двойственной задачи имеет вид .

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

,

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

.

Таким образом, из трех переменных двойственной задачи одна - оказалась неограниченной в знаке.

С помощью теорем двойственности, зная решение одной из задач можно найти оптимальное решение другой не решая ее.

Рассмотрим смешанную задачу.

Двойственная для нее задача будет иметь вид:

Если использовать каноническую форму задачи линейного программирования, то имеем дело с несимметричной задачей линейного программирования.

Каноническая форма задачи имеет вид:

Двойственная задача будет иметь вид:

Теорема 1. Для любой пары допустимых решений прямой и двойственной задач значение целевой функции в задаче максимизации не превосходит значения целевой функции в задаче минимизации.

Практическая ценность этой теоремы заключается в следующем. На практике иногда лучше получить решение, близкое к оптимуму, но за малое время, чем оптимальное - но за время, существенно большее. В этом случае последнее неравенство может служить оценкой близости решения, полученного на очередной итерации, к оптимуму.

Теорема 2. Если одна из двойственных задач имеет оптимальное решение, то другая тоже имеет оптимальное решение, причем значения целевых функций для обеих решений совпадают. Если одна из двойственных задач имеет неограниченную целевую функцию, то другая неразрешима, т.е не имеет допустимых решений.

Теорема. Для оптимальности допустимых решений необходимо и достаточно, чтобы они удовлетворяли системе уравнений

.

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

Пример Решим симметричную задачу. Пусть исходная задача имеет вид

Решив задачу графическим методом, получим

Составим для нее двойственную задачу

Так целевые функции в точке оптимума равны, то

Так как переменные
, то соответствующие им ограничения в двойственной задаче содержат знак равенства. Данные ограничения имеют вид

Подставим в ограничения значения . Получим

.

В данной системе только первое неравенство является строгим. Следовательно, . Другие значения переменных найдем из системы уравнений

.

В результате решения данной системы линейных алгебраических уравнений, получим

Решим ту же задачу, однако считая, что известно решение

Так как вторая и третья переменные строго больше нуля, то соответствующее им ограничение выполняется как строгое равенство.

.

Решая данную систему уравнений, получим

Если исходная задача решена симплексным методом и в итоговой целевой функции получены коэффициенты - матрица – строка коэффициентов, то решение двойственной задачи может быть найдено по формуле где -матрица коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи.

Рассмотрим экономическую интерпретацию двойственной задачи.

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

То двойственные переменные показывают, как изменится целевая функция при изменении ресурса на единицу