Ако постановката на проблема съдържа ограничения със знака ≥, тогава те могат да бъдат редуцирани до формата ∑a ji b j чрез умножаване на двете страни на неравенството по -1. Нека въведем m допълнителни променливи x n+j ≥0(j =1,m) и преобразуваме ограниченията във формата на равенства

(2)

Да приемем, че всички начални променливи на задачата x 1 , x 2 ,..., x n са небазисни. Тогава допълнителните променливи ще бъдат основни и определено решение на системата от ограничения има формата

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)

Тъй като в този случай стойността на целевата функция F 0 = 0, можем да представим F(x) както следва:

F(x)=∑c i x i +F 0 =0 (4)

Първоначалната симплексна таблица (симплексна таблица 1) се съставя въз основа на уравнения (2) и (4). Ако допълнителните променливи x n+j са предшествани от знак „+“, както в (2), тогава всички коефициенти пред променливите x i и свободният член b j се въвеждат в симплексната таблица без промени. При максимизиране на целевата функция коефициентите се въвеждат в долния ред на симплексната таблица с противоположни знаци. Свободните членове в симплексната таблица определят решението на задачата.

Алгоритъмът за решаване на проблема е следният:

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

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

Маса 1.

x n

основни променливи	Безплатни членове при ограничения	Неосновни променливи
		х 1	х 2	...	х л	...
x n+1	b 1	а 11	а 12	...	1л	...	a 1n
x n+2	б 2	а 21	а 22	...	2л	...	a 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+r	б2	a r1	a r2	...	a rl	...	арн
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+m	b m	a m1	м2	...	мл	...	мн
F(x)макс	F 0	-c 1	-c 2	...	-c 1	...	-c n

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

В същото време променливата, която първа променя знака, когато избраният NP x l се увеличи, се изключва от BP. Това ще бъде x n+r, чийто индекс r се определя от условието

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

Извиква се редът, съответстващ на променливата x n+r водещи или позволяващи. Елементът на симплексната таблица a rl, разположен в пресечната точка на водещия ред и водещата колона, се нарича водещ или разрешаващ елемент.Намирането на водещия елемент завършва работата с всяка обикновена симплексна таблица.

3-та стъпка. Изчислява се нова симплексна таблица, чиито елементи се преизчисляват от елементите на симплексната таблица от предходната стъпка и се отбелязват със штрих, т.е. b" j, a" ji, c" i, F" 0. Елементите се преизчисляват по следните формули:

Първо, новата симплексна таблица ще попълни реда и колоната, които са били водещи в предишната симплексна таблица. Израз (5) означава, че елементът a" rl на водеща позиция е равен на реципроченелемент от предишната симплексна таблица. Елементите на реда a ri се разделят на водещия елемент, а елементите на колоната a jl също се разделят на водещия елемент, но се вземат с обратен знак. Елементите b" r и c" l се изчисляват по същия принцип.

Останалите формули могат лесно да бъдат написани с помощта на .

Правоъгълникът е конструиран според старата симплексна таблица по такъв начин, че единият му диагонал е образуван от преизчислените (a ji) и водещите (a rl) елементи (фиг. 1). Вторият диагонал се определя еднозначно. За да се намери нов елемент a" ji, произведението на елементите от противоположния диагонал, разделено на водещия елемент, се изважда от елемент a ji (това се обозначава със знака "-" до клетката). Елементите b" j, (j≠r) и c" i се преизчисляват по същия начин. (i≠l).

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

5-та стъпка. Считаме, че е намерено допустимо принципно решение. Разглеждаме коефициентите на правата на целевата функция F(x) . Признак за оптималност на симплексна таблица е неотрицателността на коефициентите за небазисни променливи в F-реда.

Ориз. 1. Правило на правоъгълника

Ако сред коефициентите на F-реда има отрицателни (с изключение на свободния член), тогава трябва да преминете към друго основно решение. При максимизиране на целевата функция базата включва една от небазисните променливи (например x l), чиято колона съответства на максималната абсолютна стойност на отрицателния коефициент c l в долния ред на симплексната таблица. Това ви позволява да изберете променливата, чието увеличение води до подобряване на целевата функция. Колоната, съответстваща на променливата x l, се нарича водеща колона. В същото време тази променлива x n+r се изключва от основата, чийто индекс r се определя от минималната симплексна връзка:

Редът, съответстващ на x n+r, се нарича водещ, а елементът от симплексната таблица a rl, стоящ в пресечната точка на водещия ред и водещата колона, се нарича водещ елемент.

6-та стъпка. според правилата, описани в стъпка 3. Процедурата продължава до намирането му оптимално решениеили се прави извод, че не съществува.

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

Ако при следващата стъпка на търсене на екстремум една от основните променливи стане равна на нула, тогава съответното базисно решение се нарича изродено. В този случай възниква така нареченото циклизиране, характеризиращо се с факта, че същата комбинация от BP започва да се повтаря с определена честота (стойността на функцията F се запазва) и е невъзможно да се премине към ново осъществимо основно решение . Зациклянето е един от основните недостатъци на симплексния метод, но е сравнително рядко. На практика в такива случаи обикновено отказват да въведат в базата променливата, чиято колона съответства на максималната абсолютна стойност на отрицателния коефициент в целевата функция, и произволно избират ново базисно решение.

