Намиране на разрешаващия елемент в симплексната таблица. Обща характеристика на разрешената система от уравнения

За да позволите на аплета да работи на вашия компютър, трябва да направите следното - щракнете върху Старт>Контролен панел>Програми>Java. В прозореца на Java Контролен панелизберете раздела Сигурност, щракнете върху бутона Редактиране на списък със сайтове, бутона за добавяне и вмъкнете пътя до тази страница от свободното поле адресна лентабраузър. След това щракнете върху OK и след това рестартирайте компютъра.

За да стартирате аплета, щракнете върху бутона "Simplex". Ако бутонът "Simplex" не се вижда над този ред, тогава Java не е инсталирана на вашия компютър.

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

След натискане на бутона „ок” се появява прозорец за въвеждане на останалите данни на задачата по симплексния метод: режим на показване (десетични дроби или обикновени), вид на критерия на задачата min или max, въвеждане на коефициенти на целевата функция и коефициенти на системата от ограничения със знаците “≤”, “ ≥ "или "=", не е необходимо да се въвеждат ограничения от формата x i ≥ 0, ги взема предвид в своя алгоритъм.

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

Изпратете всички забелязани грешки и коментари за аплета на: [имейл защитен] или се обадете на 8 962 700 77 06, за което ще Ви бъдем много благодарни.

Програма за М-метод

Програма за решаване транспортен проблем

Ето ръчно (не аплетно) решение на два проблема с помощта на симплексния метод (подобно на аплетното решение) с подробни обясненияза да разберете алгоритъма за решаване на проблеми. Първата задача съдържа знаци за неравенство само "≤" (проблем с начална основа), втората може да съдържа знаци "≥", "≤" или "=" (проблем с изкуствена основа), те се решават по различен начин.

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

1)Симплексен методза задача с начална база (всички признаци на неравенство ограничения " ≤ ").

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

Тази система е система с базис (базис s 1, s 2, s 3, всеки от тях е включен само в едно уравнение на системата с коефициент 1), x 1 и x 2 са свободни променливи. Проблемите, които трябва да бъдат решени с помощта на симплексния метод, трябва да имат следните две свойства:
-системата от ограничения трябва да бъде система от уравнения с базис;
-свободните членове на всички уравнения в системата трябва да са неотрицателни.

Получената система е система с базис и нейните свободни членове са неотрицателни, така че може да се приложи симплексният метод. Нека създадем първата симплексна таблица (итерация 0), т.е. таблица с коефициенти на целевата функция и система от уравнения за съответните променливи. Тук „BP“ означава колоната от основни променливи, „Разтвор“ означава колоната от дясната страна на уравненията на системата. Решението не е оптимално, т.к има отрицателни коефициенти в z-реда.

итерация 0

BP	Решение	Поведение

За да подобрим решението, преминаваме към следващата итерация и получаваме следната симплексна таблица. За да направите това, трябва да изберете активиране на колона, т.е. променлива, която ще бъде включена в основата при следващата итерация. Избира се по най-големия абсолютен отрицателен коефициент в z-реда (в максималния проблем) - в началната итерация това е колоната x 2 (коефициент -6).

След това изберете активиране на низ, т.е. променлива, която ще напусне основата при следващата итерация. Избира се чрез най-малкото съотношение на колоната „Решение“ към съответните положителни елементи на колоната за разделяне (колона „Съотношение“) - в първоначалната итерация това е ред s 3 (коефициент 20).

Разрешителен елементе в пресечната точка на разрешаващата колона и разрешаващия ред, нейната клетка е осветена в цвят, тя е равна на 1. Следователно при следващата итерация променливата x 2 ще замени s 3 в основата. Имайте предвид, че връзката не се търси в z-низ; там се поставя тире „-“. Ако има еднакви минимални отношения, тогава се избира всяка от тях. Ако всички коефициенти в разделителната колона са по-малки или равни на 0, тогава решението на проблема е безкрайно.

Нека попълним следната таблица „Итерация 1“. Ще го получим от таблицата „Итерация 0“. Целта на по-нататъшните трансформации е колоната с разделителна способност x2 да се превърне в колона с единица (с единица вместо разделителния елемент и нули вместо останалите елементи).

