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

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

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

Нека многоъгълникът ABCDEFGH представлява множеството от възможни решения на PLP с две променливи и нека векторът N бъде градиент на целевата функция.

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

• Нека бъде определено първоначалното възможно основно решение на проблема, съответстващо на ъгловата точка B.

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

• От фигурата обаче става ясно, че като се вземе предвид посоката на градиента N, е по-изгодно да се премине към съседния връх C, а след това към съседния връх D, което съответства на оптималното основно решение на задачата.

• По този начин, вместо осем решения, ще трябва да се разгледат само три осъществими основни решения.

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

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

• Симплексният метод и неговото име са предложени за първи път от американския математик Джон Данциг през 1947 г., въпреки че идеите на метода са публикувани от руския математик Л.В. Канторович през 1939 г. в статията „Математически методи за организиране и планиране на производството“.

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

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

• правила за преминаване към следващото не най-лошо допустимо базово решение;

• проверка на оптималността на намереното решение.

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

Симплексни трансформации на система от линейни уравнения

• Нека разгледаме ЗЛП в канонична форма. Нека е дадена система от линейни уравнения:

• Трябва да намерим неотрицателно решение на тази система, което минимизира линейната функция

• Нека означим – матрицата на системата от уравнения (1),

• – разширена матрица на тази система.

Ще разгледаме случая, когато ранговете на матриците A и B са равни: , т.е. когато система (1) има безкраен брой решения. Нашата задача е да разберем дали в този случай има оптимални решения на проблема и как да ги намерим.

• За определеност приемаме, че първите r колони на матрица A са линейно независими, тогава системата (1) може да се трансформира, използвайки метода на елиминиране на Гаус, до формата:

• Тази система е еквивалентна на система от уравнения (1). Колони с коефициенти

• формират основата на системата от колони на матрицата на система (2) и следователно променливите са основни, а множеството е основно множество.

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

Нека изразим основните променливи в системата (3) чрез свободни и да получим система (4):

• (4)

• Прието е да се казва, че (4) е общо решение на системата от уравнения (1). Чрез присвояване на нулеви стойности на свободните променливи, ние определяме стойностите на основните променливи и конструираме основно решение, съответстващо на конструирания основен набор от променливи.

• И така, основното решение на система (1).

• По-нататък ще бъде показано, че ако системата (1) има допустими решения, тогава тя може да се преобразува във форма (3), така че условие (5) да е изпълнено

• Следователно ще приемем, че условие (5) е изпълнено. Тогава основното решение е осъществимо основно решение.

Използвайки равенства (4), можем да изразим функцията f чрез свободни променливи: (6) Сега можем да изчислим стойността на функцията f, съответстваща на основното решение

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

• С тази промяна в основата системата от уравнения (4) и линейната функция (6) се трансформират. За да направите това, i-тото уравнение на системата (3) трябва да бъде разрешено по отношение на xj.

• Полученото уравнение е:

• Замествайки вместо xj неговия израз от (7) в останалите уравнения на системата (4) и във функция (6), получаваме нова система, еквивалентна на система (1), която ще бъде разрешена по отношение на новата база

Коефициентът aij, показващ, че в основата xi се заменя със свободна променлива xj, се нарича разделителен елемент на симплексната таблица. От равенството (7) следва, че

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

• тогава условието трябва да е изпълнено, което означава . С други думи, разделящият елемент aij (xi е свободна променлива) в j-тата колона трябва да бъде избран положителен. Ще наречем описаната трансформация симплекс, ако разделящият елемент aij е избран съгласно следното правило:

• 1. Елемент aij изберете от j-та колона, която съдържа положителни елементи.

• 2. Ако в тази колона има няколко положителни елемента, тогава ще съставим отношенията на свободните членове bk към коефициентите akj>0.

• От всички съотношения избираме най-малкото. Нека бъде :

• (8)

• Избираме знаменателя на тази дроб като разделящ елемент. Ако няколко от тези съотношения са минимални (равни), тогава ще изберем който и да е от тези знаменатели.

Теорема. Ако в системата от линейни уравнения (4) всички свободни членове са неотрицателни, то след прилагане на симплексната трансформация те ще останат неотрицателни.

• Доказателство. Нека означим новите свободни членове след симплексната трансформация в (4) с

• Тогава при

• Ако akj>0, то от (8) следва, че

