Табличен изглед на ПЧП. Симплекс - таблици.

ПРОСТ МЕТОД ЗА РЕШАВАНЕ НА ЗЛП

3.1. основни характеристикии основните етапи на симплексния метод

Основателите на симплексния метод са съветският математик Л.В. Канторович и американския математик Дж. Данциг.

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

Нека опишем Главна идеясимплексен метод.

Вярваме, че ZLP е написан в канонична форма и целевата функция трябва да бъде сведена до минимум. Както вече знаем, оптимален плантрябва да се търси сред опорните планове на ЗЛП. Симплексният метод не преминава през всички референтни планове (което често би било невъзможно поради огромния им брой), а като се започне от някои начални референтен план, той последователно преминава към други референтни планове с намаление целева функция. Симплексният метод спира да работи, когато се намери оптималният референтен план или се установи неразрешимостта на проблема.

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

1) привеждане на PAP до канонична форма;

2) привеждане на системата линейни уравнениякъм форма на Йордан с неотрицателни десни части с едновременна проверка за неразрешимост на ZLP поради несъгласуваност на системата от линейни ограничения;

3) изследване на опорния план за оптималност;

4) изследване на ЗЛП за неразрешимост поради неограниченост отдолу върху ОПД на целевата функция;

5) преход към нов, „по-добър” референтен план.

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

Нека ЗЛП е написана в канонична форма (2.3-2.5). За привеждане на PAPsВ таблична форма системата (2.4) трябва първо да бъде редуцирана до Йорданова форма с неотрицателни десни части. Да приемем, че тази Йорданова форма има формата (2.6). Нека изразим от (2.6) основните променливи по отношение на свободните:

Като заместваме в целевата функция (2.3) вместо основните променливи техните изрази чрез свободни променливи съгласно формули (3.1), по този начин изключваме основните променливи от целевата функция. Целевата функция ще приеме формата:

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

Където .

Нека отбележим следните характеристики на табличната форма на ПЧП:

а) системата от линейни уравнения се редуцира до жорданова форма с неотрицателни десни части;

б) базисните променливи се изключват от целевата функция и тя се записва във формата (3.3).

Нека сега да преминем към описанието на симплексната таблица. Нека ZLP бъде написано в таблична форма:

(3.4)

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

Таблица 3.1.

Основа	Променливи	Безплатни членове
			...	x k			...
			...				...
			...				...
. . .	. .	. .	...	. .	. .	. .	...	. .	. . .
			...				...
f			...				....

Основен план на ЗОП: ..., се нарича референтен план, съответстващ на тази симплексна таблица. Както може да се види от формула (3.2), стойността на целевата функция за този референтен план е равна на γ ​​0.

Нека разгледаме един пример. Намалете следния ZLP до таблична форма и попълнете симплексната таблица:

Първо, ЗЛП трябва да бъде приведена в канонична форма. За да направите това, функцията f трябва да се замени с - f:

Системата от уравнения трябва да бъде написана в Йорданова форма с неотрицателни десни части. Общ приемсредствата, чрез които се постига това, ще бъдат обсъдени по-късно (раздел 3.7). В нашия пример такава Йорданова форма вече съществува с базовите променливи и . Нека изключим основните променливи от целевата функция - f. За да направим това, ние ги изразяваме чрез свободни изрази и заместваме тези изрази в целевата функция.

Табличният изглед на ZLP е както следва:

Нека попълним симплексната таблица (за да съкратим записите, първата колона е озаглавена „B“, последната колона е „Q“).

Таблица 3.2.

б					Q
			-5
	-7		-2
-f	-4				-20

Референтният план, съответстващ на тази симплексна таблица, има формата:

Стойността на функцията - f с този референтен план е - 20.

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

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

За простота ще обосновем валидността на това твърдение с пример. Нека попълнената симплексна таблица изглежда така:

Таблица 3.3.

б						Q
				-1
					-1
f			-5	-3	-1

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