1) Изчислете ред x 2 от таблицата „Итерация 1“. Първо, разделяме всички членове на разрешаващия ред s 3 на таблицата „Итерация 0“ на разделящия елемент (той е равен на 1 в в такъв случай) от тази таблица, получаваме ред x 2 в таблицата „Итерации 1“. защото разрешаващият елемент в този случай е равен на 1, тогава ред s 3 от таблицата „Итерация 0“ ще съвпадне с ред x 2 от таблицата „Итерация 1“. Ред x 2 от таблицата от Итерация 1 получихме 0 1 0 0 1 20, останалите редове от таблицата от Итерация 1 ще бъдат получени от този ред и редовете от таблицата от Итерация 0, както следва:

2) Изчисляване на z-реда на таблицата „Итерация 1“. На мястото на -6 в първия ред (z-ред) в колоната x2 на таблицата Итерация 0 трябва да има 0 в първия ред на таблицата Итерация 1. За да направите това, умножете всички елементи на реда x 2 на таблицата "Итерация 1" 0 1 0 0 1 20 по 6, получаваме 0 6 0 0 6 120 и добавете този ред с първия ред (z - ред) на таблицата "Итерация 0" -4 -6 0 0 0 0, получаваме -4 0 0 0 6 120. В колоната x 2 се появява нула 0, целта е постигната. Елементите на колоната за разделителна способност x 2 са маркирани в червено.

3) Изчисляване на ред s 1 от таблицата „Итерация 1“. На мястото на 1 в s 1 ред на таблицата „Итерация 0“ трябва да има 0 в таблицата „Итерация 1“. За да направите това, умножете всички елементи на ред x 2 от таблицата "Итерация 1" 0 1 0 0 1 20 по -1, получете 0 -1 0 0 -1 -20 и добавете този ред с s 1 - ред на таблица "Iteration 0" 2 1 1 0 0 64, получаваме реда 2 0 1 0 -1 44. В колоната x 2 получаваме необходимата 0.

4) Изчислете ред s 2 от таблицата „Итерация 1“. На място 3 в s 2 ред на таблицата "Итерация 0" трябва да има 0 в таблицата "Итерация 1". За да направите това, умножете всички елементи на ред x 2 от таблицата „Итерация 1” 0 1 0 0 1 20 по -3, вземете 0 -3 0 0 -3 -60 и добавете този ред с s 2 - ред от таблицата „Итерация 0“ 1 3 0 1 0 72, получаваме реда 1 0 0 1 -3 12. В колоната x 2 се получава необходимата 0. Колоната x 2 в таблицата „Итерация 1“ е станала единица , съдържа една 1 и останалите 0.

Редовете на таблицата „Итерация 1” се получават по следното правило:

Нова линия= Стар ред – (Коефициент на колона за разделителна способност на стар ред)*(Нов ред за разделителна способност).

Например за z-низ имаме:

Стар z-низ (-4 -6 0 0 0 0)
-(-6)*Нов ред на резолюция -(0-6 0 0 -6 -120)
=Нов z-низ(-4 0 0 0 6 120) .

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

итерация 1

						Решение	Поведение

Резолвираща колона x 1, разрешаващ ред s 2, s 2 излиза от основата, x 1 влиза в основата. По абсолютно същия начин получаваме останалите симплексни таблици, докато получим таблица с всички положителни коефициенти в z-реда. Това е знак за оптимална маса.

Итерация 2

						Решение	Поведение

Резолвираща колона s 3, разрешаваща ред s 1, s 1 напуска основата, s 3 влиза в основата.

Итерация 3

						Решение	Поведение

В z-реда всички коефициенти са неотрицателни, следователно се получава оптималното решение x 1 = 24, x 2 = 16, z max = 192.

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

2) Нека решим проблема с изкуствена основа (поне един знак за ограничение на неравенството „≥“ или „=“).

Нека напишем проблема в канонична форма (под формата на система от уравнения, която изисква симплексния метод), за да направим това, въвеждаме две променливи x 3 ≥ 0 и x 4 ≥ 0, получаваме:

Системата от ограничения предлага само една допустима основна променлива x 4, само че тя е включена само в едно уравнение в третото с коефициент 1, така че добавяме изкуствени променливи R 1 ≥ 0 и R 2 ≥ 0 към първото и второто уравнения така че симплексният метод да може да се приложи, уравненията на системните ограничения трябва да бъдат система с основа, т.е. във всяко уравнение трябва да има променлива с коефициент 1, която е включена само в едно уравнение на системата, в нашия случай това са R 1, R 2 и x 4. Получихме така наречената М-задача:

Тази системае система с база, в която R 1, R 2 и x 4 са основни променливи, а x 1, x 2 и x 3 са свободни променливи, свободните членове на всички уравнения са неотрицателни. Следователно симплексният метод може да се използва за решаване на проблема. Нека запишем началната симплексна таблица:

итерация 0

	Решение	Поведение
-16

Към таблицата е добавен ред „Оценка“ за проблеми с изкуствена основа. Получава се чрез сумиране на съответните коефициенти на редове с изкуствени променливи (R) с обратен знак. Той ще присъства в таблицата, докато поне една от изкуствените променливи е в основата. Въз основа на най-големия отрицателен модулен коефициент на реда „Оценка“ се определя колоната за разрешаване, докато е в таблицата. Когато редът "Оценка" напусне таблицата (няма изкуствени променливи в основата), разрешаващата колона ще бъде определена от z-реда, както в проблема с първоначалната база. В тази таблица разрешаващата колона е x 2, тя е избрана въз основа на най-големия абсолютен отрицателен резултат (-7).Разрешаващият ред R 2 се избира въз основа на най-малкото съотношение на колоната „Решение“ към съответните положителни елементи на разрешаващата колона, както в задачата без изкуствени променливи. Това означава, че при следващата итерация променливата x2 ще премине от свободна към основна, а променливата R2 ще премине от основна към свободна. Нека напишем следната симплексна таблица:

Резолвираща колона x 1, резолвиращ ред R 1, R 1 излиза от основата, x 1 влиза в основата. След това в основата няма останали изкуствени променливи, така че в следната таблица няма ред „Оценка“:

итерация 2

							Решение	Поведение

След това колоната за разделителна способност се избира от z-реда. В z-реда всички коефициенти са неотрицателни с изключение на коефициента за изкуствената променлива R 1, който не влияе върху оптималността, когато изкуствените променливи напускат основата. Следователно се получава оптималното решение x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Специални случаи на използване на симплексния метод

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

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

3) Ако ограниченията на проблем с линейно програмиране са непоследователни (т.е. не могат да бъдат удовлетворени едновременно), тогава проблемът няма възможни решения. Тази ситуация не може да възникне, ако всички неравенства, съставляващи системата от ограничения, са от типа „≤“ с неотрицателни десни части, т.к. в този случай допълнителните променливи могат да възлизат на осъществимо решение. За други видове ограничения се използват изкуствени променливи. Ако проблемът има решение, тогава в оптималната таблица няма изкуствени променливи (R i) в основата. Ако ги има, значи проблемът няма решения.

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

Пример 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. Нека изразим основните променливи чрез свободни.

При условие, че няма „0-редове“ (ограничения за равенство) и „свободни“ променливи (т.е. променливи, които не подлежат на изискването за неотрицателност).

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

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

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

Израждане в проблемите на линейното програмиране

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

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

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

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

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

По-често прилаганите алгоритми включват някои прости правила, които намаляват вероятността от възникване или преодоляване на цикъл.

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

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

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

Нека помислим Решение за ПЧПизползвайки симплексния метод и го представете във връзка с проблема за максимизиране.

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

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

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

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

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

Намаляването на система (2.55), (2.56) до нова основа ще се нарича симплексна трансформация. Ако симплексната трансформация се разглежда като формална алгебрична операция, тогава може да се забележи, че в резултат на тази операция ролите се преразпределят между две променливи, включени в определена система линейни функции: една променлива преминава от зависима към независима, а другата, напротив, преминава от независима към зависима. Тази операция е известна в алгебрата като стъпка на елиминиране на Йордан.

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

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

б) ако има поне един отрицателен елемент в F-реда, който съответства на колона от неположителни елементи, тогава<

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

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

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

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

1) прегледайте реда, съответстващ на някакъв отрицателен свободен термин, например t-ред, и изберете някакъв отрицателен елемент в него и съответната колона се приема като разрешаваща (приемаме, че ограниченията на проблема са последователни);

2) съставят отношенията на елементите на колоната от свободни термини към съответните елементи на разрешаващата колона, които имат същите знаци (симплексни отношения);

3) изберете най-малкото от симплексните отношения. Това ще определи разрешаващия низ. Нека е например p-низ;

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

Намиране на първоначалния референтен план, каноничен изглед на ЗЛП

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

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

Първо симплексен методе предложен от американския учен J. Dantzig през 1949 г., но още през 1939 г. идеите на метода са разработени от руския учен L.V. Канторович.

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