Пример 1. Решете задачата

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

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

Графична интерпретация на решението на проблема е представена на фиг. 2. Максималната стойност на целевата функция се постига във върха на ОДЗП с координати . Нека решим задачата с помощта на симплексни таблици. Нека умножим второто ограничение по (-1) и въведем допълнителни променливи, за да приведем неравенствата под формата на равенства, тогава

Приемаме началните променливи x 1 и x 2 за неосновни, а допълнителните x 3, x 4 и x 5 считаме за основни и съставяме симплексна таблица (симплексна таблица 2). Решението, съответстващо на симплексната таблица. 2, не е валидно; водещият елемент е очертан и избран в съответствие със стъпка 2 от предишния алгоритъм. Следната симплексна таблица. 3 определя допустимо базисно решение, на което отговаря върхът на ОДЗП от фиг. 2 Водещият елемент е очертан и избран в съответствие с 5-та стъпка от алгоритъма за решаване на задача. Таблица 4 съответства на оптималното решение на задачата, следователно: x 1 = x 5 = 0; х 2 = 4; х 3 = 3; х 4 = 8; F max = 20.

Ориз. 2. Графично решение на задачата

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

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

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

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

Нека е необходимо да се намери максималната стойност на функцията

при условия

Тук и – дадени постоянни числа

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

при условия

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

Да сложим Тъй като вектори – единичен, тогава и

Теорема 5

(знак за оптималност на референтния план). Основен план на задачите (22) – (24) е оптимално, ако за всеки j

Теорема 6.

Ако за някои j=k и сред числата няма положителни числа , след това целевата функция(22) задачи (22) – (24) не е ограничен в многото си планове.

Теорема 7.

Ако опорният план X на задачата (22) – (24)неизродениИ , Но сред числатаима положителни (не всички), тогава има референтен план X", такъв че

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

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

В колона С 6 на тази таблица са записани коефициентите за неизвестните целеви функции, имащи същите индекси като векторите на дадения базис.

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

В табл 3 първо мредове се определят от изходните данни на задачата и се изчисляват показателите на (m+1)-ия ред. В този ред в векторната колона напишете стойността на целевата функция, която приема за даден референтен план, а в векторната колона – значение

Стойността на Z j се намира като скаларно произведение на вектор и вектор

Стойността е равна на скаларното произведение на вектора P 0 и вектора:

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

1) за j=m+1, (в ). Следователно в в такъв случайномера за всички йот 1 до н;

2) за някои й, и всички стойности, съответстващи на този индекс

3) за някои индекси й, и за всеки такъв йпоне едно от числата е положително.

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

За да определите вектора, който да бъде изключен от основата, намерете за всички Нека този минимум бъде постигнат, когато i=r. След това векторът се изключва от основата и се извиква числото разрешителен елемент.

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

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

(25)

и коефициентите на разширение на векторите през векторите на новата основа, съответстваща на новия референтен план - по формулите

(26)

След изчисление и по формули (25) и (26) техните стойности се въвеждат в таблицата. 4. Елементите от реда на тази таблица могат да бъдат изчислени или с помощта на формули

(27)

(28)

или въз основа на тяхното определение.

Таблица 3

аз

Основа

C b

P0

c 1

c 2

...

c r

...

см

c m+1

...

c k

...

c n

П 1

P2

...

П р

...

P m

P m+1

...

Pk

...

Пн

1

П 1

c 1

b 1

1

0

...

0

...

0

1m+1

...

1k

...

a 1n

2

P2

c 2

б 2

0

1

...

0

...

0

2m+1

...

2k

...

a 2n

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

r

П р

c r

b r

0

0

...

1

...

0

a rm+2

...

a rk

...

арн

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

м

P m

см

b m

0

0

...

0

...

1

amm+1

...

a mk

...

мн

m+1

F m

0

0

...

0

...

0

Δm+1

...

Δk

...

Δn

Таблица 4

аз

Баз е

C b

P0

c 1

c 2

...

c r

...

см

c m+1

...

c k

...

c n

П 1

P2

...

П р

...

P m

P m+1

...

Pk

...

Пн

1

П 1

c 1

b 1

1

0

...

a "1r

...

0

a " 1m+1

...

0

...

a "1n

2

P2

c 2

б 2

0

1

...

a "2r

...

0

a " 2m+1

...

0

...

a "2n

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

r

П р

c r

b r

0

0

...

a "rr

...

0

a " rm+2

...

1

...

a "rn

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

м

P m

см

b m

0

0

...

a "г-н

...

1

a "mm+1

...

0

...

a "mn

m+1

F m

0

0

...

z " r -c r

...

0

z " m+1 -c m+1

...

0

...

z " n -c n

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

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

И така, преходът от един референтен план към друг се свежда до прехода от една симплексна таблица към друга. Елементите на новата симплексна таблица могат да бъдат изчислени както с помощта на рекурентни формули (25)-(28), така и с помощта на правилата, които пряко произтичат от тях. Тези правила са както следва.

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

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

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

1) число, което стои в оригиналната симплексна таблица на мястото на желания елемент от новата симплексна таблица;