3.4. Условието за неразрешимост на ZLP поради неограниченост отдолу върху ODD на целевата функция.

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

Условието за неразрешимост се формулира по следния начин.

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

За да оправдаем това, отново ще използваме пример.

Таблица 3.4.

б						Q
					-2
			-3		-1
f				-1

Колоната в долния ред съдържа положително число, а останалите редове съдържат неположителни числа. Нека докажем неразрешимостта на ЗЛП.

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

Нека a е произволно положително число. Очевидно ZLP има следното осъществимо решение:. Нека изчислим стойността на целевата функция за това възможно решение. От таблица 3.4 имаме:

. При посоченото допустимо решение f = 4 - 2a. От това виждаме, че стойността на целевата функция може да стане толкова малка, колкото желаете, за достатъчно голямо значениеА. С други думи, целевата функция не е ограничена отдолу на ODE. Следователно ЗЛП е нерешим.

3.5. Преход към нов референтен план.

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

1) новото основание все още трябва да е допустимо, т.е. десните страни на съответната Йорданова форма все още трябва да са неотрицателни;

2) при нов референтен план стойността на целевата функция не трябва да надвишава стойността си с предишния референтен план.

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

Правило за избор на общ елемент.

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

Нека илюстрираме това правило с пример.

Таблица 3.5.

б						Q
				2	-1
				-2
Е

Можете да изберете колона или колона като обща колона. Да изберем (най-често се избира колоната с най-голямо положително число отдолу). Сега нека започнем да избираме общата линия. За да направите това, помислете за два реда - и . Правим съотношения 4:2 и 8:3. Съотношението 4:2 има по-малка стойност, затова избираме първия ред като общ. Следователно общият елемент е 2 - той стои в пресечната точка на колона и ред.

След като изберете общия елемент, трябва да преминете към нов справочен план, в който променливата става основна, а променливата x 1 става свободна. Коефициентът за в новата форма на Йордания трябва да бъде равен на 1. Следователно първият ред на таблица 3.5 се разделя на 2. След това полученият първи ред се умножава по (-3) и се добавя към втория ред , изключете от второто уравнение. По същия начин, използвайки процедурата на Йордан, ние го изключваме от третото уравнение и от целевата функция (последната изисква таблична форма на ZLP).

В резултат на това получаваме следната таблица.

Таблица 3.6

б						Q
f						-2

Моля, обърнете внимание, че в колона Q първите три реда съдържат неотрицателни числа, т.е. новата основа все още е валидна. Това не е случаен факт: винаги ще е така, ако стриктно се спазва правилото за избор на генерална линия. Освен това стойността на целевата функция с новия референтен план е равна на -2, със стария беше равна на 12. „Подобряването“ на референтния план гарантира правилото за избор на обща колона. Въпреки че не доказваме стриктно тези факти, трябва да се има предвид, че те винаги се случват.

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

3.6. Табличен симплекс алгоритъм.

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

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

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

3. Изберете всяка колона, различна от най-дясната, която има положително число в долния ред - нека я наречем обща. След това разглеждаме редовете на симплексната таблица, различни от долния, които имат положителни числа в общата колона. За всеки от тези редове изчисляваме отношението на свободния член към елемента в общата колона. Редът, за който тази връзка е минимална, е генералният ред. Елементът в пресечната точка на общата колона и общия ред ще бъде общият елемент. Отидете на точка 4.

4. Създаваме нова симплексна таблица, в която:

1) променливата в общата линия се извлича от основата; променлива в общата колона се въвежда в основата;

2) общата линия е разделена на общ елемент;

3) с помощта на процедурата на Йордан се правят всички числа от общата колона, с изключение на 1, която е в общия ред равно на нула. Отидете на точка 1.

Пример IРешете с помощта на симплексния метод

Проблемът е написан в канонична форма, трябва да го приведете в табличен вид. Системата от уравнения е написана в Йорданова форма с неотрицателни десни части (основни променливи и ). Необходимо е целевата функция да се сведе до таблична форма. За да направим това, ние изразяваме основните променливи чрез свободни