За прилагане на симплексния метод - последователно подобряване на решението - е необходимо да се усвоят три основни елемента:

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

Правилото за преход към най-доброто (по-точно, не по-лошо) решение;

Критерий за проверка на оптималността на намереното решение.

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

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

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

???????????????????????????????????????????????????????????????????????

59. Алтернативен оптимум в ЗЛП, израждане в ЗЛП.

Израждане в проблемите на линейното програмиране

Когато разглеждахме симплексния метод, приехме, че проблемът с линейното програмиране е неизроден, т.е. всеки план за поддръжка съдържа точно m положителни компонента, където m е броят на ограниченията в проблема. В изроден план за поддръжка броят на положителните компоненти се оказва по-малък от броя на ограниченията: някои основни променливи, съответстващи на даден план за поддръжка, приемат нулеви стойности. Използвайки геометричната интерпретация за най-простия случай, когато n - m = 2 (броят на неосновните променливи е 2), е лесно да се разграничи изроден проблем от неизроден. В изроден проблем, в един връх на условния многостен се пресичат повече от две прави линии, описани с уравнения във формата xi = 0. Това означава, че една или повече страни на условния многоъгълник се свиват до точка. По същия начин, за n - m = 3 в изроден проблем, повече от 3 равнини се пресичат в един връх xi = 0. При допускането, че проблемът е неизроден

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

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

наборът от индекси E0, състоящ се от тези i, за които се постига. Множеството от индекси i, за които това условие е изпълнено, означаваме с E0,. Ако E0 се състои от един елемент, тогава векторът на условията Ai се изключва от основата (променливата xi се прави неосновна). Ако E0 се състои от повече от един елемент, тогава се формира множеството E1, което се състои от , на които . Ако E1 се състои от един индекс k, тогава променливата xk се извлича от основата. В противен случай се формира множеството E2 и т.н. На практика правилото трябва да се използва, ако циклизирането вече е открито.

Алтернативен оптимум в ЗЛП???????????????????????????????

60. Метод на изкуствената основа. М-задача. Теорема за връзката между решенията на изходната задача и М-задачата.

Метод на изкуствена основа.

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

max(F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0).

Така наречените „изкуствени променливи“ Rj се въвеждат в ограниченията и в целевата функция, както следва:

∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj

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

Симплексна таблица, която се компилира по време на процеса на решаване с помощта на метода на изкуствената основа, се нарича разширена. Той се различава от обичайния по това, че съдържа два реда за целевата функция: един за компонента F = ∑cixi, а другият за компонента M ∑Rj.Разгледайте процедурата за решаване на проблема на конкретен пример.

Пример 1. Намерете максимума на функцията F(x) = -x1 + 2x2 - x3 при ограниченията:

x1≥0, x2≥0, x3≥0.

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

2x1 + 3x2 + x3 + R1 = 3;

x1 + 3x3 + R2 = 2;

Целева функция F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).

Нека изразим сумата R1 + R2 от системата от ограничения: R1 + R2 = 5 - 3x1 - 3x2 - 4x3, тогава F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .

При съставянето на първата симплексна таблица (Таблица 1) ще приемем, че оригиналните променливи x1, x2, x3 са неосновни, а въведените изкуствени променливи са базисни. При задачите за максимизиране знакът на коефициентите за небазисни променливи в F- и M-редовете е обърнат. Знакът на константата в М-линията не се променя. Оптимизацията се извършва първо по М-линията. Изборът на водещи колони и редове, всички симплексни трансформации при използване на метода на изкуствената основа се извършват както при обичайния симплексен метод.

Максималният отрицателен коефициент по абсолютна стойност (-4) определя водещата колона и променливата x3, която ще влезе в основата. Минималното симплексно съотношение (2/3) съответства на втория ред на таблицата, следователно променливата R2 трябва да бъде изключена от основата. Водещият елемент е очертан.

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

x1=0; х2=7/9; Fmax=8/9.

Ако при елиминирането на M-низа решението не е оптимално, тогава процедурата за оптимизация продължава и се извършва по обичайния симплексен метод. Нека разгледаме пример, в който има ограничения от всички видове: ≤,=,≥

Задачата

Намерете оптималните производствени стойности за продукти от типове A, B и C. Разходи за суровини за единица продукция: A - 5, B - 2, C - 4. Обем на суровини - 2000 единици. Разходи за оборудване за единица продукция: А – 4, Б – 5, В – 4. Обем на оборудването – 1000 бр. Печалба от продажба на единица продукция: A – 10, B – 8, C – 12. Критерият е максималната печалба на предприятието. Производството на продукт А трябва да бъде най-малко 100 единици. Производството на продукт B трябва да бъде най-малко 50 единици.

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

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

