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

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

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

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

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

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

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

,

,

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. Если одна из двойственных задач имеет оптимальное решение, то другая тоже имеет оптимальное решение, причем значения целевых функций для обеих решений совпадают. Если одна из двойственных задач имеет неограниченную целевую функцию, то другая неразрешима, т.е не имеет допустимых решений.

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

.

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

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

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

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

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

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

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

.

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

.

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

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

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

.

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

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

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

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

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

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

Заполняем симплексную таблицу 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 ед.

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

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

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

Пример 1.

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

1. Приводим все неравенства системы ограничений исходной задачи к одному смыслу

2. Составляем расширенную матрицу

3. Транспонируем матрицу

4. Формулируем двойственную задачу

Исходная (прямая) задача

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

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

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

Аналогично для любой пары допустимых решений прямой и двойственной задач неравенство f < z можно интерпретировать следующим образом:

Доход < Общая стоимость ресурсов

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

Большой практический интерес представляет экономическая интерпретация второй теоремы двойственности, а также ее следствия о дополняющей нежесткости.

1. Если суммарная оценка i-го ресурса положительна

то этот ресурс в соответствии с оптимальным планом х* используется полностью

2. Если i-й ресурс используется не полностью

то его оптимальная оценка нулевая и i-е ограничение несущественно.

3. Если в соответствии с оптимальным планом х* j-я продукция производится

то это производство эффективно, так как цена единицы j-й продукции

равна затратам на ее производство в единицах

4. Если производство j-й продукции убыточно (приведенные издержки ненулевые

то в соответствии с оптимальным планом эта продукция не производится

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

Представлены правила составления двойственных задач. Рассмотрены симметричные, несимметричные и смешанные пары. Разобраны примеры составления двойственных задач.

Содержание

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

Симметричная двойственная задача

Рассмотрим задачу линейного программирования с неотрицательными переменными и неравенствами системы ограничений следующего вида:
(1.1) ;
(1.2)
Здесь , , есть некоторые числа. Все строки системы (1.2) являются неравенствами со знаками .


(2.1) ;
(2.2)
Здесь все строки системы (2.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (2.2) является транспонированной матрицей системы (1.2). Она содержит строк и столбцов. Двойственная задача имеет переменных . Все переменные неотрицательные.

Исходную задачу (1) часто называют прямой задачей, а задачу (2) - двойственной. Если за исходную взять задачу (2), то задача (2) будет прямой задачей, а задача (1) - двойственной. Задачи (1) и (2) называются симметричными двойственными задачами .

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

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


;

Исходная задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Первое и третье неравенства содержат знак . Умножим их на -1 :




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

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

;

Несимметричная двойственная задача

Задача на максимум

Рассмотрим каноническую задачу линейного программирования на максимум с неотрицательными переменными и равенствами системы ограничений:
(3.1) ;
(3.2)
Здесь , , есть некоторые числа. Все строки системы (3.2) являются равенствами. Все переменные являются неотрицательными.

Двойственная задача имеет вид:
(4.1) ;
(4.2)
Здесь все строки системы (4.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (4.2) является транспонированной матрицей системы (3.2). Двойственная задача имеет переменных . Переменные могут быть как положительными, так и отрицательными.

Отличие несимметричной пары задач (3) и (4) от симметричной пары (1) и (2) в том, что система ограничений (3.2) содержит только равенства, а в системе (4.2) отсутствуют условия неотрицательности переменных.

Задача на минимум

Теперь рассмотрим каноническую задачу линейного программирования на минимум:
(5.1) ;
(5.2)

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

Система ограничений (6.2) отличается от (4.2) тем, что неравенства имеют знаки .

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

Покажем, что несимметричную пару задач (3)-(4) можно получить из симметричной пары (1)-(2).

Итак, пусть мы имеем прямую задачу с целевой функцией
(3.1)
и системой ограничений
(3.2)
Каждое равенство можно представить двумя неравенствами:

Неравенства со знаками умножим на -1 :

Система ограничений имеет неравенств.

По формулам (1)-(2) получаем двойственную задачу:
;


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

Сделаем подстановки
.
Поскольку и , то переменные могут быть как положительными, так и отрицательными.

И мы получаем двойственную задачу (4):
(4.1) ;
(4.2)

Если мы за исходную задачу возьмем (4), то, выполняя все действия в обратном порядке, получим двойственную задачу (3).

Тем же способом можно из задачи (5) получить двойственную задачу (6) и из задачи (6) получить двойственную задачу (5).

Смешанная задача

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

Пусть мы имеем прямую задачу (1) на максимум, в системе ограничений которой -я строка является равенством. Тогда двойственная задача имеет вид (2) за одним исключением - переменная может быть как положительной, так и отрицательной. То есть отсутствует ограничение .

То же самое произойдет, если мы имеем прямую задачу (2) на минимум, в системе ограничений которой -я строка является равенством. Двойственная задача имеет вид (1) за одним исключением - переменная может быть любого знака.

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

И наконец, пусть мы имеем прямую задачу (2) на минимум, но отсутствует ограничение . Тогда двойственная задача имеет вид (1) за одним исключением - -я строка системы ограничений является равенством.

Все это позволяет нам сформулировать правила составления двойственных задач.

Правила составления двойственных задач

1. Для исходной задачи на максимум, все неравенства системы ограничений приводим к виду:
.
Для исходной задачи на минимум, все неравенства приводим к виду:
.
Если требуется поменять знак, то умножаем обе части неравенств на -1 .
2. Составляем двойственную задачу тем же способом, как для симметричной пары задач.
3. Если в исходной задаче, -я строка системы ограничений является равенством, то вычеркиваем условие неотрицательности -й переменной двойственной задачи.
4. Если в исходной задаче, отсутствует условие неотрицательности для -й переменной, , то в -й строке двойственной задачи меняем знак неравенства на знак равенства.

Пример составления смешанной двойственной задачи

Дана задача линейного программирования:
;

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

Целевая функция имеет свободный член 5. Чтобы привести ее к виду (2.1), введем переменную и добавим равенство . Тогда задача примет вид:

;

Эта задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Третье неравенства содержат знак . Поэтому умножим его на -1 :

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

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

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

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

Поскольку в исходной задаче 1, 2 и 4-я строка системы ограничений являются равенствами, то в двойственной задаче переменные , и могут иметь любой знак. Неотрицательной переменной является только . Поэтому условия неотрицательности переменных имеют вид:
.

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

Таким образом, двойственная задача имеет вид:
;

Из четвертого уравнения . Заменим переменную ее значением и умножим третью строку на -1 .

Следует отметить, что методы решения задач линейного программирования относятся не к экономике, а к математике и вычислительной технике. При этом экономисту нужно обеспечить максимально комфортные условия диалога с соответствующим программным обеспечением. В свою очередь такие условия могут обеспечивать только динамично развивающиеся и интерактивные среды разработки, имеющие в своём арсенале набор необходимых для решения таких задач библиотек. Одной из каких сред разработки программного обеспечения безусловно является 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]

Выводы

  1. Найден оптимальный план по видам продукции
  2. Найдено фактическое использование ресурсов
  3. Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
  4. Нет необходимости в вычислениях по п.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

Выводы

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

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

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