x 3 =10 - 2x 1 - x 2

x 4 = 8 - x 1 - 2x 2

и го заместете в целевата функция

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

Сега имаме табличен изглед на ZLP:

Нека попълним първата симплексна таблица

Таблица 3.7

б					Q
Е

В таблица 3.7 условията за оптималност и неразрешимост не са изпълнени. Нека изберем като обща колона , която има положително число в долния ред. След това, сравнявайки съотношенията 10:3 и 8:1, избираме първия ред като общ. В таблицата общият елемент е 2.

Действайки в съответствие с точка 4 от табличния симплекс алгоритъм, нека преминем към таблица 3.8.

Таблица 3.8

б					Q
Е			-5		-22

Условията за оптималност и неразрешимост не са изпълнени. Изберете общия елемент в таблица 3.8 и преминете към следващата таблица

Таблица 3.9

б					Q
Е					-24

Таблица 3.9 удовлетворява условието за оптималност.

Отговор: оптимален план

Минималната стойност на целевата функция f min = - 24.

Пример 2. Решете с помощта на симплексния метод:

На първо място, ЗЛП трябва да се доведе до каноничен вид

Сега привеждаме ZLP в таблична форма. Виждаме, че системата от уравнения е написана в Йорданова форма с неотрицателни десни части (и z-основни променливи). Обаче целевата функция включва базисна променлива. Ние имаме:

Следователно табличният изглед на ZLP е както следва:

Попълнете симплексната таблица (Таблица 3.10).

Таблица 3.10

б				z	Q
	-1
z		-2
ж					-1

След като изберете общия елемент, преминете към таблица 3.11

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

Симплексният метод е аналитичен метод ZLP решения, прилагащи алгоритъма графичен методаналитично, без чертеж.

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

Симплексният метод може да се използва за решаване на PLP с произволен брой неизвестни.

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

Симплексен метод с естествена основа се прилага, ако ZLP е даден в канонична нотационна форма и матрицата в QLP съдържа единична подматрица с размер м´м. За категоричност нека приемем, че първото мВекторните матрици на системата от уравнения образуват единичната матрица. Тогава първоначалният план се избира, както следва:

Оптималността на референтния план се проверява с помощта на знака за оптималност; преходът към друг план се извършва с помощта на трансформацията на Йордан-Гаус с помощта на математическия знак за оптималност. Полученият опорен план отново се проверява за оптималност и т.н.

Математическият критерий за оптималност се състои от следните две теореми:

1. Ако за всички вектори A 1 , A 2 , … , A nусловието е изпълнено където , тогава полученият референтен план е оптимален. Общо за определяне Z jучаствам м термини, тоест не всички коефициенти на целевата функция участват в него c j, но само с числа, съответстващи на номерата на текущите базисни вектори A i, чийто брой е равен м .

2. Ако за някакъв вектор, който не е включен в базиса, условието е изпълнено , тогава трябва да потърсите нов референтен план, за който CF стойността е по-голяма от тази за текущия. В този случай са възможни два случая:

а) ако всички компоненти на вектора A k, които трябва да бъдат въведени в основата, са неположителни, тогава LLP няма решение (няма краен оптимум);

б) ако векторът има поне една положителна компонента A k, да се въведе в основата, след което може да се получи нов опорен план.

Въз основа на критерия за оптималност в основата се въвежда вектор A k, което дава минималната отрицателна стойност на симплексната разлика:

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

Линия A r, в която се намираше старият базисен вектор, се нарича водеща колона A kи елемент a rk- водачи.

Елементите на водещата линия в новата симплексна таблица се изчисляват по формулите:

и всякакви други елементи азред - по формулите:

Стойностите на новия референтен план се изчисляват по подобни формули:

,

Процесът продължава или докато се получи оптимален план, или докато TF е неограничен. Ако сред разликите Δ j , j=1, 2, … , nна оптималния план, само разликите, съответстващи на базисните вектори, са нула, това показва уникалността на оптималния план. Ако нулевата оценка съответства на вектор, който не е включен в основата, то в общия случай това означава, че оптималният план не е единствен.

