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

Тестове за текущ контролзнания

1. Произволен икономико-математически модел на задачата линейно програмираневключва:

A. целева функция и системи с ограничения

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

C. Системи от ограничения и условия за неотрицателност на променливите

D. Целева функция и условия за неотрицателност на променливите

А.целева функция

Б. система от уравнения

В. система от неравенства

Г. условие за неотрицателност на променливите

3. Оптималното решение на проблема с математическото програмиране е

А. допустимо решение на ограничителната система

Б. всяко решение на системата за ограничения

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

Г. максимално или минимално решение на ограничителната система

4. Система от ограничения се нарича стандартна, ако съдържа

А. всички белези

b.всички знаци

C. всички марки

Г. всички знаци

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

А. една променлива

b.две променливи

C. три променливи

Г. четири променливи

6. Неравенство на формата описва

Б. обиколка

° С.полуравнина

г. самолет

7. Намира се максимумът или минимумът на целевата функция

А. в началото

Б. по страните на изпъкнал многоъгълник за решение

C. вътре в изпъкнал разтвор многоъгълник

Д.във върховете на изпъкнал полигон за решение

8. Каноничната форма на LLP е такава форма, в която системата от ограничения съдържа знаци

А. всички белези

Б. всички белези

° С.всички знаци

Г. всички знаци

9. Ако ограничението е посочено със знака “>=”, тогава в това ограничение се въвежда допълнителна променлива с коефициент

b.-1

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

° С.0

А.количеството ресурс с номер i, необходимо за производството на 1 единица продукт от j-ти вид

Б. неизползвани ресурси от i-ти вид

В. печалба от продажбата на 1 единица продукция от j -тия вид

Г. количество продукти от j-ти вид

12. Разрешаващата колона при решаване на LLP за максимална целева функция се избира въз основа на условието

А.най велик положителна стойносткоефициент Cj на целевата функция

Б. най-малката положителна стойност на коефициента Cj на целевата функция

В. най-голямото отрицателно значениекоефициент Cj на целевата функция

D. всяка колона от коефициенти за неизвестни

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

A. в пресечната точка на реда от коефициенти на целевата функция с колоната от коефициенти при x1

b.в пресечната точка на реда от коефициенти на целевата функция с колона b

C. в колоната с коефициенти при xn

Г. в пресечната точка на реда от коефициенти на целевата функция с колоната на първоначалната основа

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

А.1

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

A. по колона b

b.чрез низа от стойности на целевата функция

C. Линия за разрешение

Г. по колона за разрешение

16. Дадена е задача на линейно програмиране

b.1

17. Дадена е задача на линейно програмиране

Броят на изкуствените променливи за този проблем е

° С.2

18. Ако оригиналният LLP има формата

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

А. имат формата

b.изглежда като

C. изглежда като

Г. приличат

19. Ако оригиналният LLP има формата

А. имат формата

Б. имат формата

C. изглежда като

Д.изглежда като

20. Коефициентите за неизвестни целеви функции на двойствената задача са

А. коефициенти за неизвестни целеви функции на първоначалната задача

b.свободни членове на ограничителната система на първоначалния проблем

C. неизвестни на първоначалния проблем

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

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

А. също до максимум

Б. максимум или минимум

C. както максимум, така и минимум

Д.до минимум

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

А. трябва да се решат и двете задачи

b.решението на едното от тях се получава от решението на другото

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

Г. и двете имат еднакви решения

23. Ако оригиналният LLP има формата

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

А. имат формата

Б. имат формата

° С.изглежда като

Г. приличат

24. Ако оригиналният LLP има формата

тогава броят на променливите в двойния проблем е

b.2

25. Моделът на транспортната задача е затворен,

А.ако

26. Цикълът в транспортния проблем е

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

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

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

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

27. Потенциалите на транспортния проблем с размерност (m * n) са m + n числа ui и vj, за които условията

А.ui+vj=cij за заети клетки

Б. ui+vj=cij за свободни клетки

C. ui+vj=cij за първите две колони на таблицата за разпределение

D. ui+vj=cij за първите два реда на таблицата за разпределение

28. Оценките на транспортен проблем с размерност (m + n) са числата

yij=cij-ui-vj, които се изчисляват

А. за заети клетки

b.за свободни клетки

C. за първите два реда от таблицата за разпределение

D. за първите две колони на таблицата за разпределение

