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

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

Изграждаме прави линии в координатната система x 1 x 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 е невъзможно и ние сме получили оптимален план.

КОНТРОЛНА РАБОТА ПО ДИСЦИПЛИНА:

„МЕТОДИ ЗА ОПТИМАЛНИ РЕШЕНИЯ“

Вариант No8

1. Реши графичен методзадача за линейно програмиране. Намерете максимума и минимума на функцията с дадените ограничения:

,

.

Решение

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

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

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

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

Нека построим права линия, съответстваща на стойността на функцията F = 0: F = 2x 1 +3x 2 = 0. Градиентният вектор, съставен от коефициентите на целевата функция, показва посоката на минимизиране на F(X). Началото на вектора е точка (0; 0), краят е точка (2; 3). Ще преместим тази права линия успоредно. Тъй като се интересуваме от минималното решение, ние преместваме правата линия, докато тя първо докосне обозначената област. На графиката тази права линия е обозначена с пунктирана линия.

Направо
пресича областта в точка C. Тъй като точка C се получава в резултат на пресичането на линиите (4) и (1), нейните координати удовлетворяват уравненията на тези линии:
.

След като решихме системата от уравнения, получаваме: x 1 = 3,3333, x 2 = 0.

Как можем да намерим минималната стойност на целевата функция: .

Нека помислим целева функциязадачи .

Нека построим права линия, съответстваща на стойността на функцията F = 0: F = 2x 1 +3x 2 = 0. Градиентният вектор, съставен от коефициентите на целевата функция, показва посоката на максимизиране на F(X). Началото на вектора е точка (0; 0), краят е точка (2; 3). Ще преместим тази права линия успоредно. Тъй като се интересуваме от максималното решение, ние преместваме правата линия до последното докосване на обозначената зона. На графиката тази права линия е обозначена с пунктирана линия.

Направо
пресича региона в точка B. Тъй като точка B се получава в резултат на пресичането на линиите (2) и (3), нейните координати удовлетворяват уравненията на тези линии:

.

Как можем да намерим максималната стойност на целевата функция: .

Отговор:
И
.

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

.

Решение

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

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

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

В първото смислово неравенство (≥) въвеждаме основната променлива х 3 със знак минус. Във второто смислово неравенство (≤) въвеждаме основната променлива х 4 . В 3-то смислово неравенство (≤) въвеждаме основната променлива x 5 .

Нека въведем изкуствени променливи : в първото равенство въвеждаме променлива х 6 ;

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

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

Получената основа се нарича изкуствена, а методът на решение се нарича метод на изкуствена основа.

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

От уравненията изразяваме изкуствени променливи: x 6 = 4-x 1 -x 2 +x 3, които заместваме в целевата функция: или.

Матрица на коефициента
тази система от уравнения има формата:
.

Нека решим системата от уравнения за основните променливи: х 6 , х 4 , х 5.

Ако приемем, че свободните променливи са равни на 0, получаваме първата референтен план:

X1 = (0,0,0,2,10,4)

Базисното решение се нарича допустимо, ако е неотрицателно.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6
х 4
х 5

Текущият референтен план не е оптимален, тъй като има положителни коефициенти в линията на индекса. Като водеща колона ще изберем колоната, съответстваща на променливата x 2, тъй като това е най-големият коефициент. Нека изчислим стойностите д аз и от тях избираме най-малкото: min(4:1, 2:2, 10:2) = 1.

Следователно вторият ред е водещият.

Разрешаващият елемент е равен на (2) и се намира в пресечната точка на водещата колона и водещия ред.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6
х 4
х 5

Формираме следващата част от симплексната таблица. Вместо променлива x 4, план 1 ще включва променлива x 2.

Редът, съответстващ на променливата x 2 в план 1, се получава чрез разделяне на всички елементи на реда x 4 от план 0 на разделящия елемент RE = 2. На мястото на разрешаващия елемент получаваме 1. В останалите клетки на колоната x 2 записваме нули.

Така в новия план 1 се попълват ред х 2 и колона х 2. Всички останали елементи на новия план 1, включително елементите на индексния ред, се определят от правилото на правоъгълника.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6
х 2
х 5
		1 1/2 +1 1/2 M