Пример.Решете ZLP с помощта на модела:

намирам ,

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

Този ZLP се редуцира до канонична форма чрез въвеждане на допълнителни променливи х 3И х 4:

KZLP има необходимия брой (две) нулеви колони при х 3И х 4, тоест има очевиден първоначален референтен план (0,0,300,150).

Решението се извършва по симплексния метод с естествена основа с изчисленията, форматирани в симплексни таблици:

Номер на симплексна таблица	Основа	с j	с j					Q
б	A 1	А 2	A 3	A 4
	←A 3
A 4
Δ	-		-2	-3			-
аз	→А 2			1/3		1/3
←A 4			2/3		-1/3
Δ	-		-1				-
II	А 2					1/2	-1/2	-
→A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Нека се спрем по-подробно на попълването на симплексни таблици и съответно получаването на решение на KZLP.

IN горен ред обща масадобавени коефициенти c j, j=1, 2, 3, 4с променливи в цифровата функция. Първите два реда на нулевата симплексна таблица съдържат колонни вектори B, A 1, A 2, A 3, A 4, съответстващ векторна форма KZLP записи. Тъй като началната основа е двойка вектори А 3, А 4, те са включени в колоната, наречена „Основа“ на нулевата симплексна таблица. при което, A 3е включен в първия ред, който се определя от единицата, която е първият елемент на този вектор, и вектора A 4- към втория ред, за този вектор единицата е във втория ред. В колоната, наречена „ c i” са въведени коефициентите на целевата функция, съответстващи на базисните вектори А 3, А 4, това е c 3, c 4. И двете са равни на нула. След това се изчисляват стойностите на разликите Δ за векторите B, A 1, A 2, A 3, A 4и се вписват в третия ред на нулевата таблица. За вектор A 1:

за вектор:

По същия начин,.

За вектор бизчисляването на разликата е донякъде опростено, тъй като няма съответен коефициент c j, j=1, 2, 3, 4в CF:

Не за всички вектори A 1, A 2, A 3, A 4получените разлики са неотрицателни, така че референтният план, който сме избрали, не е оптимален. Трябва да потърсим нов референтен план и за това трябва да заменим един от векторите, включени в основата А 3, А 4.

За да определим вектора, който трябва да въведем, търсим вектора, за който стойността на разликата е минимална. Това е векторът А 2, съответства на минималната стойност на разликата: -3. Тоест индексът кот формула (8.4) е равно на 2. За да определим вектора, който ще трябва да изведем от основата, изчисляваме стойностите Qза всеки ред по формула (8.5) и ги въведете в последната колона. IN в такъв случайвъв всеки ред се нуждаем от стойността на векторния елемент бразделете на големината на векторния елемент А 2. В първия ред получаваме 300/3=100, във втория: 150/1=150. Съотношението в първия ред беше по-малко; базисният вектор съответстваше на него A 3, следователно, индексът rвъв формула (8.5) е равно на 1, a rk=3 (маркирано в таблицата с рамка), а вектора ще изведем от основата A 3(обозначено със стрелка в таблицата).

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

След това се попълва втората симплексна таблица. За преизчисляване на векторни елементи B, A 1, A 2, A 3, A 4се използват формули (8.6)-(8.8). Те са малко по-различни за определяне на елементите на водещата линия (в нашия случай първата) и за определяне на елементите на други линии. Нека запишем изчисленията на няколко елемента:

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

Както виждаме, в резултат на изчисленията във втората симплексна таблица с базисни вектори А 2, А 1всички разлики се оказаха неотрицателни, което означава постигане на оптималния план (75; 75; 0; 0). Симплексна разлика за вектор INравна на желаната максимална CF стойност - 375.

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