• Ако akj

• Ако akj =0, тогава

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

Идеята на симплексния метод

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

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

Нека многоъгълникът ABCDEFGH представлява множеството от допустими решения на ПЧПс две променливи и вектор – градиент на целевата функция.

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

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

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

Симплексният метод и неговото име са предложени за първи път от американския математик Джон Данциг през 1947 г., въпреки че идеите на метода са публикувани от руския математик Л.В. Канторович през 1939 г. в статията „ Математически методиорганизация и планиране на производството“.

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

Курска академия за държавна и общинска служба

Департамент по информационна и техносферна сигурност

Есе

по дисциплина "Методи на оптимални решения"

по темата "Идеята на симплексния метод"

Изпълнил: студент 2-ра година

Специалности "Икономика"

Москалева О. С.

Проверява: д-р, доц. Погосян С. Л.

Курск – 2012 г

Въведение……………………………………………………………………………………..3

1. Идеята на симплексния метод……………………………………………….…4

2. Прилагане на симплексния метод с помощта на примера……………………..……6

3. Таблична реализация на прост симплекс метод……………….10

Заключение……………………………………………………………………………………….15

Списък на използваната литература……………………………..…….16

Въведение.

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

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

Идеята на симплексния метод

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

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

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

Итерирането през всички ъглови точки е изчислително скъпо и следователно неефективно. През 1947 г. J. Dantzig предлага подредена процедура за изброяване на ъглови точки, в които да се намери оптимално решениедостатъчно е да разгледаме само малка част от тях. Тази процедура се нарича симплексен метод.

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

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

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

Обща схемаСимплексният метод се състои от следните основни стъпки: стъпка 0. Определяне на началната основа и съответната начална ъглова точка (базова линия).

етап 1. Проверка на текущата базова линия за оптималност . Ако критерият за оптималност е изпълнен, Че планът е оптимален и решението е пълно. В противен случайотидете на стъпка 2.

стъпка 2. Намиране на променливата, въведена в основните. (От условието за нарастване на целевата функция).

стъпка 3. Намиране на променлива, изключена от основните променливи (От условието за запазване на ограниченията на проблема).

стъпка 4 . Намиране на координатите на новата базова линия (съседна ъглова точка). Отидете на стъпка 1.

Повтарящите се стъпки 1-4 образуват една итерация на симплексния метод.

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

Определение. Ще кажем, че каноничният LP проблем има „предпочитана форма“, ако: десните страни на уравненията; матрицата на условията съдържа подматрица с размер на единица.

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

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

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

f(x) = х 1 + 2х 2 + 0х 3 + 0х 4 > макс
-х 1 + 2х 2 + x 3 = 4,
3х 1 + 2х 2 + x 4 = 12,
x j? 0, j = 1,2,3,4.

Матрица на условията А = (А 1 , А 2 , А 3 , А 4), където

Целеви вектор ° С =(c 1, c 2, c 3, c 4) = (1, 2, 0, 0); вектор на десните части b=(b 1 ,б 2) = (4, 12).

Стъпка 0.Намиране на началната ъглова точка (базова линия).

Задачата има предпочитана форма, тъй като десните части на уравненията са положителни, а колоните на матрицата на условието А 3, А 4 образуват единична подматрица. Това означава началната базисна матрица = (А 3 ,A 4); х 3 И х 4 - основни променливи х 1 И х 2 - неосновни променливи, в Б = (° С 3, ° С 4) = = (0, 0).

Първоначалната базова линия изглежда така x 0 =(0, 0, х 3 , х 4) = (0, 0, 4, 12); f(x o) = 0.

Етап 1.Проверка на основния план за оптималност.

Нека изчислим симплексни оценки за неосновни променливи, използвайки формула (5.1)

? 1 = 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

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

Стъпка 2. Намиране на променливата, въведена в основата.

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

Стъпка 3.Дефиниция на променлива, получена от основата.

След въвеждане на променливата в основата х 2новият план ще изглежда така

x" =(0, х 2, х 3 , х 4).

Този план не е основен, тъй като съдържа само една нулева координата, което означава, че е необходимо да направите една от променливите нула (изключете от основата) х 3 или х 4 . Нека заместим координатите на плана x" =(0, х 2, х 3 ,х 4) в ограниченията на проблема. Получаваме

2х 2 + x 3 = 4,