2) число в оригиналната симплексна таблица в пресечната точка на реда, съдържащ желания елемент от новата симплексна таблица, и колоната, съответстваща на вектора, въведен в основата;

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

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

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

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

И така, намирането на оптималния план с помощта на симплексния метод включва следните стъпки:

1. Намерете референтен план.

2. Съставете симплексна таблица.

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

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

5. По формули (25) – (28) се определят положителните компоненти на новия опорен план и коефициентите на векторно разширение Pjчрез вектори на новата основа и число , . Всички тези числа са записани в нова симплексна таблица.

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

Пример 9.

За производство на различни продукти А,INи C предприятието използва три различни видовесурови материали. Разход на суровини за производството на един продукт от всеки вид, цена на един продукт А,INИ СЪС, както и общото количество суровини от всеки вид, които могат да бъдат използвани от предприятието, са дадени в табл. 5.

Таблица 5

Вид на суровината	Разходни норми за суровини (кг) за продукт			Обща сумасуровини (кг)
Цена на един продукт (RUB)

Продукти А,INИ СЪСмогат да се произвеждат във всякакво съотношение (продажбите са гарантирани), но производството е ограничено до суровините от всеки вид, определени за предприятието.

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

Решение.Нека създадем математически модел на проблема. Изисква се освобождаване на продукта Аобозначаваме с x 1, продукти В -чрез , продукти С -през . Тъй като има ограничения върху фонда от суровини от всеки вид, разпределен за предприятието, променливите трябва да отговарят на следната система от неравенства:

(29)

Общата цена на продуктите, произведени от предприятието, подлежи на освобождаване на x 1 продукта А, продукти INи продукти СЪСвъзлиза на

Според тяхното икономическо съдържание променливите могат да приемат само неотрицателни стойности:

Така стигаме до следната математическа задача: сред всички неотрицателни решения на системата от неравенства (29) се изисква да се намери такова, при което функция (30) приема максимална стойност.

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

От икономическа гледна точка тези допълнителни променливи означават количеството суровина от един или друг вид, което не се използва в даден производствен план. Например, – Това е неизползваното количество суровини от тип I.

Записваме трансформираната система от уравнения във векторна форма:

Тъй като сред векторите Тъй като има три единични вектора, референтният план може да бъде написан директно за този проблем. Това е планът х=(0; 0; 0; 360; 192; 180), дефинирани от система от триизмерни единични вектори, които формират основата на триизмерно векторно пространство.

Съставяме симплексна таблица за итерация I (Таблица 6), изчисляваме стойностите и проверяваме първоначалния референтен план за оптималност:

За базисни вектори

Таблица 6

	Р 5

Както може да се види от таблица 6, стойностите на всички основни променливи са равни на нула, а допълнителните променливи приемат своите стойности в съответствие с ограниченията на проблема. Тези променливи стойности съответстват на „план“, в който нищо не се произвежда, не се използват суровини и стойността на целевата функция е нула (т.е. няма производствени разходи). Този план, разбира се, не е оптимален.

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

И така, числото - 9 означава, че когато един продукт е включен в производствения план Аосигурява увеличение на производството с 9 рубли. Ако включите един продукт в производствения план INи C, тогава общата цена на произведените продукти ще се увеличи съответно с 10 и 16 рубли. Ето защо от икономическа гледна точка най-целесъобразно е продуктите да се включат в производствения план СЪС.Същото трябва да се направи въз основа на формалния знак на симплексния метод, тъй като максималното отрицателно число по абсолютна стойност е в 4-тия ред на векторната колона Р 3. Затова въвеждаме вектора в основата Р 3. определяме вектора, който да бъде изключен от базиса. За да направим това намираме

След като намерихме броя, ние определихме от икономическа гледна точка колко продукти СЪСпредприятието може да произвежда, като се вземат предвид нормите на потребление и наличните количества суровини от всеки вид. Тъй като има съответно 360, 192 и 180 кг суровини от този тип, и за един продукт СЪСнеобходимите за изразходване суровини от всеки вид са съответно 12, 8 и 3 кг, след това максималният брой продукти СЪС, които могат да бъдат произведени от предприятието, е равно на т.е. ограничаващ фактор за производството на продукти СЪСе наличният обем суровини от II тип. Като се има предвид неговата наличност, компанията може да произведе 24 продукта СЪС.В този случай суровините от тип II ще бъдат използвани напълно.

Следователно векторът Р 5 подлежи на изключване от осн. Векторна колона РРедовете от 3 до 2 са водачите. Съставяме таблица за итерация II (Таблица 7).

Таблица 7

	П 4 стр 3

Първо, запълваме линията на нововъведения вектор в основата, т.е. линията, чийто номер съвпада с номера на водещата линия. Тук водачът е 2-ри ред. Елементите на този ред са в таблицата. 7 се получават от съответните елементи на таблица 6 чрез разделянето им на разделящия елемент (т.е. на 8). Освен това в колоната C bЗаписваме коефициента в колоната на вектора, въведен в основата. След това попълваме елементите на колоните за векторите, включени в новата база. В тези колони, в пресечната точка на редове и колони на вектори със същото име, ние поставяме единици, а всички останали елементи са равни на нула.

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

