Двойственный симплекс-метод решения задач линейного программирования. Решение двойственной задачи Решение двойственной задачи о оптимальной производственной программе

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

Содержание

См. также: Правила составления двойственных задач

Здесь мы рассмотрим вопрос, как из решения прямой задачи, получить решение двойственной задачи.

Теоремы двойственности

Первая теорема двойственности

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

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

Вторая теорема двойственности

;

Применим вторую теорему двойственности. Подставим оптимальные значения переменных в систему ограничений прямой задачи.
(П1.1.1) ;
(П1.1.2) ;
(П1.1.3) ;
(П1.1.4) .
Поскольку первая и четвертая строки являются строгими неравенствами (не являются равенствами), то
и .

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

Подставим уже найденные значения и , имеем:

Отсюда
;
; .

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

Ее решение
;

Пример 2

Дана задача линейного программирования:
(П2.1.1) ;
(П2.1.2)
Найти решение этой задачи, решив двойственную задачу графическим методом.

(П2.2.1) ;
(П2.2.2)

Решение задачи (П2.2) приводится на странице “Решение задач линейного программирования графическим методом ”. Решение задачи (П2.2) имеет вид:
; .

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

Применим вторую теорему двойственности. Подставим оптимальные значения переменных в систему ограничений прямой задачи (П2.2).
;
;
.
Поскольку третья строка является строгим неравенством (не являются равенством), то
.

Поскольку и , то 1-я и 2-я строки двойственной задачи (П2.1) являются равенствами:

Подставим найденное значение .

Решаем систему уравнений.
;
;
;
; ;
.

Решение исходной задачи (П2.1) имеет вид:
; .

См. также:

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

Теорема 1 (Первая теорема двойственности) . Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и

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

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

Примечание: утверждение, обратное по отношению ко второй части первой теоремы двойственности, в общем случае неверно.

Теорема 2 . Компоненты оптимального плана двойственной задачи (обладающие условием неотрицательности ) равны абсолютным значениям коэффициентов

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

Теорема 3 . Положительным (ненулевым) компонентам оптимального решения одной из задач симметричной двойственной пары соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых и :

Теорема 4 (Третья теорема двойственности) . Компоненты оптимального плана двойственной задачи равны значениям частных производных линейной функции по соответствующим аргументам, т.е.

. (7.2)

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

Пример 9.1. На основе решения примера 5.2 (файл «Алгоритм и примеры симплекс-метода») определим двойственным симплекс- методом оптимальное решение двойственной задачи.

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

Данная двойственная пара является симметричной. Задачи записаны в стандартной форме, приведем их к каноническому виду:

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

Установим соответствие между переменными взаимно двойственных задач.

На основе решения примера 5.2. симплекс-таблица последней итерации (таблица 5.10) имеет вид:

Таблица 9.3

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

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

Следовательно, , .

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

В соответствии с теоремой 1, .

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

Пример 9.2. На основе решения исходной задачи найти оптимальное решение двойственной задачи используя двойственный симплекс-метод.

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

Данная двойственная пара является несимметричной. Приведем к каноническому виду двойственную задачу.

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

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

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

Установим соответствие между переменными взаимно двойственных задач.

Таблица 9.4

Соответствие переменных двойственной пары

Решим исходную задачу симплекс-методом.

Используя метод Жордана-Гаусса, выделим в системе ограничений исходной задачи в качестве базисных переменные и (примечание: не использовать в качестве базисных фиктивные переменные).

В результате преобразований получим следующую матрицу коэффициентов:

Система ограничений исходной задачи примет следующий вид:

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

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

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

Таблица 9.5

Симплекс-таблица оптимального решения исходной задачи

Структура и свойства двойственной задачи

Любую задачу максимизации ЛП с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b 1 ,b 2 ,…,b m между различными потребителями, например, между некоторыми технологическими процессами, которые представляются столбцамиA 1 ,A 2 ,…A n матрицы ограничений задачи. Любое допустимое решение задачи ЛПx 1 ,x 2 ,…x n дает конкретное распределение, указывающее ту долю каждого из ресурсов, которая должна быть использована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Завод производит три вида продукции x 1 ,x 2 иx 3 , каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пустьc 1 ,c 2 ,c 3 – прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль.

Формально эта задача записывается так:

максимизировать (c 1 x 1 +c 2 x 2 +c 3 x 3) (1)

при ограничениях

a 11 x 1 + a 12 x 2 + a 13 x 3 ≤ b 1 ;

a 21 x 1 + a 22 x 2 + a 23 x 3 ≤ b 2 ;

a 31 x 1 +a 32 x 2 +a 33 x 3 ≤b 3 , (2)

где a 1 j ,a 2 j ,a 3 j – время, необходимое для обработки единицыj-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j= 1, 2, 3);b 1 ,b 2 ,b 3 – недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.

Обозначим y 1 ,y 2 иy 3 –цену единицы времени работы на токарном, фрезерном и сверлильном станках. Тогдаa 11 y 1 +a 21 y 2 +a 31 y 3 – можно трактовать как расходы на изготовление единицы продукции первого вида;a 12 y 1 +a 22 y 2 +a 32 y 3 – расходы на изготовление единицы продукта второго вида и т. д.

Предположим, что цены ресурсов y 1 ,y 2 ,…,y m выбраны так, что выполняются следующие соотношения:

a 11 y 1 + a 21 y 2 + a 31 y 3 ≥ с 1 ;

a 12 y 1 + a 22 y 2 + a 32 y 3 ≥ с 2 ;

a 13 y 1 +a 23 y 2 +a 33 y 3 ≥ с 3 . (3)

Поскольку b 1 ,b 2 иb 3 – использованный ресурс машинного времени для каждого из станков, тоb 1 y 1 +b 2 y 2 +b 3 y 3 – суммарные расходы на производство.

Требуется найти такие y 1 ,y 2 иy 3 , удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:

минимизировать g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

при условиях

y 1 ≥0;y 2 ≥0;y 3 ≥0.

Такую задачу называют двойственной задачей по отношению к задаче (1), называемой прямой.

Запишем теперь прямую и двойственную задачи в общем случае.

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

максимизировать

при условиях

(7)

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

минимизировать

при условиях

(10)

В матричном виде пара двойственных задач записывается следующим образом:

максимизировать

при условиях

минимизировать

при условиях

A T y≥c; (15)

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

если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

коэффициенты целевой функции прямой задачи c 1 ,c 2 ,…,c n становятся свободными членами ограничений двойственной задачи;

свободные члены ограничений прямой задачи b 1 ,b 2 ,…,b m становятся коэффициентами целевой функции двойственной задачи;

матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;

знаки неравенств в ограничениях изменяются на обратные;

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

Переменные y 1 ,y 2 ,…,y m двойственной задачи иногда называют теневыми ценами.

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

задаче при малом количестве переменных имеется большое количество ограничений (m n).

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

ТЕОРЕМА 1. Если -допустимые решения прямой и двойственной задач, т. е. то

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

ТЕОРЕМА 2 (основная теорема двойственности). Если -допустимые решения прямой и двойственной задач и если , то – оптимальные решения пары двойственных задач.

ТЕОРЕМА 3. Если в оптимальном решении прямой задачи (5) – (7) i -ое ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, т. е.

где - i -ая строка матрицы А.

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

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

ТЕОРЕМА 4. Если в оптимальном решении двойственной задачи ограничение j выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю, т. е. если то

Дадим экономическую интерпретацию теоремы 4.

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

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

Таким образом, теорема 4 выражает принцип рентабельности оптимально организованного производства.

Из нее вытекает также, что то

(20)

Предположим, что среди переменных x 1 ,x 2 ,…,x n прямой задачи есть множество изmпеременных, которые в оптимальном решении имеют ненулевое значение. Пусть, например, таковыми оказались первые по порядкуmпеременных.

Тогда на основании уравнения (22) получают mусловий рентабельности:

(21)

Приведем еще две важные теоремы теории двойственности.

ТЕОРЕМА 5 (теорема существования). Прямая и двойственная задачи имеют оптимальные решения тогда, и только тогда, когда обе они имеют допустимые решения.

ТЕОРЕМА 6 (теорема двойственности). Допустимый вектор x 0 оптимален тогда, и только тогда, когда в двойственной задаче имеется такое допустимое решение y 0 , что

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

i=1, 2, …,m;j=1, 2, …,n,

