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

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

Всяка задача за линейно програмиране съответства на друга задача, в известен смисъл нейната противоположност. Ако първият проблем се нарича директен, тогава противоположният се нарича двоен. Тъй като двойственият проблем на двойствения проблем е първоначалният директен проблем, няма значение кой проблем се нарича директен и кой двоен. Следователно директните и двойните задачи се наричат ​​задачи с двойна двойка.

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

Има симетрични, асиметрични и смесени двойствени проблеми. При симетрични проблеми ограниченията на директния проблем имат формата . В ограниченията на асиметричния проблем, ограниченията на директния проблем използват знаци за равенство. Смесените задачи използват и двата типа релации по-малко или равно и равно. При асиметрични и смесени задачи изискването за тяхната неотрицателност не се налага на нововъведени променливи.

Изчисленията, базирани на дуалностни отношения, започват с редуциране на преките и двойствените проблеми до стандартна форма. Следователно можем да се ограничим до формулирането на правилата за формиране на задача, която е двойна на стандартната задача за линейно програмиране. Правилата за получаване на двойствения проблем за други типове задачи на LP могат да бъдат получени от тези правила.

Нека напишем проблема с LP в стандартна форма:

,

,

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

Нека наречем този проблем директен. Тогава задачата ще бъде двойна по отношение на него:

,

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

След като анализирахме задачите, можем да направим следните изводи:

1. Всяко ограничение на директния проблем съответства на променлива на двойния проблем.

2. Всяка променлива на директния проблем съответства на ограничение на двойния проблем.

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

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

5. Векторите B и C в директните и дуалните задачи сменят местата си;

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

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

За случай на симетричен двоен проблем:

За случай на асиметричен проблем:

Двойният проблем има формата:

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

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

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

,

Нека формулираме двойна задача за тази задача. Целевата функция на двойния проблем е линейна форма, получена като произведение на вектора b=(10,20,60,80) от вектора на променливите на двойния проблем Y =( ). Освен това, тъй като в директния проблем целевата функция е максимизирана, в двойния проблем тя е минимизирана. Като вземем предвид направените коментари, получаваме

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

И тъй като освен това прекият проблем е проблемът за намиране на максимум, първото ограничение има формата:

Разсъждавайки по подобен начин, получаваме второто ограничение на двойния проблем: . Липсата на променлива в това ограничение се дължи на факта, че във второто ограничение на пряката задача няма променлива.

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

По този начин, въпреки факта, че условието за неотрицателност не е специално наложено върху променливите на двойствения проблем, въпреки това се оказва, че е изпълнено за всички тях.

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

,

,

,

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

Нека напишем тази задача в стандартна форма. За да направите това, нека направим промяна на променливите , нека въведем излишна променлива във второто ограничение и допълнителна променлива в третото. получаваме

,

.

Нека формулираме двоен проблем. Тъй като в директния проблем целевата функция е минимизирана, целевата функция на двойния проблем има формата .

По същата причина първото, второто и третото ограничение на двойния проблем, свързани съответно с променливите се записват, както следва:

,

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

.

Така от трите променливи на двойствената задача една се оказа неограничена по знак.

Използвайки теореми за двойственост, знаейки решението на един от проблемите, можете да намерите оптималното решение на другия, без да го решавате.

Нека разгледаме смесен проблем.

Двойната задача за него ще има формата:

Ако използваме каноничната форма на проблем с линейно програмиране, тогава имаме работа с проблем с асиметрично линейно програмиране.

Каноничната форма на проблема е:

Двойният проблем ще изглежда така:

Теорема 1. За всяка двойка осъществими решения на директния и двойствения проблем, стойността на целевата функция в задачата за максимизиране не превишава стойността на целевата функция в задачата за минимизиране.

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

Теорема 2.Ако един от двойните проблеми има оптимално решение, то другият също има оптимално решение и стойностите на целевите функции за двете решения съвпадат. Ако един от двойствените проблеми има неограничена целева функция, тогава другият е неразрешим, тоест няма възможни решения.

Теорема.За да бъдат допустимите решения оптимални е необходимо и достатъчно те да удовлетворяват системата от уравнения

.

Тази теорема означава, че една от променливите на всеки проблем е строго по-голяма от нула, тогава съответното ограничение в другия двоен проблем е изпълнено като строго равенство и, обратно, ако с оптимално решение всяко ограничение е изпълнено като строго неравенство , тогава съответната променлива в оптималното решение е нула.