Нека изчислим елементите на таблицата. 7, стоящи във векторна колона Р 0 . Първият е в първия ред на тази колона. За да го изчислим, намираме три числа:

1) числото в таблицата. 6 в пресечната точка на векторната колона Р 0 и 1-ви редове (360);

2) числото в таблицата. 6 в пресечната точка на векторната колона П 3-ти и 1-ви редове (12);

3) числото в таблицата. 7 в пресечната точка на векторната колона Р 0 и 2-ри редове (24).

Като от първото число извадим произведението на другите две, намираме търсения елемент: 360 – 12 x 24 = 72; запишете го в първия ред на векторната колона Р 0 раздел. 7.

Елемент от втората колона на вектора Р 0 раздел. 7 вече беше изчислено по-рано. За да изчислите третия елемент от колона на вектор Р 0 намираме и три числа. Първият от тях (180) се намира в пресечната точка на 3-ти ред и колона на вектора Р 0 раздел. 6, втора (3) – в пресечната точка на 3-ти ред и колона на вектора П 3 маси 6, трета (24) – в пресечната точка на 2-ри ред и колона на вектора Р 0 раздел. 8. И така, посоченият елемент е 180 - 24 x 3 = 108. Записваме числото 108 в 3-тия ред на векторната колона Р 0 раздел. 7.

Значение Е 0 в 4-тия ред на колоната на същия вектор може да се намери по два начина:

1) по формулата, т.е.

2) според правилото на триъгълника; в този случай триъгълникът се формира от числата 0, -16, 24. Този метод води до същия резултат: 0 - (-16) x 24 = 384.

При определяне на елементите на векторната колона с помощта на правилото на триъгълника Р 0 третото число, стоящо в долния връх на триъгълника, остана непроменено през цялото време и само първите две числа се промениха. Нека вземем това предвид, когато намираме елементите на векторната колона П 1 маса 7. За да изчислим посочените елементи, вземаме първите две числа от колоните на векторите П 1 и Р 3 маси 6, а третото число е от табл. 7. Това число е в пресечната точка на 2-ри ред и колона на вектора П 1 от последната таблица. В резултат на това получаваме стойностите на необходимите елементи: 18 – 12 x (3/4) =9; 5 – 3 x (3/4) = 11/4.

Число в 4-ти ред на векторната колона П 1 маса 7 може да се намери по два начина:

1) съгласно формулата Z 1 -C 1 = (C,P 1) -C 1 имаме

2) според правилото на триъгълника, което получаваме

По същия начин намираме елементите на векторната колона П 2 .

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

При изчисляване на елемента от 1-ви ред на посочената колона се получава триъгълник, образуван от числата 0,12 и 1/8. Следователно необходимият елемент е 0 – 12x (1/8) = -3/2. Елементът в 3-тия ред на тази колона е равен на 0 - 3 x (1/8) = -3/8.

След завършване на изчислението на всички елементи на таблицата. 7 в него се получават нов референтен план и векторни коефициенти на разширение чрез базисните вектори P 4, P 3, P 6 и стойностите и . Както се вижда от тази таблица, новият справочен план за задачата е планът х=(0; 0; 24; 72; 0; 108). С този производствен план се произвеждат 24 продукта СЪСи 72 кг суровини от вид 1 и 108 кг суровини от вид III остават неизползвани. Цената на всички продукти, произведени по този план, е 384 рубли. Посочените числа са записани във векторната колона Р 0 раздел. 7. Както можете да видите, данните в тази колона все още представляват параметрите на разглеждания проблем, въпреки че са претърпели значителни промени. Данните в други колони също са променени и икономическото им съдържание е станало по-сложно. Така че, например, вземете данните от векторната колона Р 2 . Числото 1/2 във втория ред на тази колона показва колко трябва да се намали производството на продукти СЪС, ако планирате да пуснете един продукт IN.Числата 9 и 3/2 в 1-ви и 3-ти ред на вектора П 2 показват съответно колко суровини от тип I и II ще бъдат необходими, когато бъдат включени в производствения план за един продукт IN, а числото - 2 в 4-ти ред показва, че ако е планирано пускането на един продукт IN, тогава това ще осигури увеличение на производствената продукция в стойностно изражение с 2 рубли. С други думи, ако включите един продукт в производствения план IN, тогава това ще изисква намаляване на производството на продукта СЪСс 1/2 единица и ще изисква допълнителни разходи от 9 kg суровини от тип I и 3/2 kg суровини от тип III, а общата цена на произведените продукти в съответствие с новия оптимален план ще се увеличи с 2 рубли. По този начин числата 9 и 3/2 действат като нови „норми“ за разходите за суровини от тип I и III за производството на един продукт IN(както се вижда от таблица 6, преди това те бяха равни на 15 и 3), което се обяснява с намаляване на производството на продукта СЪС.

Данните от векторната колона също имат същото икономическо значение Р 1 маса 7. Числата, записани във векторната колона, имат малко по-различно икономическо съдържание Р 5 . Числото 1/8 във втория ред на тази колона показва, че увеличаването на обема на суровините от тип II с 1 kg би позволило увеличаване на производството на продукти СЪСс 1/8 единици В същото време ще са необходими допълнителни 3/2 kg суровини от тип I и 3/8 kg суровини от тип III. Увеличаване на производството на продукта СЪСс 1/8 единици ще доведе до увеличение на производството с 2 рубли.