2х 2 + х 4 = 12.

Нека изразим основните променливи от тук х 3 И х 4 чрез променлива х 2 , вписан в основата.

х 3 = 4 - 2х 2,
х 4 = 12 - 2х 2 .

Така че променливи х 3 И х 4 трябва да е неотрицателна, получаваме система от неравенства

4 - 2х 2 ? 0,
12 - 2х 2 ? 0.

Колкото по-висока е стойността х 2 , толкова повече нараства целевата функция. Ще намерим максимална стойностнова базова променлива, която не нарушава ограниченията на проблема, т.е. удовлетворява условия (2.8), (2.9).

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

2х 2 ? 4,

2х 2 ? 12,

откъде идва максималната стойност? х 2 = min (4/2, 12/2) = 2. Заместване на тази стойност в изрази (2.6), (2.7) за х 3 И х 4 , получаваме х 3 = 0. Следователно х 3 получени от основата .

Стъпка 4.Определяне на координатите на новата базова линия.

Новата базова линия (съседна ъглова точка) е:

х" = (0, х 2, 0, х 4)

Основата на тази точка се състои от колони А 2 и А 4 , така =( А 2, А 4). Тази основа не е унитарна, тъй като векторът А 2 = (2,2), и следователно проблемът (2.2)-(2.5) няма предпочитана форма по отношение на новата основа. Нека трансформираме условията на задача (2.3), (2.4), така че да приеме предпочитаната форма по отношение на новите основни променливи х 2, х 4, така че променливата х 2 беше включено в първото уравнение с коефициент, равен на единица, и не присъстваше във второто уравнение. Нека пренапишем уравненията на задачата

- х 1 + 2 х 2 + х 3 = 4, (стр 1)

3х 1 +2 х 2 + х 4 = 12. (стр 2)

Нека разделим първото уравнение на коефициента at х 2 . Получаваме ново уравнение = p 1/2 еквивалент на оригинала

1/2 х 1 + х 2 + 1/2 х 3 = 2. ()

Използваме това уравнение, което наричаме разрешаване, за да елиминираме променливата х 2 от второто уравнение. За да направите това, трябва да умножите уравнението по 2 и да извадите от стр 2 . Получаваме = p 2 - 2= p 2 - стр 1:

4 х 1 - х 3 + х 4 = 8. ()

В резултат на това получихме ново „предпочитано“ представяне първоначален проблемспрямо нови основни променливи х 2 , х 4:

f(х) = х 1 + 2 х 2 + 0 х 3 + 0 х 4 ? макс

1/2 х 1 + x 2 + 1/2 х 3 = 2 ()

4 х 1 - х 3 + х 4 = 8 ()

x j? 0, j = 1,2,3,4

Замествайки тук представянето на новата базова линия х 1 = (0, х 2, 0, х 4), веднага ще намерим неговите координати, тъй като стойностите на основните променливи са равни на десните страни на уравненията

х" = (0, 2, 0, 8); f(х 1)=4.

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

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

Таблична реализация на прост симплекс метод

Ще демонстрираме табличната реализация, използвайки същия пример (2.2)-(2.5).

Стъпка 0. Решението започва с конструирането на първоначална симплексна таблица. Първо се попълва дясна часттаблици от третата колона. На две горни редовесе записват имена проблемни променливи (х 1, ...,х 4) и коефициенти на целевата функция за тези променливи. По-долу са коефициентите на уравненията - елементи на матрицата на условието А, така че под променливата х 1 разположен колона А 1, под променлива х 2 - колона А 2 и т.н. В дясната колона се въвеждат десните страни на ограниченията (числата). b i > 0).

След това намираме колоните на матрицата на условията, които формират основата на единицата - в нашия пример това е А 3 и А 4 - и съответните им основни променливи х 3, х 4 напишете във втората колона. Накрая в първата колона записваме коефициентите на целевата функция за основните променливи.

маса 1- Начална симплексна таблица

	Основни променливи					Основни променливи стойности ( x B = b)
		х 1	х 2	х 3	х 4
	х 3	a 11 =-1
	х 4
Рейтингова линия ? й	? 1 = -1	? 2 = -2

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

х o = (0, 0, х 3 , х 4) = (0, 0, 4, 12).

Етап 1.За проверка на плана хо за оптималност изчисляваме симплексни оценки за небазисни променливи х 1 И х 2 според формулата