где n– количество переменных прямой задачи;m– количество ее ограничений; - соответствующие элементы индексной строки прямой и двойственной задач соответственно. При этом, еслиn+i, где 1 ≤i≤mбольше числа векторов-столбцов матрицы ограничений расширенной формы соответствующей задачи, то элементы находятся путем циклической перестановки элементов индексной строки, начиная с элемента

Общий случай двойственности

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

Пусть прямая ЛП-задача задана в виде:

максимизировать

при условиях

Тогда двойственная задача по отношению к (24)-(26) (или сопряженная с ней) состоит в минимизации линейной формы:

минимизировать

при условиях

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

Если переменная x j прямой задачи предполагается неотрицательной, то j-е условие системы ограничений (28) является неравенством.

Если на x j не накладывается такое ограничение, то j-е ограничение двойственной задачи будет равенством.

Аналогичным образом связаны знаки переменных двойственной задачи y i и соответствующие им ограничения прямой задачи. Заметим, что если положитьm 1 =mиn 1 =n, то получим частный случай пары двойственных задач с ограничениями в форме неравенств.

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

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

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

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

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

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

Решение прямой задачи о оптимальной производственной программе

Учитывая высокий уровень математической подготовки подавляющего большинства пользователей данного ресурса не стану приводить балансовые уравнения с верхними и нижними ограничениями и введением для перехода к равенствам дополнительных переменных. Поэтому сразу приведу обозначения используемых в решении переменных:
N – количество видов производимых изделий;
m– количество видов используемого сырья;
b_ub - вектор имеющихся ресурсов размерности m;
A_ub – матрица размерности m×N, каждый элемент которой является расходом ресурса вида i на производство единицы изделия вида j;
с - вектор прибыли от производства единицы изделия каждого вида;
x – искомые объёмы производимых изделий каждого вида (оптимальный план производства) обеспечивающие максимальную прибыль.

Функция цели
maxF(x)=c×x

Ограничения
A×x≤b

Численные значения переменных:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Задачи
1.Найти x для обеспечения максимальной прибыли
2. Найти использованные ресурсы при выполнении п.1
3. Найти остатки ресурсов (если они есть) при выполнении п.1

Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.

Используемые при выводе результатов обозначения:
x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
success – True, если функции удалось найти оптимальное решение;
status – статус решения:
0 – поиск оптимального решения завершился успешно;
1 – достигнут лимит на число итераций;
2 – задача не имеет решений;
3 – целевая функция не ограничена.
nit – количество произведенных итераций.

Листинг решения прямой задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # загрузка библиотеки ЛП c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели b_ub = # список объёмов ресурсов A_ub = [, # матрица удельных значений ресурсов , , ] d=linprog(c, A_ub, b_ub) # поиск решения for key,val in d.items(): print(key,val) # вывод решения if key=="x": q=#использованные ресурсы print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов print("b_ub-A_ub*x", q1)

Результаты решения задачи
nit 3
status 0

success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
fun -5863.63636364
slack [ 0. 0. 0. 90.90909091]

Выводы

Найден оптимальный план по видам продукции
Найдено фактическое использование ресурсов
Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack

Решение двойственной задачи о оптимальной производственной программе

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

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

C – вектор имеющихся ресурсов;
b_ub – вектор прибыли от производства единицы изделия каждого вида;
A_ub_T– транспонированная матрица A_ub.

Функция цели
minF(x)=c×x

Ограничения
A_ub_T ×x≥ b_ub

Численные значения и соотношения для переменных:
с = ; A_ub_T transpose(A_ub); b_ub = .

Задача:
Найти x показывающий ценность для производителя каждого вида ресурсов.

Особенности решения с библиотекой scipy. optimize
Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Листинг решения двойственной задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,-40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

Результаты решения задачи
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [ 5.45454545 2.27272727 0. 0. 0. ]
status 0
success True

Выводы

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

Результаты сравнения прямой и двойственной задачи

Двойственная задача расширяет возможности планирования выпуска продукции, но средствами scipy. optimize решается за вдвое большее чем прямая количество итераций.
Переменная slack выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
Прямая задача является задачей максимизации, а двойственная - задачей минимизации, и наоборот.
Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
Знаки неравенств в ограничениях меняются на противоположные.
Матрица системы равенств транспонируется.

Ссылки

Так как есть три единичных вектора, то
можно сразу записать опорный план
Х=(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-го
видов соответственно.