От горното икономическо съдържание на данните в табл. 7 следва, че проблемният план, открит при итерация II, не е оптимален. Това се вижда от 4-ти ред на таблицата. 7, тъй като във векторната колона П 2 на този ред е отрицателно число - 2. Това означава, че векторът трябва да бъде въведен в основата П 2, т.е. новият план трябва да предвижда производство на продукция IN.При определяне на възможния брой продукти за производство INследва да се вземе предвид наличното количество суровини от всеки вид, а именно: възможното производство на продукти INе дефинирано за , т.е. намираме

Следователно векторът трябва да бъде изключен от базиса Р 4 с други думи, освобождаване на продукта INограничено от суровините от тип I, налични в предприятието. Като се вземат предвид наличните количества от тези суровини, компанията трябва да произвежда 8 продукта IN.Числото 9 е разделящият елемент и колоната на вектора П 2 и 1 ред на таблицата. 7 са водачи. Съставяме таблица за итерация III (Таблица 8).

Таблица 8

	П 2 П 3

В табл 8, първо попълваме елементите на 1-ви ред, който е редът на вектора, нововъведен в основата Р 2 . Елементите на този ред се получават от елементите на 1-ви ред на таблицата. 7 чрез разделяне на последното на разделящия елемент (т.е. на 9). Освен това в колоната C bна този ред пишем .

След това попълваме елементите на колоните на базисните вектори и по правилото на триъгълника изчисляваме елементите на останалите колони. В резултат на това в табл. 8 получаваме нов справочен план х=(0; 8; 20; 0; 0; 96) и коефициенти на векторно разширение чрез базисни вектори и съответните стойности и

Проверяваме дали дадения референтен план е оптимален или не. За да направите това, помислете за 4-ти ред, таблица. 8. Сред числата в този ред няма отрицателни числа. Това означава, че намереният референтен план е оптимален и

Следователно, производствен план, който включва производството на 8 продукта INи 20 продукта СЪС, е оптимално. С този план за производство на продукти суровините от тип I и II се използват напълно и 96 kg суровини от тип III остават неизползвани, а себестойността на произведените продукти е 400 рубли.

Оптималният производствен план не предвижда производството на продукти А.Запознаване с производствения план за изделия от вида Аби довело до намаляване на посочените общи разходи. Това може да се види от 4-тия ред на векторната колона П 1, където цифрата 5 показва, че за даден план, включително освобождаване на единица продукт Аводи само до намаляване на общите разходи с 5 рубли.

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

Таблица 9

	Р 5 П 4 стр 3 П 2 стр 3

Както се вижда от табл. 10, първоначалният референтен план не е оптимален. Затова преминаваме към нов справочен план. Това може да се направи, защото в колоните от вектори П 1 и стр 5 , чийто 4-ти ред съдържа отрицателни числа, има положителни елементи. За да преминем към нов референтен план, въвеждаме вектора в основата стр 5 и изключете вектора от основата стр 4 . Съставяме таблица II на итерация.

Таблица 11

Както се вижда от табл. 11, новият референтен план на проблема не е оптимален, тъй като в 4-ти ред на векторната колона П 1 струва отрицателно число -11/3. Тъй като в колоната на този вектор няма положителни елементи, тази задача няма оптимален план.

Линейно програмиране е техника за математическо моделиране, предназначена да оптимизира използването на ограничени ресурси. LP се използва успешно във военната област, индустрията, селско стопанство, транспортна индустрия, икономика, здравна система и дори в социални науки. Широкото използване на този метод се поддържа и от високоефективни компютърни алгоритми, които прилагат този метод. Алгоритмите за оптимизация за други, по-сложни типове модели и задачи за изследване на операции (OR), включително целочислено, нелинейно и стохастично програмиране, се основават на алгоритми за линейно програмиране.

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

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

Където X = (x 1 , х 2 , ... , х н ) ; У– диапазон от допустими стойности на променливите х 1 , х 2 , ... , х н ;f(X)– целева функция.

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

Един оптимизационен проблем е неразрешим, ако няма оптимално решение. По-специално, проблемът за максимизиране ще бъде неразрешим, ако целта функция f(X)не е ограничено отгоре на допустимото множество У.

Методите за решаване на оптимизационни проблеми зависят както от вида на целевата функция f(X), и от структурата на допустимото множество У. Ако целевата функция в проблема е функция нпроменливи, тогава методите за решаване се наричат ​​методи за математическо програмиране.

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

индекс на оптималност f(X)е линейна функция на елементите на решението X = (x 1 , х 2 , ... , х н ) ;

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

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

(2) (3) (4) (5)

В този случай системата от линейни уравнения (3) и неравенства (4), (5), която определя допустимото множество от решения на задачата У, Наречен система от ограничения задачи за линейно програмиране и линейна функция f(X)Наречен целева функция или критерий за оптималност .