29. При решаване на транспортна задача стойността на целевата функция трябва да варира от итерация до итерация

А. увеличаване

Б. увеличаване или непромяна

C. увеличаване със стойността на произволен резултат

Д.намаляват или остават непроменени

30. Броят на заетите клетки на неизроден план на транспортния проблем трябва да бъде равен на

° С.m+n-1

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

А. общ трафик

b.обща цена на транспорта

В. общи доставки

Г. общи нужди

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

Изграждаме в координатната система x 1 oh 2 линии

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

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

Като преместим линията (5) по посока на вектора, виждаме, че максималната точка на областта ще бъде в точката А на пресечната точка на линията (3) и линията (2). Намираме решението на системата от уравнения:

И така, разбрахме точката (13;11) и.

Като преместим линията (5) по посока на вектора, виждаме, че минималната точка на областта ще бъде в точката B на пресечната точка на линията (1) и линията (4). Намираме решението на системата от уравнения:

И така, получихме точката (6;6) и.

2. Мебелна фирма произвежда комбинирани шкафове и компютърни маси. Производството им е ограничено от наличието на суровини (висококачествени плоскости, обков) и времето на работа на машините, които ги обработват. За всеки шкаф са необходими 5 м2 дъски, за маса - 2 м2. Фитинги за $10 се харчат за един шкаф и $8 за една маса. Компанията може да получи от своите доставчици до 600 m2 дъски на месец и аксесоари за $2000. За всеки шкаф са необходими 7 часа машинна работа, за маса - 3 часа. Възможно е да се използват само 840 часа работа на машината на месец.

Колко комбинирани шкафове и компютърни маси трябва да произвежда една фирма на месец, за да увеличи максимално печалбата, ако един шкаф носи $100, а всяка маса прави $50?

• 1. Съставете математически моделпроблем и го решете с помощта на симплексния метод.
• 2. Съставете математически модел на двойствената задача, запишете нейното решение въз основа на решението на първоначалната.
• 3. Определете степента на недостиг на използваните ресурси и обосновете рентабилността на оптималния план.
• 4. Проучете възможностите за допълнително увеличаване на продукцията, в зависимост от използването на всеки тип ресурс.
• 5. Оценете осъществимостта на въвеждането на нов тип продукт - рафтове за книги, ако 1 m 2 дъски и аксесоари за $ 5 се изразходват за производството на един рафт и са необходими 0,25 часа работа на машината и печалбата от продажбата на един рафт е $20.
• 1. Нека изградим математически модел за този проблем:

Означаваме с x 1 - обема на производство на шкафове и x 2 - обема на производство на маси. Нека съставим система от ограничения и целева функция:

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

Нека напишем данните за задачата под формата на таблица:

маса 1

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

Лабораторна работа #1 Решаване на задачи за линейно програмиране

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

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

Метод на геометрично решение азРазгледайте проблеми с линейно програмиране с пример.

Пример. Намерете максималната стойност на целевата функция Л=2х 1 +2х 2 при зададени ограничения

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

л 1: 3х 1 -2х 2 +6=0,

л 2: 3х 1 +х 2 -3=0,

л 3:х 1 -3=0.

дОТ

2 0 1 3 х 1

(л 1) (л 3)

Направо л 1 разделя равнината хО прина две полуравнини, от които трябва да се избере една, която да удовлетворява първото неравенство в системата (3). За това вземаме t. О(0; 0) и заместваме в неравенството. Ако е вярно, тогава трябва да засенчите полуравнината от правата линия, в която т.нар. О(0; 0). Направете същото с правите линии. л 2 и л 3 . Областта на решенията на неравенства (3) е многоъгълник ABCд. За всяка точка от равнината функцията Лприема фиксирана стойност Л=Ледин . Наборът от всички точкови токове е права линия Л=° С 1 х 1 +° С 2 х 2 (в нашия случай Л=2х 1 +2х 2) перпендикулярна на вектора ОТ(с 1 ;с 2) (ОТ(2; 2)), излизащи от произхода. Ако тази линия се премести в положителната посока на вектора с, след това целевата функция Лще се увеличи, в противен случай ще намалее. Така в нашия случай правата линия при излизане от полигона ABCдрешенията ще преминат AT(3; 7.5), и следователно, вкл. ATцелевата функция приема максимална стойност, т.е. Л max =2ּ3+2ּ7,5=21. По същия начин се определя, че функцията приема минималната стойност, т.е. д(1; 0) и Л min=2ּ1+2ּ0=2.

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

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