? j = б, A j > - c j .

? 1 = б, А 1 > - c 1 = 0·(-1) + 0 ·3 - 1 = -1 .

С таблична реализация за изчисляване на резултата ? 1 трябва да намерим сумата от произведенията на елементите от първата колона ( в Б) към съответните елементи на колоната А 1 за неосновна променлива х 1 . Резултатът се изчислява по същия начин ? 2 , като скаларно произведение на първата колона ( в Б) на колона при променлива х 2.

? 2 = 2 > - c 2 = 0 2 + 0 2 - 2 = -2 .

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

f(х)= c B, х Б >,

скаларно умножаване на първата и последната колона на таблицата.

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

Стъпка 2.Тъй като и двете оценки ? 1 И ? 2, тогава всяка от променливите може да бъде включена в основата х 1, х 2 . Нека въведем в основата променливата с най-голяма абсолютна отрицателна оценка, т.е х 2 .

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

В примера водещата колона ще бъде в x 2 .

Стъпка 3.Ако всички елементи във водещата колона са отрицателни, тогава няма решение на задачата и макс f(х) ???. В примера всички елементи на водещата колона са положителни, следователно можем да намерим максималната стойност х 2 , при което една от старите основни променливи отива на нула. Спомнете си, че максималната стойност x 2 = min(4/2, 12/2)=2.

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

Най-малкото съотношение е в реда с базовата променлива х 3.Така че променливата х 3изключени от основните променливи ( х 3 = 0).

Редът, съдържащ променливата, която трябва да бъде изключена от основата, се нарича водеща линия.

В примера водещата линия ще бъде първата линия.

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

В нашия случай водещият елемент а 12 = 2.

Таблица 2- Първоначална симплексна таблица с водещ ред и колона

	Основни промени.					Основни променливи стойности	Уравнения
			х 2
c 3 =0	х 3	-1	2	1	0	4
			2
Рейтингова линия ? й	? 1 = -1	? 2 = -2

Стъпка 4. За да получим нов основен план, свеждаме проблема до нова предпочитана форма по отношение на новите основни променливи.

За да направим това, ще изградим нова симплексна таблица, във втората колона на която вместо изключената променлива х 3нека напишем нова основна променлива х 2, а в първата колона ( с Б) вместо от 3Нека запишем коефициента на целевата функция при х 2: c 2 =2. В новата симплексна таблица колоната at х 2трябва да стане единица (водещият елемент трябва да е равен на единица, а всички останали елементи трябва да станат нула). Това се постига чрез следните трансформации на редовете на таблицата.

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

Полученият низ p 1"Нека го наречем разрешително.

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

p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.

° С.Нека попълним последния ред, като изчислим оценките ? j " = - - c j, Където c B ", A j " -съответните колони на новата симплексна таблица и стойността на целевата функция f(x)= .

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

Таблица 3- Резултат от първата итерация

	Основни промени.					Основни променливи стойности	Уравнения
		-1/2
	х 4	4	0	-1	1	8	p 2 " = p 2 - p 1
оценки ? j"	-2

Нова базова линия х " = (0, х 2, 0, х 4) = (0, 2, 0, 8 ). От оценката ? 1 = -2 след това планирайте х " не е оптимално. За да преминем към нов основен план (на съседната ъглова точка), ще извършим още една итерация на симплексния метод.

защото? 1 тогава в основата се въвежда променлива х 1. Първата колона, съдържаща x 1 -водещи.

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

Избираме водещата колона и водещия ред и в пресечната им точка намираме водещ елемент (= 4).

Изграждаме нова (трета) симплексна таблица, като заместваме основната променлива в нея х 4 На х 1 и отново трансформиране на редовете на таблицата, така че водещият елемент да стане равен на единица, а останалите елементи на водещата колона да станат нула. За да направите това, разделете водещия (втори) ред на 4 и добавете получения втори ред, разделен на 2, към първия ред. Последен редизчислете с помощта на формули за симплексни оценки ? й"" = "", A j""> - c j, Където в Б"", A j"" - съответните колони на новата симплексна таблица. Стойността на целевата функция върху новата базова линия се намира с помощта на формулата f(x"")= "", х Б"" >.

Таблица 4- Резултат от втората итерация

	Основен промяна.					Основни променливи стойности	уравнения
							p 1 "" = p 1 "+p 2 ""/2
							p 2 "" = p 2 "/4