Валидно решение е колекция от числа ( план ) х = (х 1 , х 2 , ... , х н ) , удовлетворяващи ограниченията на проблема. Оптимално решение – това е план, при който целевата функция приема своята максимална (минимална) стойност.

Ако математическият модел на задача за линейно програмиране има формата:

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

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

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

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

ако дясната страна на ограниченията е отрицателна, тогава това ограничение трябва да се умножи по -1;

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

ако някаква променлива х йняма ограничения за знаци, тогава се заменя (в целевата функция и във всички ограничения) от разликата между две нови неотрицателни променливи: х 3 = х 3 + -х 3 - , Където х 3 + , х 3 - ≥ 0 .

Пример 1. Намаляване на проблема с линейното програмиране до канонична форма:

min L = 2x 1 +x 2 -х 3 ; 2x 2 -х 3 ≤ 5; х 1 +x 2 -х 3 ≥ -1; 2x 1 -х 2 ≤ -3; х 1 ≤ 0; х 2 ≥ 0; х 3 ≥ 0.

Нека във всяко уравнение на системата от ограничения въведем изравняващи променливи х 4 , х 5 , х 6 . Системата ще бъде записана под формата на равенства, а в първото и третото уравнение на системата от ограничения променливите х 4 , х 6 се вписват лява странасъс знак "+", а във второто уравнение променливата х 5 се въвежда със знак "-".

2x 2 -х 3 +x 4 = 5; х 1 +x 2 -х 3 -х 5 = -1; 2x 1 -х 2 +x 6 = -3; х 4 ≥ 0; х 5 ≥ 0; х 6 ≥ 0.

Свободните членове в каноничната форма трябва да са положителни; за да направите това, умножете последните две уравнения по -1:

2x 2 -х 3 +x 4 = 5; -х 1 -х 2 +x 3 +x 5 = 1; -2x 1 +x 2 -х 6 = 3.

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

Алгоритъмът на симплексния метод намира оптималното решение, като разглежда ограничен брой възможни основни решения. Алгоритъмът на симплексния метод винаги започва с някакво изпълнимо базисно решение и след това се опитва да намери друго изпълнимо базисно решение, което „подобрява“ стойността на целевата функция. Това е възможно само ако увеличението на която и да е нулева (небазисна) променлива води до подобряване на стойността на целевата функция. Но за да може една неосновна променлива да стане положителна, една от текущите основни променливи трябва да бъде настроена на нула, т.е. преобразувайте в неосновни. Това е необходимо, така че новото решение да съдържа точно мосновни променливи. В съответствие с терминологията на симплексния метод се извиква избраната нулева променлива вход (към основата), а базовата променлива, която трябва да бъде изтрита, е изключени (от основата).

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

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

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

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

F = с 1 x 1 +с 2 x 2 +…+с n x n max

x 1 0, x 2 0,…, x n 0.

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

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

2-ра стъпка.Съставяме началната симплексна таблица.

Променливи	Основни и допълнителни променливи								безплатни членове (решение)	Приблизително поведение

3-та стъпка.Проверяваме изпълнението на критерия за оптималност - наличието на отрицателни коефициенти в последния ред. Ако няма такива, тогава решението е оптимално и F * =c o, основните променливи са равни на съответните коефициенти b j, небазисните променливи са равни на нула, т.е. X * =(b 1,b 2,…, b m, 0,…, 0).

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

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

Прогнозното съотношение на i-тия ред е

 ако b i и a има различни знаци;

 ако b i =0 и a е<0;

 ако a е =0;

0, ако b i =0 и a е >0;

В графата оценъчни отношения намираме минималния елемент min който дефинира разрешаващия низ g.

Ако няма минимум, тогава задачата няма краен оптимум I и е неразрешима.

В пресечната точка на разрешаващия ред и колоната има разделящ елемент a gs.

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

Да преминем към третата стъпка.

М-метод Понякога, когато се решава ZLP, матрицата от коефициенти за неизвестни системни ограничения няма единични колони, от които може да се състави единична матрица, т.е. възниква проблем при избора на базови променливи или първоначалното решение е неприемливо. В такива случаи използвайте метод на изкуствена основа (М - метод).Във всички ограничения, където няма основни променливи, изкуствени променливи. В целевата функция се въвеждат изкуствени променливи с коефициент (- M) за задачи с max и с коефициент (+ M) за задачи с min, където M е достатъчно голямо положително число. След това разширената задача се решава с помощта на правилата на симплексния метод. Ако всички изкуствени променливи са равни на нула, т.е. са изключени от основата, тогава или ще се получи оптимално решение на първоначалния проблем, или първоначалният проблем се решава допълнително и се намира оптималното му решение или се установява неговата неразрешимост. Ако поне една от изкуствените променливи се окаже различна от нула, тогава първоначалният проблем няма решение

11.4. ДВОЙЕН СИМПЛЕКСЕН МЕТОД

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

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

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

Като се има предвид това условие, като се вземе предвид двойствеността, можем да напишем

.

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

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

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

Пример. Намерете минимума на функция

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

.

Да преминем към каноничната форма:

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

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

Основен променливи	х 1	х 2	х 3	х 4	х 5	Решение
х 3 х 4 х 5	–3 –4	–1 –3				–3 –6
	–2	–1