За да се приложи симплексният метод с естествена основа, KZLP трябва да съдържа единична подматрица с размер mxm - в този случай първоначалният план за поддръжка (неотрицателно основно решение на системата от ограничения на KZLP) е очевиден.
За да бъдем конкретни, приемаме, че първите m вектора от матрицата на системата от уравнения съставляват единичната матрица. Тогава началният референтен план е очевиден - (b 1, b 2,..., b m,0,...,0).
Оптималността на референтния план се проверява с помощта на критерия за оптималност; преходът към друг референтен план се извършва с помощта на трансформациите на Йордан-Гаус с помощта на математическия критерий за оптималност. Полученият референтен план отново се проверява за оптималност и т.н. Процесът завършва в краен брой стъпки и при последна стъпкаили се разкрива неразрешимостта на проблема (няма краен оптимум), или се получава оптимален референтен план и съответната оптимална стойност на CF.
Математическият критерий за оптималност се състои от следните две теореми:
1. Ако за всички вектори A 1, A 2,…, A n условието е изпълнено
Където ,
тогава полученият референтен план е оптимален.
2. Ако за някакъв вектор, който не е включен в базиса, условието е изпълнено , тогава можете да получите нов референтен план, за който стойността на CF ще бъде по-голяма от оригиналната и може да има два случая:
- ако всички компоненти на вектора, който трябва да се въведе в основата, са неположителни, тогава LLP няма решение (няма краен оптимум);
- ако има поне един положителен компонент на вектора, който трябва да бъде въведен в основата, тогава може да се получи нов референтен план.
Въз основа на критерия за оптималност вектор A k се въвежда в основата, което дава минималната отрицателна стойност на симплексната разлика:
За да бъде изпълнено условието за неотрицателност на стойностите на референтния план, векторът A r се извлича от основата, което дава минималното положително съотношение на оценка

Ред A r се нарича водач, колона A k и елемент a r k се наричат ​​водачи.
Елементите на водещата линия в новата симплексна таблица се изчисляват по формулите:
А i-ти елементилинии - по формулите:
Стойностите на новия референтен план се изчисляват по формулите:
за i = r;
Процесът на вземане на решение продължава или докато се получи оптимален план, или докато TF бъде установен като неограничен. Ако сред симплексните разлики (оценки) на оптималния план само оценките, съответстващи на базисните вектори, са нула, то това показва уникалността на оптималния план. Ако нулева оценка съответства на вектор, който не е включен, тогава в общия случай това означава, че оптималният план не е уникален.
Забележка. Да се ​​използва дадената процедура за минимизиране линейна функция f (x 1 ,x 2 ,…, x n) трябва да търсите максимума - f (x 1 ,x 2 ,…, x n), след което вземете получения максимум с обратен знак. Оптималното решение е същото.
Пример.Вземете решение въз основа на модела:
Този проблем (модел) на линейното програмиране, нека го доведем до канонична форма чрез въвеждане на допълнителни променливи x 3 и x4:
KZLP има необходимия брой единични колони, т.е. има очевиден първоначален референтен план (0,0,300,150). Решението се извършва по симплексния метод с естествена основа и изчисленията са представени в симплексни таблици:

й. Оптимални стойностипроменливите са равни: x1*=75, x2* =75 (основни променливи), x3* =0, x4* =0 (допълнителни променливи). Максимална стойностцелевата функция е 375.
По този начин в проблема, разгледан по-горе оптимално използванеограничени ресурси, оптимални производствена програмасе състои от издание от 75 единици. продукти от първи вид и 75 бр. продукти от втори тип. Тази програма е свързана с максимални приходи от продажбата на готови продукти - 375 USD.

Номер			IN	2	3	0	0
симплекс-	Основа		план					Q
маси
	A3	0	300	1	3	1	0	100
0	A4	0	150	1	1	0	1	150
		f(x)	0	-2	-3	0	0
	A2	3	100	1/3	1	1/3	0	300
аз	A4	0	50	2/3

Симплексен метод. Алгоритъм. Знак за оптималност на опорния план.