оценки ? j ""					f(x"")= 8

Нова базова линия х "" = (x 1, x 2, 0, 0) = (2, 3, 0, 0 ). Тъй като всички оценки са неотрицателни, тогава планът х ""- оптимален план.

По този начин, х* = (2, 3, 0, 0 ), f(x*) = 8.

ЗАКЛЮЧЕНИЕ

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

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

СПИСЪК НА ИЗПОЛЗВАНАТА ЛИТЕРАТУРА

1. Ашманов С.А. Линейно програмиране. - М.: Наука, 1981.

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

f=(n; j=1)ΣCj*Xj (макс.)

(n;j=1)Σaij*xj=aio (i=1,m)

Xj>=0 (j=1,n)

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

Главна идеяпрост методтова просто ли е m-d е разделен на 2 етапа:

1. намиране на първоначалния опорен план;

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

8. Признак за оптималност на опорния план на ЗЛП.

Атрибут на план за поддръжкае неотрицателността на елементите на колоната от свободни членове, без да се броят елементите на f-реда. Знак за оптимален план- ако в симплексна таблицасъдържа план за поддръжка, всички елементи на f-низа, които са неотрицателни (без да се брои свободният термин booo), тогава този план за поддръжка е оптимален. Ако в отношението f=boo-(n-m;j=1)Σboj*Xj+m стойността на всички свободни променливи е равна на нула, тогава целевата функция ще бъде равна на свободния член f(vectorXo)=boo. С нарастващи стойности на безплатно променлива функцияще започне да намалява, следователно с плана Ho функцията придобива екстремна стойност.

9. Намиране на начален опорен план на ЗЛП.

За да намерите първоначалния референтен план, можем да предложим следното алгоритъм:

1. напишете проблема под формата на таблица на Йордан, така че всички елементи на колоната от свободни членове да са неотрицателни, т.е. неравенството aio>=0 (i=1,m) беше изпълнено. Тези уравнения, в които свободните членове са отрицателни, първо се умножават по -1.

		-x1….. -xn
0=	a1o	а11…. a1n
…..	…..	………………………..
0=	амо	am1…..amn
f=		-c1…. -cn

Трансформирайте таблицата, като използвате стъпките за елиминиране на Jordan, като замените нулите в лявата колона със съответното x. При това на всяка крачка може да се избере permissiveвсяка колона, съдържаща поне един положителен елемент. Разрешаващият ред се определя от най-малкото от съотношенията на свободните членове към съответните положителни елементи на разделящата колона. Ако в процеса на елиминиране се срещне 0-ред, чиито всички елементи са нула, а свободният член е различен от нула, тогава системата от уравнения за ограничения няма решения. Ако срещнем 0-ред, в който, освен свободния член, няма други положителни елементи, тогава наборът от ограничителни уравнения няма неотрицателни решения.Ако наборът от ограничителни уравнения става, тогава след определен брой стъпки всички нули в лявата колона ще бъдат заменени с x и по този начин ще се получи определена база и, следователно, съответен референтен план.

10. Намиране на оптимален опорен план за ЗЛП.

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

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

11. Знак за неограниченост на целевата функция върху набор от планове и геометрична илюстрация.

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

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

Знак за безкрайността на набор от планове е наличието в f-реда на симплексна точка, съдържаща оптималния план на поне един нулев елемент, без да се брои свободният член. Нека бъде намерен оптимален план X1* с един нулев елемент в f-реда. Друг оптимален план X2* може да бъде намерен, като се избере колона с нулев елемент в f-реда като резолюция. Останалите са оптимизирани. плановете могат да бъдат определени като линейна комбинация:

Х1*= λХ1*+(1-λ)Х2* 0=<λ<=λ

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

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

Например: нека референтният план X =(x1,x2,…,xm,0,0,…,0) и свързаната система от линейно независими вектори: A1,A2,…,Am са известни, тогава за този референтен план можете да изчислите стойността CF Z=(c1x1+c2x2+…+cmxm) и да запишете ограничителните условия в следната форма x1A1+x2A2+…+xmAm=b