Първоначално базово решениеоптимално, но не и приемливо.

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

Условие за допустимост. Най-голямата отрицателна базова променлива по абсолютна стойност се избира като изключена променлива (ако има алтернативи, изборът се прави произволно). Ако всички базови променливи са неотрицателни, процесът на изчисление приключва, тъй като полученото решение е осъществимо и оптимално.

Състояние оптималност. Променливата, включена в основата, се избира измежду неосновните променливи, както следва. Изчисляват се съотношенията на коефициентите на лявата страна-уравнения към съответните коефициенти на уравнението, свързано с изключената променлива. Коефициенти с положителен или нулев знаменател не се вземат предвид. В задачата за минимизиране входната променлива трябва да съответства на най-малкото от посочените съотношения, а в задачата за максимизиране - отношението, което е най-малко по абсолютна стойност (ако има алтернативи, изборът се прави произволно). Ако знаменателите на всички съотношения са нула или положителни, проблемът няма възможни решения.

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

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

Променливи	х 1	х 2	х 3	х 4	х 5
Уравнението х 4 - уравнение	–2 –4	–1 –3
Поведение

Включената променлива е избрана х 2. Последващото преобразуване на низ води до нова симплексна таблица:

Основен променливи	х 1	х 2	х 3	х 4	х 5	Решение
х 3 х 2 х 5						–1 –1

Ново решение също оптимално, но все пак неприемливо. Като нова изключена променлива избираме (произволно) х 3. Нека дефинираме променливата, която да бъде включена.

Променливи	х 1	х 2	х 3	х 4	х 5
Уравнението х 4 - уравнение
поведение

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

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

Решение:

аз повторение:

x3, x4, x5, x6 x1,x2. Нека изразим основните променливи чрез свободни:

Нека редуцираме целевата функция до следния вид:

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

Таблица 5.3

Оригинална симплексна маса

				Оценъчни отношения

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

Етап 3: проверка на съвместимостта на системата за ограничения на PAP.

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

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

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

Етап 6: проверка на оптималността.

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

Тъй като намереното основно решение е допустимо, ще търсим разрешаващата колона по следната схема: определяме колоните с отрицателни елементи в реда на целевата функция (с изключение на колоната със свободни числа). Съгласно таблица 5.3 има две такива колони: колона „ x1" и колона " x2" От такива колони се избира тази, която съдържа най-малкия елемент в реда на целевата функция. Тя ще бъде разрешителната. Колона " x2" съдържа най-малкия елемент (–3) в сравнение с колоната " x1

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

Таблица 5.4

Оригинална симплексна маса

В таблица 5.4 най-малката положителна оценъчна връзка съответства на реда „ x5“, следователно ще бъде разрешително.

Елементът, разположен в пресечната точка на разрешаващата колона и разрешаващия ред, се приема като разрешаващ. В нашия пример това е елементът, който се намира в пресечната точка на линията " x5" и колони " x2».

Разрешаващият елемент показва една база и една свободна променлива, които трябва да бъдат разменени в симплексната таблица, за да се премине към ново „подобрено“ базисно решение. В този случай това са променливи x5И x2, в новата симплексна таблица (Таблица 5.5) ги разменяме.

9.1. Трансформация на разделящия елемент.

Резолюционният елемент от таблица 5.4 се преобразува, както следва:

Въвеждаме получения резултат в подобна клетка в таблица 5.5.

9.2. Преобразуване на низове за резолюция.

Разделяме елементите на разрешаващия ред на таблица 5.4 на разделящия елемент на тази симплексна таблица, резултатите се вписват в подобни клетки на новата симплексна таблица (таблица 5.5). Трансформациите на разделителните низови елементи са дадени в таблица 5.5.

9.3. Преобразуване на разделителната колона.

Разделяме елементите на разделителната колона на таблица 5.4 на разделителния елемент на тази симплексна таблица и резултатът се взема с обратен знак. Получените резултати се вписват в подобни клетки на новата симплексна таблица (Таблица 5.5). Трансформациите на елементите на разделителната колона са дадени в таблица 5.5.

9.4. Трансформация на останалите елементи от симплексната таблица.

Трансформацията на останалите елементи на симплексната таблица (т.е. елементи, които не са разположени в разрешаващия ред и разрешаващата колона) се извършва съгласно правилото на "правоъгълника".