ПримерНека решим една симетрична задача. Нека първоначалният проблем има формата

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

Нека създадем двоен проблем за него

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

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

Нека заместим стойностите в ограниченията . получаваме

.

В тази система само първото неравенство е строго. следователно . Ще намерим други стойности на променливите от системата от уравнения

.

В резултат на решаването на тази система от линейни алгебрични уравнения получаваме

Нека решим същата задача, но ако приемем, че решението е известно

Тъй като втората и третата променливи са строго по-големи от нула, съответното ограничение е изпълнено като строго равенство.

.

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

Ако първоначалната задача е решена с помощта на симплексния метод и коефициентите са получени в крайната целева функция - матрица - ред от коефициенти, тогава решението на двойната задача може да се намери с помощта на формулата където е матрицата на коефициентите за основните променливи на целевата функция в оптималното решение на първоначалната задача.

Нека разгледаме икономическата интерпретация на двойствения проблем.

Теорема.Стойностите на променливите в оптималното решение на двойния проблем представляват оценки на влиянието на свободните членове на ограниченията на първоначалния проблем върху оптималната стойност на неговата целева функция. защото

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

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

Попълваме симплексната таблица на 0-та итерация.

BP Симплекс
връзка		 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.

Сега започваме да компилираме първата итерация. Вместо единичен вектор въвеждаме вектора .

IN нова масана мястото на разрешаващия елемент пишем 1, всички останали елементи на ключовата колона са нули. Ключовите низови елементи са разделени на активиращия елемент. Всички останали елементи на таблицата се изчисляват по правилото на правоъгълника.

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

BP Симплекс
връзка		 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-ра итерация:

BP Симплекс
връзка		 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. Формулирайте двойствената задача

Оригинален (директен) проблем

Двоен проблем

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

променлива при аздвойният проблем представлява цената на единица ресурс аз. В литературата за изследване на операциите, променливи при аздвойственият проблем често се нарича двойни цени . Освен това понякога се наричат сенчести цени И симплексни множители .

По същия начин, за всяка двойка допустими решения на директните и двойните задачи, неравенството f < zможе да се тълкува по следния начин:

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

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

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

1. Ако общата оценка на i-тия ресурс е положителна

тогава този ресурс се използва напълно в съответствие с оптималния план x*

2. Ако i-ти ресурсне е използван напълно

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

3. Ако в съответствие с оптималния план x* j-ти продуктипроизведени

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

равна на себестойността на производството му в единици