2. Целевата функция се изразява чрез основни и спомагателни променливи.

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

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

5. Критерият за оптималност е липсата на отрицателни елементи в последния ред на таблицата за решаване на задачата за максимума и положителни елементи за минимума.

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

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

8. Симплексните таблици се трансформират до получаване на оптимален план.

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

Решение. 1. Въвеждане на нови променливи
, с помощта на които преобразуваме неравенствата на системата в уравнения:

Променяме знака на коефициентите на целевата функция или го записваме във формата
. Попълваме първата симплексна таблица, в нулевия ред пишем х 1 ,х 2 и (безплатни коефициенти). В колона нула х 3 ,х 4 ,х 5 и Е. Попълваме тази таблица според получената система от уравнения и преобразуваната целева функция.

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

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

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

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

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

.

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

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

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

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

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

За решаване на проблеми с линейно програмиране се използва добавката Search for Solution. Първо трябва да се уверите, че тази добавка присъства в раздела Данни в групата Анализ (за 2003 г. вижте Инструменти). Ако командата Solver или групата Analyze липсват, трябва да изтеглите тази добавка.

За да направите това, щракнете върху Файл на Microsoft Office (2010), след което щракнете върху бутона Опции на Excel. В прозореца Опции на Excel, който се появява, изберете полето Добавки отляво. От дясната страна на прозореца стойността на полето Управление трябва да бъде зададена на Добавки на Excel, щракнете върху бутона „Отиди“, който се намира до това поле. В прозореца на добавките поставете отметка в квадратчето до Намиране на решение и след това щракнете върху OK. След това можете да работите с инсталираната добавка Find Solutions.

Преди да извикате Search Solutions, е необходимо да подготвите данни за решаване на задача за линейно програмиране (от математически модел) на работен лист:

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

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

След това трябва да използвате добавката Търсене на решение. В раздела Данни, в групата Анализ изберете Решател. Ще се появи диалоговият прозорец Търсене на решение, който трябва да бъде попълнен както следва:

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

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

3) Поставете отметка в квадратчето „Направете променливи без ограничения неотрицателни“. Изберете метода на решение "Търсене на решението на линейни задачи по симплексния метод". След натискане на бутона "Намери решение" започва процесът на решаване на проблема. В резултат на това се появява диалоговият прозорец „Резултати от търсенето на решение“ и оригиналната таблица с попълнени клетки за стойностите на променливите и оптималната стойност на целевата функция.

Пример.Решете с помощта на добавката Solver Задача на Excelлинейно програмиране: намерете максималната стойност на функция
под ограничения

,

;

,
.

Решение.За да разрешим нашия проблем на работен лист на Excel, ще изпълним посочения алгоритъм. Въвеждаме първоначалните данни под формата на таблица

Въвеждаме зависимости за целевата функция и системата от ограничения. За да направите това, в клетка C2 въведете формулата =SUMPRODUCT(A2:B2;A3:B3). В клетки C4 и C5, съответно, формулите са: =SUMPRODUCT(A2:B2;A4:B4) и =SUMPRODUCT(A2:B2;A5:B5). Резултатът е маса.

Стартираме командата "Търсене на решение" и попълваме появилия се прозорец Търсене на решение, както следва. В полето „Оптимизиране на целевата функция“ въведете клетка C2. Избираме да оптимизираме стойността на целевата клетка „Максимум“.

В полето "Промяна на променливи клетки" въведете променливите клетки A2:B2. В полето "Съгласно ограниченията" въведете посочените ограничения чрез бутона "Добави". Клетъчни препратки $C$4:$C$5 Ограничителни препратки =$D$4:$D$5 знак между тях<= затем кнопку «ОК».

Поставете отметка в квадратчето „Направете неограничените променливи неотрицателни“. Изберете метода на решение "Търсене на решението на линейни задачи по симплексния метод".

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

В диалоговия прозорец "Резултати от търсенето на решение" записваме резултата x1=0.75, x2=0.75 , F=1.5 - равен на максималната стойност на целевата функция.

Задачи за самостоятелна работа

Упражнение 1.Графични, симплексни методи и инструменти на Excel за намиране на максималната и минималната стойност на функцията Е(х) за дадена система от ограничения.

1. Е(х)=10х 1 +5х 2 2. Е(х)=3х 1 -2х 2