Например, помислете за трансформиране на елемент, разположен в пресечната точка на линията " x3" и колони "", условно ще го обозначим " x3" В таблица 5.4 мислено начертаваме правоъгълник, единият връх на който се намира в клетката, чиято стойност трансформираме (т.е. в клетката „ x3"), а другият (диагонален връх) е в клетка с разрешаващ елемент. Другите два върха (от втория диагонал) са еднозначно определени. Тогава трансформираната стойност на клетката " x3" ще бъде равна на предишната стойност на тази клетка минус дробта, в чийто знаменател е разделящият елемент (от таблица 5.4), а в числителя е произведението на два други неизползвани върха, т.е.:

« x3»: .

Стойностите на други клетки се преобразуват по подобен начин:

« х3 х1»: ;

« x4»: ;

« х4 х1»: ;

« x6»: ;

« х6 х1»: ;

«»: ;

« x1»: .

В резултат на тези трансформации се получава нова симплексна таблица (Таблица 5.5).

II повторение:

Етап 1: изготвяне на симплексна таблица.

Таблица 5.5

Симплексна масаII итерации

				Приблизително връзка

Етап 2: определяне на основния разтвор.

В резултат на симплексните трансформации се получава ново основно решение (Таблица 5.5):

Както можете да видите, с това основно решение стойността на целевата функция = 15, което е по-голямо, отколкото с предишното основно решение.

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

Етап 4: проверка на ограничеността на целевата функция.

Неограничеността на целевата функция в съответствие с критерий 2 в таблица 5.5 не се разкрива.

Етап 5: проверка на допустимостта на намереното основно решение.

Намереното основно решение в съответствие с критерий 4 не е оптимално, тъй като редът на целевата функция на симплексната таблица (Таблица 5.5) съдържа отрицателен елемент: –2 (свободният номер на този ред не се взема предвид при разглеждането на това Характеристика). Затова преминаваме към етап 8.

Етап 8: определяне на разрешаващия елемент.

8.1. Дефиниция на колоната за разделителна способност.

Намереното основно решение е приемливо, определяме колоните с отрицателни елементи в реда на целевата функция (с изключение на колоната със свободни числа). Според таблица 5.5 има само една такава колона: „ x1" Затова го приемаме за позволено.

8.2. Дефиниция на разрешаващ низ.

Според получените стойности на положителните оценъчни отношения в таблица 5.6, минимумът е отношението, съответстващо на линията „ x3" Затова го приемаме за позволено.

Таблица 5.6

Симплексна масаII итерации

				Приблизително връзка
				3/1=3 – мин

Етап 9: трансформация на симплексната таблица.

Трансформациите на симплексната таблица (Таблица 5.6) се извършват по същия начин, както в предишната итерация. Резултатите от трансформациите на елементите на симплексната таблица са дадени в таблица 5.7.

III повторение

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

Таблица 5.7

Симплексна масаIII итерации

				Приблизително връзка

Етап 2: определяне на основния разтвор.

В резултат на симплексните трансформации се получава ново основно решение (Таблица 5.7):

Етап 3: проверка на съвместимостта на системата от ограничения.

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

Етап 4: проверка на ограничеността на целевата функция.

Не се разкрива неограниченост на целевата функция в съответствие с критерий 2 в таблица 5.7.

Етап 5: проверка на допустимостта на намереното основно решение.

Намереното базово решение по критерий 3 е приемливо, тъй като не съдържа отрицателни компоненти.

Етап 6: проверка на оптималността на намереното базисно решение.

Намереното основно решение в съответствие с критерий 4 не е оптимално, тъй като редът на целевата функция на симплексната таблица (Таблица 5.7) съдържа отрицателен елемент: –3 (свободният номер на този ред не се взема предвид при разглеждането на това Характеристика). Затова преминаваме към етап 8.

Етап 8: определяне на разрешаващия елемент.

8.1. Дефиниция на колоната за разделителна способност.

Намереното основно решение е приемливо, определяме колоните с отрицателни елементи в реда на целевата функция (с изключение на колоната със свободни числа). Според таблица 5.7 има само една такава колона: „ x5" Затова го приемаме за позволено.

8.2. Дефиниция на разрешаващ низ.

Съгласно получените стойности на положителни оценъчни отношения в таблица 5.8, минимумът е отношението, съответстващо на линията „ x4" Затова го приемаме за позволено.

Таблица 5.8

Симплексна масаIII итерации

				Приблизително връзка
				5/5=1 – мин

Етап 9: трансформация на симплексната таблица.

Трансформациите на симплексната таблица (Таблица 5.8) се извършват по същия начин, както в предишната итерация. Резултатите от трансформациите на елементите на симплексната таблица са дадени в таблица 5.9.

IV повторение

Етап 1: изграждане на нова симплексна таблица.

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

Таблица 5.9

Симплексна масаIV итерации

				Приблизително връзка
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Етап 2: определяне на основния разтвор.

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

Етап 3: проверка на съвместимостта на системата от ограничения.

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

Етап 4: проверка на ограничеността на целевата функция.

Не се разкрива неограниченост на целевата функция в съответствие с критерий 2 в таблица 5.9.

Етап 5: проверка на допустимостта на намереното основно решение.

Намереното базово решение по критерий 3 е приемливо, тъй като не съдържа отрицателни компоненти.

Етап 6: проверка на оптималността на намереното базисно решение.

Намереното основно решение в съответствие с функция 4 е оптимално, тъй като няма отрицателни елементи в реда на целевата функция на симплексната таблица (Таблица 5.9) (свободният номер на този ред не се взема предвид при разглеждането на тази характеристика) .

Етап 7: проверка на алтернативността на решението.

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

Отговор: оптималната стойност на целевата функция на разглежданата задача =24, която се постига при.

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

Решение:

аз повторение:

Етап 1: формиране на началната симплексна таблица.

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

В получената система от уравнения ние приемаме като разрешени (основни) променливи x3, x4, x5, x6, тогава свободните променливи ще бъдат x1,x2. Нека изразим основните променливи чрез свободни.