Текущият референтен план не е оптимален, тъй като в индексния ред има положителни коефициенти. Като водеща колона ще изберем колоната, съответстваща на променливата x 1, тъй като това е най-големият коефициент. Нека изчислим стойностите д азпо ред като частно от деленето: и от тях избираме най-малкото: min (3: 1 1 / 2, -, 8: 2) = 2.

Следователно 1-вият ред е водещият.

Разрешаващият елемент е равен на (1 1/2) и се намира в пресечната точка на водещата колона и водещия ред.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6		1 1 / 2
х 2
х 5
		-1 1 / 2 +1 1 / 2 М

Формираме следващата част от симплексната таблица. Вместо променливата x 6, план 2 ще включва променливата x 1.

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

		х 1	х 2	х 3	х 4	х 5	х 6
х 1
х 2
х 5

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

Крайната версия на симплексната таблица:

		х 1	х 2	х 3	х 4	х 5	х 6
х 1
х 2
х 5

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

Оптималният план може да се запише по следния начин: x 1 = 2, x 2 = 2:.

Отговор:
,
.

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

Намерете транспортен план, който осигурява най-ниските парични разходи (изпълнете първоначалния транспортен план, като използвате метода „северозападен ъгъл“).

Решение

Нека проверим необходимото и достатъчно условие за разрешимостта на задачата:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Условието за баланс е изпълнено. Задоволява равни нужди. Следователно, моделът транспортен проблемзатворено е.

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

потребности

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

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

Необходимият елемент е 4. За този елемент запасите са 300, изискванията са 250. Тъй като минимумът е 250, ние го изваждаме: .

			300 - 250 = 50
250 - 250 = 0

Необходимият елемент е равен на 2. За този елемент запасите са 50, изискванията са 400. Тъй като минимумът е 50, ние го изваждаме: .

			50 - 50 = 0
	400 - 50 = 350

Необходимият елемент е 5. За този елемент запасите са 300, изискванията са 350. Тъй като минимумът е 300, ние го изваждаме:

			300 - 300 = 0
	350 - 300 = 50

Необходимият елемент е 3. За този елемент запасите са 200, изискванията са 50. Тъй като минимумът е 50, ние го изваждаме:

			200 - 50 = 150
	50 - 50 = 0

Необходимият елемент е 6. За този елемент запасите са 150, изискванията са 150. Тъй като минимумът е 150, ние го изваждаме:

			150 - 150 = 0
		150 - 150 = 0

потребности

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

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

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

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

Пример. Намерете максималната стойност на целевата функция Л=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 х 1 +° С 2 х 2 (в нашия случай Л=2х 1 +2х 2), перпендикулярно на вектора СЪС(с 1 ;с 2) (СЪС(2; 2)), идващи от произхода. Ако тази линия се премести в положителната посока на вектора с, след това целевата функция Лще се увеличи, в противен случай ще намалее. Така в нашия случай правата линия на изхода от полигона ABCдрешенията ще минават през т.нар IN(3; 7.5), и следователно вкл. INцелевата функция приема максимална стойност, т.е. Л 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. Попълнете втората симплексна таблица. Променливите, при пресичането на които получаваме разрешаващ елемент, се разменят, т.е. И . Заменяме разрешаващия елемент с неговия обратен, т.е. на. Елементите на разрешаващия ред и колона (с изключение на разрешаващия елемент) са разделени на разделящия елемент. В този случай променяме знака на коефициентите на разделителната колона.

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

.

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

	х 1	х 4					х 3	х 2
х 3						х 1
х 2						х 2
х 5						х 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

;

,
.

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

Въвеждаме зависимости за целевата функция и системата от ограничения. За да направите това, въведете формулата =SUMPRODUCT(A2:B2;A3:B3) в клетка C2. В клетки 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. Графичен метод за решаване на задачи от линейно програмиране.

7) 7х 1 + 6х 2 → макс 20х 1 + 6х 2 ≤ 15 16х 1 − 2х 2 ≤ 18 8х 1 + 4х 2 ≤ 20 13х 1 + 3х 2 ≤ 4 х 1 , х 2 ≥ 0.

Стъпка 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