3. Е(х)=3х 1 +5х 2 4. Е(х)=3х 1 +3х 2

5. Е(х)=4х 1 -3х 2 6. Е(х)=2х 1 -х 2

7. Е(х)=-2х 1 +4х 2 8. Е(х)=4х 1 -3х 2

9. Е(х)=5х 1 +10х 2 10. Е(х)=2х 1 +х 2

11. Е(х)=х 1 +х 2 12. Е(х)=3х 1 +х 2

13. Е(х)=4х 1 +5х 2 14. Е(х)=3х 1 +2х 2

15. Е(х)=-х 1 -х 2 16. Е(х)=-3х 1 -5х 2

17. Е(х)=2х 1 +3х 2 18. Е(х)=4х 1 +3х 2

19. Е(х)=-3х 1 -2х 2 20. Е(х)=-3х 1 +4х 2

21. Е(х)=5х 1 -2х 2 22. Е(х)=-2х 1 +3х 3

23. Е(х)=2х 1 +3х 2 24. Е(х)=4х 1 +3х 2

25. Е(х)=-3х 1 -2х 2 26. Е(х)=-3х 1 +4х 2

27. Е(х)=-2х 1 +4х 2 28. Е(х)=4х 1 -3х 2

29. Е(х)=-х 1 -х 2 30. Е(х)=-3х 1 -5х 2

Тестови въпроси.

1. Какви задачи се наричат ​​задачи за линейно програмиране?

2. Дайте примери за задачи по линейно програмиране.

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

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

5. Опишете алгоритъма за решаване на задачи по линейно програмиране с помощта на Excel.

Държавно бюджетно учебно заведение

висше професионално образование

"Омски държавен технически университет"

ИЗЧИСЛИТЕЛНО-ГРАФИЧНА РАБОТА

по дисциплина"ТЕОРИЯ ЗА ОПТИМАЛНО УПРАВЛЕНИЕ »

по темата "МЕТОДИ ЗА ОПТИМИЗАЦИЯ И ИЗСЛЕДВАНЕ НА ОПЕРАЦИИ »

вариант 7

Завършено:

задочно студент

4-та година група ZA-419

Име: Кужелев С. А.

Проверено:

Девятерикова М.В.

Омск - 2012 г
^

Задача 1. Графичен метод за решаване на задачи от линейно програмиране.

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

Първото ограничение на модела е . Заменяйки знака ≤ в него със знака =, получаваме уравнението . На фиг. 1.1 той дефинира права (1), която разделя равнината на две полуравнини, в този случай над и под правата. Да се ​​избере кой удовлетворява неравенството , ние заместваме в него координатите на всяка точка, която не лежи на дадената права (например началото х 1 = 0, х 2 = 0). Тъй като получаваме правилния израз (20 0 + 6 0 = 0 ≤15), полуравнината, съдържаща началото (отбелязана със стрелка), удовлетворява неравенството. Иначе друга полуравнина.

Продължаваме по подобен начин с останалите ограничения на проблема. Пресечната точка на всички построени полуравнини се образува с първия квадрант ABCD(виж фиг. 1). Това е валидният обхват на задачата.

Стъпка 2. Изграждане на линия на ниво Линия на ниво целевата функция е набор от точки в равнината, в които целевата функция приема постоянна стойност. Такъв набор е даден от уравнението f ( х) = конст. Да сложим например конст = 0 и начертайте линия на нивото f ( х) = 0, т.е. в нашия случай директно 7 х 1 + 6х 2 = 0.

Тази права минава през началото и е перпендикулярна на вектора. Този вектор е градиентът на целевата функция при (0,0). Градиентът на функция е вектор от стойности на частните производни на дадена функция във въпросната точка. В случая на задачата LP частните производни на целевата функция са равни на коефициентите ° Саз, й = 1 , ..., н.

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

Той се намира в пресечната точка на линиите (2) и (3) (виж фиг. 1) и задава оптималното решение.

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

^ Стъпка 3. Определяне на координатите на максималната (минималната) точка и оптималната стойност на целевата функция

За да се намерят координатите на точка C, е необходимо да се реши система, състояща се от съответните директни уравнения (в този случай от уравнения 2 и 3):

16х 1 − 2х 2 ≤ 18

8х 1 + 4х 2 ≤ 20

Получаваме оптималното решение = 1,33.

^ Оптималната стойност на целевата функция f * = f (Х*) = 7 * 0 + 6 * 1,33 = 7,8