От геометричната интерпретация на ZLP става ясно, че максимумът или минимумът на функцията се постига в ъгловата точка на изпъкнал полиедър - ODP - система от ограничения. Следователно симплексният метод се основава на идеята за разглеждане и тестване за оптималност само на ъгловите точки - върховете на полиедъра, а не на целия безкраен набор от неговите точки.

Ориз. Геометрична интерпретация на идеята за симплексния метод

в случай на две (Фигура a) и три (Фигура b) променливи.

Симплексе изпъкнал многоъгълник в n-мерно пространство с n+1 върха, които не лежат в една и съща хиперравнина (хиперравнината разделя пространството на 2 полупространства).

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

Основно решение– това е едно от приемливите решения, намерени в ОРС.

Наричат ​​се променливи, за които се решава система от линейни уравнения основен. След това се извикват всички останали променливи Безплатно.

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

Алгоритъм на симплексния метод:

1. Изградете математически моделзадачи.

1. Преобразувайте получения математически модел в канонична форма, в която: десните части на условията са неотрицателни; условията са равенства (ако е необходимо, въведете изкуствени променливи).
2. Постройте симплексна таблица и намерете първоначалния справочен план за решаване на задачата. Много променливи, които са основен, се приемат като първоначално основно решение. Стойностите на тези променливи са равни на свободните условия. Всички други променливи са нула.
3. Проверката на основното решение за оптималност се извършва с помощта на специални оценки на коефициентите на целевата функция (вж. последен редтаблици). Ако проблемът е решен при max, тогава всички оценки трябва да са неотрицателни, ако при min, тогава всички оценки трябва да са неположителни.
4. Преход към ново основно решение. Очевидно оптималният план трябва да включва променлива, която ще увеличи в най-голяма степен целевата функция. При решаване на максимални проблеми оптималният план включва продукти, чието производство е най-рентабилно. Това се определя от максималната положителна стойност на оценката на коефициентите на целевата функция. Колоната на таблицата, която съдържа тази оценка, се нарича главна колона. Ако поне един елемент от колоната е положителен, тогава се намира общият ред (в противен случай задачата няма оптимално решение). Ако в тази колона има нули, тогава трябва да вземете друга колона. За да намерите общия ред, всички безплатни членове (ресурси) се разделят на съответните елементи на общата колона (разход на ресурс за единица продукт). От получените резултати се избира най-малкият, а съответният ред се нарича общ ред. Той съответства на ресурс, който ограничава производството до тази стъпка. Елемент на симплексна таблица, разположен в пресечната точка на общ ред и колона, се нарича общ елемент. Всички елементи на общия низ, включително свободния член, са разделени на общия елемент. В резултат на това общият елемент става равен на 1. След това е необходимо всички други елементи на общата колона да станат равни на 0. Общата колона трябва да стане единица. Всички редове с изключение на общия се преобразуват, както следва: получени елементи нова линияумножете по съответните елементи на общата колона и извадете получения продукт от елементите на стария ред. Стойността на новите базови променливи ще бъде получена в съответните клетки на колоната със свободни членове (правило на правоъгълниците).
5. Полученото основно решение се проверява за оптималност (стъпка No4). Ако е оптимално, тогава изчисленията спират, в противен случай се намира ново основно решение (стъпка № 5).

Знак за оптималност на опорния план

Ако решим задача за max, тогава всички оценки трябва да са неотрицателни.

Ако решим задача за min, тогава всички оценки трябва да са неположителни.

Ако референтният план не е оптимален, трябва да преминете към по-добър референтен план. За да направим това, избираме най-лошата оценка. Тя ще съответства на колоната за резолюция. След това трябва да намерите активиращия ред.

Θ (колона от симплексни отношения) не се чертае за линии с отрицателни и нулеви стойности. От всички θ избираме най-малкото; това се прави винаги, независимо дали първоначалният проблем е min или max.

Разрешаващата линия винаги показва кой елемент трябва да бъде премахнат от основата, а разделителната колона винаги показва кой елемент трябва да бъде въведен в основата.