Нека x1, x2, x3 са съответно количеството произведени продукти от тип A, B, C. Тогава математическият модел на задачата има формата:

F = 10 x1 + 8 x2 + 12 x3 –> макс

Въвеждаме допълнителни променливи x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0, за да преобразуваме неравенствата в равенства.

За да изберем начална база, въвеждаме изкуствени променливи x8 ≥ 0, x9 ≥ 0 и много голямо число M (M –> ∞). Решаваме по метода М.

F = 10 x1 + 8 x2 + 12 x3 + 0 x4 + 0 x5 + 0 x6 + 0 x7– M x8– M x9 –>max

Да вземем за основа x4 = 2000; x5 = 1000; x8 = 100; x9 = 50.

Въвеждаме данните в симплексна таблица

Симплексна таблица №1

Целева функция:

0 2000 + 0 1000 + (– M) 100 + (– M) 50 = – 150M

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

Δ1 = 0 5 + 0 4 + (– M) 1 + (– M) 0 – 10 = – M – 10

Δ2 = 0 2 + 0 5 + (– M) 0 + (– M) 1 – 8 = – M – 8

Δ3 = 0 4 + 0 4 + (– M) 0 + (– M) 0 – 12 = – 12

Δ4 = 0 1 + 0 0 + (– M) 0 + (– M) 0 – 0 = 0

Δ5 = 0 0 + 0 1 + (– M) 0 + (– M) 0 – 0 = 0

Δ6 = 0 0 + 0 0 + (– M) (–1) + (– M) 0 – 0 = M

Δ7 = 0 0 + 0 0 + (– M) 0 + (– M) (–1) – 0 = M

Δ2 = 0 0 + 12 0 + 10 0 + 8 1 – 8 = 0

Δ3 = 0 0 + 12 1 + 10 0 + 8 0 – 12 = 0

Δ4 = 0 1 + 12 0 + 10 0 + 8 0 – 0 = 0

Δ5 = 0 (–1) + 12 1/4 + 10 0 + 8 0 – 0 = 3

Δ6 = 0 1 + 12 1 + 10 (–1) + 8 0 – 0 = 2

Δ7 = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7

Тъй като няма отрицателни оценки, планът е оптимален.

Решение на задачата: x1 = 100; х2 = 50; x3 = 175/2 = 87,5; х4 = 1050; x5 = 0; x6 = 0; х7 = 0; Fmax = 2450

Отговор: x1 = 100; х2 = 50; x3 = 175/2 = 87,5; х4 = 1050; x5 = 0; x6 = 0; х7 = 0; Fmax = 2450 Тоест, необходимо е да се произведат x1 = 100 единици продукти от тип A, x2 = 50 единици продукти от тип B и x3 = 87,5 единици продукти от тип C. Максимална печалбав този случай ще бъде Fmax = 2450 единици.

Теорема за връзката между решенията на изходната задача и М-задачата.

???????????????????????

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

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

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

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

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

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

Задача.

За производство на продукти АИ INСкладът може да освободи не повече от 80 единици суровини. Освен това за производството на продукта Аизразходват се две единици, а продуктите IN- една единица суровини. Необходимо е да се планира производството така, че да се осигури най-голяма печалба, ако продуктите Асе изисква да се произвеждат не повече от 50 броя и продукти IN- не повече от 40 бр. Освен това печалбата от продажбата на един продукт А- 5 рубли и от IN- 3 търкайте.

Да строим математически модел, обозначавайки като х 1 количество продукти А в план, за х 2 - брой продукти IN. тогава системата за ограничения ще изглежда така:

Нека приведем проблема в канонична форма, като въведем допълнителни променливи:

(3.10)

F = -5x 1 - 3x 2 → мин.

Тази задача има специален тип(с основа, десните части са неотрицателни). Може да се реши с помощта на симплексния метод.