4. Ако производството j-ти продуктинерентабилни (намалените разходи са ненулеви

тогава, в съответствие с оптималния план, този продукт не се произвежда

По този начин двойните оценки са свързани с оптималния дизайн на директния проблем. Всяка промяна в изходните данни на директен проблем засяга неговия оптимален план и системата от двойни оценки. От своя страна двойните оценки служат като инструмент за анализ и вземане на правилни решения при променящи се търговски ситуации.

Представени са правила за съставяне на двойни задачи. Разглеждат се симетрични, асиметрични и смесени двойки. Анализират се примери за съставяне на двойни задачи.

Съдържание

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

Симетричен двоен проблем

Разгледайте задача на линейно програмиране с неотрицателни променливи и неравенства на система от ограничения от следната форма:
(1.1) ;
(1.2)
Тук има някои числа. Всички редове на системата (1.2) са неравенства със знак.


(2.1) ;
(2.2)
Тук всички редове на системата (2.2) са неравенства със знак.

Първоначалният проблем (1) често се нарича директен проблем, а проблем (2) се нарича двоен проблем. Ако приемем задача (2) за начална, тогава задача (2) ще бъде пряка задача, а задача (1) ще бъде двойна. Проблеми (1) и (2) се наричат ​​симетрични двойствени проблеми.

По този начин симетричен двоен проблем може да бъде съставен само ако всички променливи на първоначалния проблем са неотрицателни и системата от ограничения не съдържа равенства. Ако се търси максимумът на целевата функция, тогава неравенствата трябва да бъдат преобразувани във формата . -1 .

Ако се търси минимум, тогава неравенствата трябва да се преобразуват във вида .


;

За да промените знака, трябва да умножите двете страни на неравенството по -1 :




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

Двойният проблем има формата:
;

;

Първоначалната задача е задача за намиране на минимума. Следователно всички неравенства трябва да имат знаци.

Първото и третото неравенство съдържат знака.

Нека ги умножим по
(3.1) ;
(3.2)
Нека транспонираме тази матрица. Тоест, ще напишем първия ред като първа колона, ще напишем втория ред като втора колона и ще напишем третия ред като трета колона.

Двойният проблем има формата:
(4.1) ;
(4.2)
Асиметричен двоен проблем

Максимално предизвикателство

Разгледайте каноничния проблем за максимално линейно програмиране с неотрицателни променливи и равенства на системата от ограничения:

Тук има някои числа. Всички редове на системата (3.2) са равенства. Всички променливи са неотрицателни.
(5.1) ;
(5.2)

Двойният проблем има формата:
(6.1) ;
(6.2)

Тук всички редове на системата (4.2) са неравенства със знак.

Матрицата на коефициента на ограничителната система (4.2) е транспонираната матрица на системата (3.2). Двойният проблем има променливи.

Променливите могат да бъдат положителни или отрицателни.

Разликата между асиметричната двойка задачи (3) и (4) от симетричната двойка (1) и (2) е, че системата от ограничения (3.2) съдържа само равенства, а в системата (4.2) няма условия за неотрицателността на променливите.
(3.1)
Минимална задача
(3.2)
Сега разгледайте проблема с каноничното минимално линейно програмиране:

Системата от ограничения (6.2) се различава от (4.2) по това, че неравенствата имат знаци. -1 :

Връзка със симетрична двойка двойствени задачи

Нека покажем, че асиметрична двойка задачи (3)-(4) може да се получи от симетрична двойка (1)-(2).
;


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

Да направим смени
.
Тъй като и , променливите могат да бъдат положителни или отрицателни.

И получаваме двойния проблем (4):
(4.1) ;
(4.2)

Ако приемем (4) за първоначална задача, тогава, изпълнявайки всички действия в обратен ред, получаваме двойствената задача (3).

Използвайки същия метод, може да се получи двойна задача (6) от задача (5) и двойна задача (5) от задача (6).

Смесен проблем

Сега нека разгледаме смесен проблем.

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

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

Сега нека имаме пряка задача (1) за максимум, но няма ограничение.

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

Тогава двойствената задача има вида (1) с едно изключение - рият ред на системата от ограничения е равенство.

Всичко това ни позволява да формулираме правила за съставяне на двойни задачи.

1. Правила за съставяне на двойни задачи
.
За първоначалния максимален проблем редуцираме всички неравенства на системата от ограничения до формата:
.
За първоначалния минимален проблем редуцираме всички неравенства до формата: -1 .
2. Ако трябва да промените знака, тогава умножете двете страни на неравенствата по
3. Съставяме двойна задача по същия начин, както за симетрична двойка задачи.
4. Ако в първоначалната задача редът от системата от ограничения е равенство, тогава зачеркваме условието за неотрицателност на променливата от двойствения проблем.

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

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

Като се има предвид проблем с линейно програмиране:

Създайте двоен проблем.

;

Този проблем е проблем за намиране на минимума. Следователно всички неравенства трябва да имат знаци. -1 :

Третото неравенство съдържа знака.

Затова нека го умножим по

Нека пренапишем системата от ограничения, като изрично посочим коефициентите на променливите:

Матрицата на коефициента на ограничителната система има формата:
;

Нека транспонираме тази матрица. Тоест, ще напишем първия ред като първа колона, ще напишем втория ред като втора колона и т.н.
.

Нека създадем двойна задача като за симетрична двойка.

Тъй като в първоначалната задача 1-ви, 2-ри и 4-ти ред на системата от ограничения са равенства, то в двойствената задача променливите , и могат да имат произволен знак. Единствената неотрицателна променлива е .
;

Следователно условията за неотрицателност на променливите имат формата: -1 .

Тъй като в първоначалната задача променливите и могат да имат произволни знаци, 3-ти и 4-ти ред на системата от ограничения на двойствената задача са равенства. Така двойственият проблем има формата:От четвъртото уравнение. Заменете променливата с нейната стойност и умножете третия ред поТрябва да се отбележи, че методите за решаване на проблеми с линейно програмиране включват

не към икономиката, а към математиката и компютърните технологии.

В същото време икономистът трябва да осигури най-удобните условия за диалог с подходящия софтуер. От своя страна, такива условия могат да бъдат осигурени само от динамично развиващи се и интерактивни среди за разработка, които имат в своя арсенал набор от библиотеки, необходими за решаване на подобни проблеми. Една от които среди за разработка

софтуер

определено е Python.

Оптималните стойности на разходите за материали и труд ще бъдат оценени според техния принос към целевата функция. Резултатът ще бъде „обективно определени оценки“ на суровини и труд, които не съвпадат с пазарните цени.

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

като се има предвид високо ниво математическа подготовкаЗа огромното мнозинство от потребителите на този ресурс няма да представя балансови уравнения с горни и долни ограничения и въвеждане на допълнителни променливи за преминаване към равенства. Затова веднага ще дам обозначенията на променливите, използвани в решението:
N – брой видове произведени продукти;
m – брой видове използвани суровини;
b_ub - вектор на наличните ресурси с размерност m;
A_ub е матрица с размерност m×N, всеки елемент от която е потреблението на ресурс от тип i за производството на единица продукт от тип j;
c е векторът на печалбата от производството на единица от всеки вид продукт;
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] и игнорирайте знака минус пред печалбата.