Тъй като векторите A1, A2,…, Am са линейно независими, всеки вектор Aj може да бъде разширен в тези вектори: Aj=x1jA1+x2jA2+…+xmjAm (*) Нека въведем стойностите Zj Zj=x1jc1+x2jc2+…+ xmjcm, където xij е коефициентът, съответстващ на Ai във вектора на разширение Aj чрез базисни вектори

Теорема 1: Подобряване на референтния план

Ако за някакъв индекс j условието Zj-Cj>0 е изпълнено, тогава стойността на CF може да бъде намалена и:

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

· ако TF не е ограничен отдолу, тогава е възможно да се изгради план, съответстващ на произволно малка стойност на TF

Теорема 2: критерий за оптималност на опорния план

Ако за някакъв индекс j в опорния план неравенството Zj-Cj0. Нека този минимум се постигне за вектора Ak, тогава именно този вектор трябва да се изведе от основата. Линията, съответстваща на този вектор, се нарича водач и се обозначава с "à".

4. След като дефинирате водачите на колони и редове, попълнете нова симплексна таблица. В такава таблица Ai ще се появи на мястото на водещата линия. Попълването на нова таблица започва с водеща линия. Като компонент на референтния план там е записана стойността Ө0 X'l=Ө0=Xk/Xkl, останалите елементи от този ред се определят по формулата X'lj X'lj=Xkj/Xkl, където Xkl е елементът разположен в пресечната точка на водачите на реда и колоната, по-точно върху него се разделят всички бивши елементи на водещата линия и автоматично се появява единица на мястото на бившия Xkl елемент. Общото правило за преизчисляване на водеща линия може да бъде записано по следния начин: Ak (нов елемент от водещата линия) = (стар елемент от водещата линия)/(елемент, разположен в пресечната точка на водещата колона и ред)

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

· за компоненти на референтния план X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil

· за компоненти, разширени върху основата X’ij=Xij-(Xkj/Xkl)*Xil

· за допълнителната линия Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

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

(нов имейл)=(стар имейл)-(нов имейл за посока на ред)*(имейл за посока на колона в съответния ред)

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

Методи на естествена и изкуствена основа. Основни понятия, алгоритми на методите.

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

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

Нека е дадено ZLP с канонична форма

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+...+an1xn=b1

a12x1+a22x2+...+an2xn=b2

…………………………

a1mx1+a2mx2+...+anmxn=bm

След това се преобразува във формата

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+...+an1xn+xn+1=b1

a12x1+a22x2+...+an2xn+xn+2=b2

……………………………….

a1mx1+a2mx2+...+anmxn+xn+m=bm

Където M са безкрайно големи числа. В получената задача първоначалната база се вижда веднага, като нея трябва да се приемат векторите с изкуствено въведените променливи xn+1, xn+2,…, xn+m. Тъй като тези вектори ще имат формата: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). След това трансформираният проблем се решава с помощта на алгоритъма на симплексния метод. Първоначалният референтен план на трансформирания проблем има формата (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, bm). Оригиналната симплексна таблица изглежда така:

Основа	коефициент CF	Планирайте	C1	C2	…	Cn	М	М	…	М
			A1	A2	…	Ан	An+1	An+2	…	An+m
An+1	М	b1	а11	а21	…	an1	1	0	…	0
An+2	М	b2	а12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	М	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

Определяме елементите на допълнителната линия по формулите Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

За определяне на разликите Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

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

Тъй като M е много голямо число, ще има много положителни числа сред разликите Zj-Cj. Тоест ще има много кандидати за включване в основата сред векторите A1,A2,…,An

Ако някакъв вектор съответства на изкуствено въведените променливи xn+1,xn+2,…,xn+m, тогава съответният вектор се извлича от основата и симплексната колона на таблицата с този вектор се зачертава и не се връща към него отново. В края на трансформацията на симплексната таблица са възможни две опции:

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

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

Проблеми с двойно линейно програмиране. Постановка на проблемите, техните свойства.

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

Първи стандартен формуляр

f(x)=c1x1+c2x2+...+cnxnàmin

a11x1+a21x2+...+an1xn>=b1

a12x1+a22x2+...+an2xn>=b2

…………………………………………..

a1mx1+a2mx2+…+anmxn>=bm

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

d(y)=b1y1+b2y2+...+bmymàmax

a11y1+a12y2+...+a1mym=0, V j=1,m

Двойка двойни задачи без седмица

Оригиналният проблем в канонична форма

f(x)=c1x1+c2x2+...+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

…………………………..