азсцена.Записване на проблем в симплексна таблица. Съществува взаимно еднозначно съответствие между системата от ограничения на задача (3.10) и симплексната таблица. В таблицата има толкова редове, колкото равенства има в системата от ограничения и има толкова колони, колкото са свободните променливи. Основните променливи попълват първата колона, свободните - горен редмаси. Долният ред се нарича индексен ред, в него са записани коефициентите на променливите в целевата функция. В долния десен ъгъл първоначално се записва 0, ако във функцията няма свободен член; ако има, тогава го напишете с противоположния знак. На това място (в долния десен ъгъл) ще има стойност на целевата функция, която трябва да нараства по абсолютна стойност при преминаване от една таблица към друга. И така, таблица 3.4 съответства на нашата система от ограничения и можем да преминем към етап II на решението.

Таблица 3.4

основен			Безплатно

IIсцена. Проверка на референтния план за оптималност.

Тази таблица 3.4 съответства на следния референтен план:

(х 1 , х 2 , х 3 , х 4 , х 5) = (0, 0, 50, 40, 80).

Свободни променливи х 1 , х 2 е равно на 0; х 1 = 0, х 2 = 0. И основните променливи х 3 , х 4 , х 5 вземат стойности х 3 = 50, х 4 = 40, х 5 = 80 - от графата свободни условия. Стойност на целевата функция:

-Е = - 5х 1 - 3х 2 = -5 0 - 3 0 = 0.

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

Възможни са различни ситуации.

1. В индекса Е- в низа няма отрицателни елементи. Това означава, че планът е оптимален и може да се запише решение на проблема. Целевата функция е постигнала целта си оптимална стойност, равно на числото в долния десен ъгъл, взето с обратен знак. Да преминем към етап IV.

2. Индексният ред има поне един отрицателен елемент, чиято колона няма положителни елементи. Тогава заключаваме, че целта функция Е→∞ намалява неограничено.

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

IIIсцена. Подобряване на референтния план.

От отрицателните елементи на индекса Е-редове, изберете този с най-голям модул, извикайте преобразуване на съответната колона и го маркирайте с “”.

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

В нашия пример, , елемент 2 е разрешителен. Линията, съответстваща на този елемент, се нарича също разрешаваща (Таблица 3.5).

Таблица 3.5

След като избрахме разрешаващия елемент, преизчисляваме таблицата според правилата:

1. В нова таблица със същия размер като предишния, променливите на разрешаващия ред и колона се разменят, което съответства на прехода към нова база. В нашия пример: х 1 е включена в основата, вместо това х 5, който напуска основата и вече е свободен (Таблица 3.6).

Таблица 3.6

основен			Безплатно

2. На мястото на разрешаващия елемент 2 запишете обратното му число.

3. Разделяме елементите на разделителната линия на разделителния елемент.

4. Разделяме елементите на разделителната колона на разделителния елемент и ги записваме с противоположния знак.

5. За да попълним останалите елементи от таблица 3.6, преизчисляваме по правилото на правоъгълника. Да кажем, че искаме да преброим елемента на позиция 50.

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

Така, . Пишем 10 на мястото, където е имало 50. По същия начин :

, , , .

Таблица 3.7

Ние имаме нова маса 3.7, основните променливи сега са променливите (x 3,x 4,x 1). Стойността на целевата функция стана равна на -200, т.е. намаля. За да проверим това основно решение за оптималност, трябва да преминем отново към етап II. Процесът очевидно е краен; критерият за спиране са точки 1 и 2 от етап II.

Нека завършим решението на проблема. За да направите това, нека проверим линията на индекса и, виждайки отрицателен елемент в него, извикайте разрешаването на съответната колона и, според етап III, преизчислете таблицата. След като съставихме отношенията и избрахме минимума = 40 сред тях, ние определихме разрешаващия елемент 1. Сега извършваме преизчисляването съгласно правила 2-5.

Таблица 3.8

основен

Безплатно

х 3 = 30, х 2 = 40, х 1 = 20. Свободните променливи са 0, х 5 = 0, х 4 = 0. Целевата функция приема стойността последен елементколона със свободни термини с обратен знак: - Е = -220 Е = 220, в нашия пример функцията беше изследвана при min и първоначално Е max, така че знакът всъщност се промени два пъти. Така, х* = (20, 40, 30, 0, 0), Е* = 220. Отговор на задачата:

В производствения план е необходимо да се включат 20 продукта от вида А, 40 продукта от тип B, докато печалбата ще бъде максимална и ще бъде равна на 220 рубли.

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

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

Въпроси за самоконтрол

1. Как се конструира симплексна таблица?

2. Как се отразява промяната в основата в таблицата?

3. Формулирайте критерия за спиране на симплексния метод.

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

5. От кой ред е удобно да започнете преизчисляването на таблицата?