Обозначения, използвани за показване на резултатите:
х– масив от променливи стойности, които осигуряват минимума (максимума) на целевата функция;
отпуснатост– стойности на допълнителни променливи. Всяка променлива съответства на ограничение за неравенство. Стойност на променлива нула означава, че съответното ограничение е активно;
успех– Вярно, ако функцията е успяла да намери оптималното решение;
състояние– състояние на решението:
0 – търсенето на оптималното решение приключи успешно;
1 – достигнато е ограничението за брой итерации;
2 – проблемът няма решения;
3 – целевата функция не е ограничена.
гнида– брой извършени итерации.

Изброяване на решението на задачата за директна оптимизация

#!/usr/bin/python # -*- кодиране: utf-8 -*- import scipy от scipy.optimize import linprog # зареждане на LP библиотека c = [-25, -35,-25,-40,-30] # списък с коефициенти на целевата функция b_ub = # списък с обеми на ресурси A_ub = [, # матрица на специфични стойности на ресурса ​​, , ] d=linprog(c, A_ub, b_ub) # търсене на решение за key,val в 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)


Резултати от решаването на проблема
гнида 3
състояние 0

успех Вярно
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
забавно -5863.63636364
отпуснатост [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

Числени стойности и връзки за променливи:
c = ; A_ub_T транспониране (A_ub); b_ub = .

Задача:
Намерете x, показващ стойността за производителя на всеки тип ресурс.

Характеристики на решението с библиотеката scipy. оптимизиране
За да замените ограниченията отгоре с ограниченията отдолу, е необходимо да умножите двете части на ограничението по минус едно – A_ub_T ×x≥ b_ub... За целта запишете оригиналните данни във формата: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Изброяване на решението на проблема с двойната оптимизация

#!/usr/bin/python # -*- кодиране: utf-8 -*- import scipy от 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) за ключ,вал в d.items(): печат(ключ,вал)


Резултати от решаването на проблема
гнида 7
съобщение Оптимизацията е прекратена успешно.
забавно 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
отпуснатост [5.45454545 2.27272727 0. 0. 0. ]
състояние 0
успех Вярно

Изводи

Следователно третият вид ресурс има най-голяма стойност за производителя този типресурсите трябва да бъдат закупени първо, след това първият и вторият тип. Четвъртият вид ресурс има нулева стойност за производителя и се купува последен.

Резултати от сравнение на преки и двойни задачи

  1. Двойният проблем разширява възможностите за продуктово планиране, но с помощта на scipy. optimize се решава с два пъти повече директни итерации.
  2. Променливата slack показва информация за активността на ограниченията под формата на неравенства, които могат да се използват например за анализ на баланси на суровини.
  3. Директният проблем е проблем за максимизиране, а двойният проблем е проблем за минимизиране и обратно.
  4. Коефициентите на целевата функция в директния проблем са ограничения в двойния проблем.
  5. Ограниченията в директната задача стават коефициенти на целевата функция в двойствената.
  6. Знаците на неравенствата в ограниченията са обърнати.
  7. Транспонира се матрицата на системата от равенства.
Връзки