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

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

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

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

Изтегляне на бележка в , чертежи във формат

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

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

Помислете за пример за конструиране на математически модел на линейно програмиране

Николай Кузнецов управлява малък механичен завод. Следващия месец той планира да произведе два продукта (А и Б), за които специфичната маргинална печалба се оценява съответно на 2500 и 3500 рубли.

Производството и на двата продукта изисква разходи за машинна обработка, суровини и труд (фиг. 1). За производството на всяка единица продукт А са отделени 3 часа машинна обработка, 16 единици суровини и 6 единици труд. Съответните изисквания за блок B са 10, 4 и 6. Николай прогнозира, че следващия месец може да осигури 330 часа обработка, 400 единици суровини и 240 единици труд. Технологията на производствения процес е такава, че най-малко 12 единици продукт B трябва да бъдат произведени през даден месец.

Ориз. 1. Използване и осигуряване на ресурси

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

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

Етап 1. Дефиниране на променливи

Има целева променлива (нека я обозначим Z), която трябва да бъде оптимизирана, тоест максимизирана или минимизирана (например печалба, приходи или разходи). Николай се стреми да максимизира пределната печалба, следователно целевата променлива е:

Z = общата пределна печалба (в рубли), получена през следващия месец в резултат на производството на продукти А и Б.

Има редица неизвестни неизвестни променливи (означаваме ги x 1, x 2, x 3 и т.н.), чиито стойности трябва да бъдат определени, за да се получи оптималната стойност на целевата функция, която в нашия случай е общата пределна печалба. Този марж на приноса зависи от количеството произведени продукти A и B. Тези стойности трябва да бъдат изчислени и следователно са променливите от интерес в модела. Така че нека обозначим:

x 1 = броят единици от продукт А, произведени през следващия месец.

x 2 = брой единици продукт B, произведени през следващия месец.

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

Сцена. 2. Построяване на целевата функция

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

В нашия пример всеки произведен продукт А носи 2500 рубли. пределна печалба, а при производството на x 1 единици от продукт A, пределната печалба ще бъде 2500 * x 1. По същия начин пределната печалба от производството x 2 единици от продукт B ще бъде 3500 * x 2. По този начин общата пределна печалба, получена през следващия месец поради производството на x 1 единици продукт A и x 2 единици продукт B, т.е. целевата променлива Z ще бъде:

Z = 2500 * x 1 + 3500 * x 2

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

Увеличете максимално Z = 2500 * x 1 + 3500 * x 2

Сцена. 3. Дефиниране на ограниченията

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

В нашия пример продуктите A и B изискват време за обработка, суровини и труд за производство, а наличността на тези ресурси е ограничена. Производствените обеми на тези два продукта (т.е. x 1 от 2 стойности) следователно ще бъдат ограничени от факта, че количеството ресурси, необходими в производствения процес, не може да надвишава наличните. Помислете за ситуацията с времето за машинна обработка. Производството на всяка единица продукт А изисква три часа машинна обработка и ако се произведат x 1 единици, тогава ще бъдат изразходвани 3 * x 1 часа от този ресурс. Производството на всяка единица продукт B изисква 10 часа и следователно, ако се произвеждат x 2 продукта, тогава ще са необходими 10 * x 2 часа. Така общото количество машинно време, необходимо за производството на x 1 единици от продукт A и x 2 единици от продукт B, е 3 * x 1 + 10 * x 2 . то общо значениемашинното време не може да надвишава 330 часа. Математически това се записва по следния начин:

3 * x 1 + 10 * x 2 ≤ 330

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

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

И накрая, трябва да се отбележи, че има условие, според което трябва да бъдат произведени най-малко 12 единици продукт Б:

Етап 4. Записване на условията за неотрицателност

Желаните променливи не могат да бъдат отрицателни числа, които трябва да бъдат записани като неравенства x 1 ≥ 0 и x 2 ≥ 0. В нашия пример второто условие е излишно, тъй като по-горе беше определено, че x 2 не може да бъде по-малко от 12.

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

Увеличете: Z = 2500 * x 1 + 3500 * x 2

При условие, че: 3 * x 1 + 10 * x 2 ≤ 330

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

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

Този метод е подходящ само за проблеми с две задължителни променливи. Изграденият по-горе модел ще бъде използван за демонстриране на метода.

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

Ориз. 2. Графични оси на линейно програмиране

Помислете например за първото ограничение: 3 * x 1 + 10 * x 2 ≤ 330. Това неравенство описва областта под линията: 3 * x 1 + 10 * x 2 = 330. Тази права пресича оста x 1 при x 2 \u003d 0, тоест уравнението изглежда така: 3 * x 1 + 10 * 0 \u003d 330, а неговото решение: x 1 \u003d 330 / 3 \u003d 110

По подобен начин изчисляваме точките на пресичане с осите x 1 и x 2 за всички ограничителни условия:

Приемлив диапазон	Ограничение на допустимите стойности	Пресечна точка с ос x 1	Пресечна точка с ос х 2
3 * x 1 + 10 * x 2 ≤ 330	3 * x 1 + 10 * x 2 = 330	х 1 = 110; х 2 = 0	x 1 = 0; х 2 = 33
16 * x 1 + 4 * x 2 ≤ 400	16 * x 1 + 4 * x 2 = 400	x 1 = 25; х 2 = 0	x 1 = 0; х 2 = 100
6 * x 1 + 6 * x 2 ≤ 240	6 * x 1 + 6 * x 2 = 240	х 1 = 40; х 2 = 0	x 1 = 0; х 2 = 40
x 2 ≥ 12	х 2 = 12	не пресича; върви успоредно на оста x 1	x 1 = 0; х 2 = 12

Графично първото ограничение е показано на фиг. 3.

Ориз. 3. Конструиране на областта на допустимите решения за първото ограничение

Всяка точка от избрания триъгълник или от неговите граници ще отговаря на това ограничение. Такива точки се наричат ​​валидни, а точки извън триъгълника се наричат ​​невалидни.

По същия начин ние отразяваме останалите ограничения върху диаграмата (фиг. 4). Стойностите x 1 и x 2 върху или вътре в защрихованата зона ABCDE ще отговарят на всички ограничения на модела. Такава област се нарича област на допустимите решения.

Ориз. 4. Областта на възможните решения за модела като цяло

Сега, в областта на възможните решения, е необходимо да се определят стойностите x 1 и x 2, които максимизират Z. За да направите това, в уравнението на целевата функция:

Z = 2500 * x 1 + 3500 * x 2

разделяме (или умножаваме) коефициентите преди x 1 и x 2 с едно и също число, така че получените стойности да попадат в диапазона, показан на графиката; в нашия случай такъв диапазон е от 0 до 120; така че коефициентите могат да бъдат разделени на 100 (или 50):

Z = 25x 1 + 35x 2

след това задайте Z стойност равно на произведениетокоефициенти преди x 1 и x 2 (25 * 35 = 875):

875 = 25x 1 + 35x 2

и накрая намерете точките на пресичане на линията с осите x 1 и x 2:

Нека начертаем това целево уравнение върху графиката по същия начин като ограниченията (фиг. 5):

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

Стойността Z е постоянна по цялата линия на целевата функция. За да намерите стойностите x 1 и x 2, които максимизират Z, трябва паралелно да прехвърлите линията на целевата функция към такава точка в границите на зоната на допустимите решения, която се намира на максимума разстояние от първоначалната линия на целевата функция нагоре и надясно, т.е. до точка С (фиг. 6).

Ориз. 6. Линията на целевата функция е достигнала своя максимум в областта на възможните решения (в точка C)

Може да се заключи, че оптимално решениеще бъде разположен в една от крайните точки на зоната за вземане на решения. В коя ще зависи от наклона на целевата функция и от това какъв проблем решаваме: максимизиране или минимизиране. По този начин не е необходимо да се чертае целева функция - всичко, което е необходимо, е да се определят стойностите на x 1 и x 2 във всяка от крайните точки чрез четене от диаграмата или чрез решаване на съответната двойка уравнения. Намерените стойности на x 1 и x 2 след това се заместват в целевата функция, за да се изчисли съответната стойност на Z. Оптималното решение е това, при което максималната стойност на Z се получава при решаване на проблема за максимизиране, а минималната при решаване на задачата за минимизиране.

Нека да определим, например, стойностите на x 1 и x 2 в точка C. Имайте предвид, че точка C е в пресечната точка на линиите: 3x 1 + 10x 2 = 330 и 6x 1 + 6x 2 = 240. решението на тази система от уравнения дава: x 1 = 10, x 2 = 30. Резултатите от изчислението за всички върхове на областта на възможните решения са дадени в таблицата:

Точка	Стойност х 1	Стойност х 2	Z \u003d 2500x 1 + 3500x 2
НО	22	12	97 000
AT	20	20	120 000
ОТ	10	30	130 000
д	0	33	115 500
д	0	12	42 000

Така Николай Кузнецом трябва да планира производството на 10 артикула А и 30 артикула Б за следващия месец, което ще му позволи да получи пределна печалба от 130 хиляди рубли.

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

1. Начертайте две оси на графиката, представящи два параметъра за вземане на решение; начертайте само 1-ви квадрант.
2. Определете координатите на точките на пресичане на всички гранични условия с осите, като заместите стойностите x 1 = 0 и x 2 = 0 в уравненията на граничните условия на свой ред.
3. Начертайте ограничителни линии на модела върху диаграмата.
4. Определете областта на графиката (наречена допустима зона за вземане на решение), която отговаря на всички ограничения. Ако няма такъв регион, тогава моделът няма решение.
5. Определете стойностите на необходимите променливи в крайни точкиобласт на вземане на решения и във всеки случай изчислява съответната стойност на целевата променлива Z.
6. За проблеми с максимизиране решението е точката, в която Z е максимално; за проблеми с минимизиране решението е точката, в която Z е минимум.

ТЕМА: ЛИНЕЙНО ПРОГРАМИРАНЕ

ЗАДАЧА 2.А. Решаване на задача от линейно програмиране по графичен метод

внимание!

Това е ВЪВЕДЕНИЕ ВЕРСИЯ на работа № 2073, цената на оригинала е 200 рубли. Рамкирана в Програма на Microsoftдума.

Плащане. Контакти.

Вариант 7. Намерете максималната и минималната стойностлинейна функция Ф \u003d 2x 1 - 2 x 2с ограничения: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Решение:

Заменяйки условно знаци на неравенства със знаци на равенства, получаваме система от уравнения x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

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

Минималната стойност на функцията

tsii - в точката M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Максималната стойност се достига в точка N (10; 0),

Ф max \u003d 2 10 - 2 0 \u003d 20.

Вариант 8. Намерете максималната и минималната стойност

линейна функция Ф \u003d x 1 + x 2

с ограничения: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Решение:

Заменяйки условно знаци на неравенства със знаци на равенства, получаваме система от уравнения x1 - 4 x2 = 4;

3 x1 - x2 = 0;

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

Минималната стойност на функцията

ции - на права линия NP, например

в точка Р(4; 0)

Ф min = 4 + 0 = 4.

ODE не е ограничен отгоре, следователно Ф max = + ∞.

Вариант 10. Намерете максималната и минималната стойност

линейна функция Ф \u003d 2 x 1 - 3 x 2

с ограничения: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

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

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

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

Построяваме вектора Г(2; -3) и прекарваме през началото линия на ниво- прав.

Преместваме линията на нивото в посока, докато стойността на F се увеличава. В точката S(7; 0) целевата функция достига своя максимум Ф max =2·7–3·0= = 14. Преместваме линията на нивото в посока, докато стойността на Ф намалява. Минималната стойност на функцията е в точка N(0; 5)

Ф min = 2 0 – 3 5 = –15.

ЗАДАЧА 2.Б. Решаване на задача от линейно програмиране

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

Вариант 7. Минимизирайте целевата функция Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

при ограничения: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Решение:

Броят на неизвестните n=6, броят на уравненията m=3. Следователно r = n-m = 3 неизвестни могат да се приемат за свободни. Нека изберем x 1 , x 3 и x 6 .

Изразяваме основните променливи x 2 , x 4 и x 5 по отношение на свободните и привеждаме системата към единица

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Целевата функция ще изглежда така:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Нека поставим x 1 \u003d x 3 \u003d x 6 \u003d 0, докато основните променливи ще приемат стойностите x 2 \u003d 2; x 4 \u003d 9; x 5 \u003d 6, т.е. първото възможно решение (0; 2; 0; 9; 6; 0), целева функция Ф 1 \u003d 13.

Променливите x 3 и x 6 са включени в целевата функция с отрицателни коефициенти, следователно с увеличаване на техните стойности стойността на Ф ще намалее. Вземете, например, x 6 . От първото уравнение на системата (*) се вижда, че е възможно увеличение на стойността на x 6 до x 6 \u003d 1 (стига x 2 ³ 0). В този случай x 1 и x 3 запазват стойности, равни на нула. Сега като основни променливи приемаме x 4, x 5, x 6, като свободни - x 1, x 2, x 3. Нека изразим новите основни променливи чрез новите свободни. Вземете

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Присвояване на безплатни променливи нулеви стойности, тоест x 1 = x 2 = x 3 = 0, докато x 6 = 1, x 4 = 3, x 5 = 4, тоест третото валидно решение (0; 0; 0 ; 3; 4; 1 ). В този случай Ф 3 \u003d 6.

Променливата x 3 е включена в целевата функция с отрицателен коефициент, следователно увеличението на x 3 спрямо нула ще доведе до намаляване на F. От второто уравнение се вижда, че x 3 може да се увеличи до 1/ 4, от 3-то уравнение - до 2/3 . Второто уравнение е по-критично. Превеждаме променливата x 3 в броя на основните, x 4 в броя на свободните.

Сега вземаме x 1 , x 2 и x 4 като нови свободни променливи. Нека изразим нови основни променливи x 3 , x 5 , x 6 чрез тях. Да вземем системата

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Целевата функция ще приеме формата

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Променливите x 1 и x 2 са включени в целевата функция с отрицателни коефициенти, следователно с увеличаване на техните стойности стойността на Ф ще намалее. Вземете, например, x 2 . От второто уравнение на системата може да се види, че е възможно увеличение на стойността на x 2 до x 2 \u003d 5 (стига x 5 ³ 0). В този случай x 1 и x 4 запазват нулеви стойности, стойностите на другите променливи са равни на x 3 = 3/2; x 5 \u003d 0, x 6 \u003d 3/2, т.е. четвъртото валидно решение (0; 5; 3/2; 0; 0; 3/2). В този случай Ф 4 \u003d 5/4.

Сега вземаме x 1, x 4 и x 5 като нови свободни променливи. Нека изразим нови основни променливи x 2 , x 3 , x 6 чрез тях. Да вземем системата

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Целевата функция ще приеме формата

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Коефициентите и на двете променливи в израза за Ф са положителни, следователно по-нататъшно намаляване на стойността на Ф е невъзможно.

Тоест минималната стойност на Ф min = - 5, последното възможно решение (0; 5; 3/2; 0; 0; 3/2) е оптимално.

Вариант 8. Максимизиране на целевата функция Ф = 4 x 5 + 2 x 6

с ограничения: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Решение:

Броят на уравненията е 4, броят на неизвестните е 6. Следователно r = n - m = 6 - 4 = 2 променливи могат да бъдат избрани като свободни, 4 променливи като основни. Избираме x 5 и x 6 като безплатни, x 1, x 2, x 3, x 4 като основни. Изразяваме основните променливи чрез свободните и редуцираме системата от уравнения до единица

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Записваме целевата функция във вида Ф = 4 x 5 + 2 x 6 . Присвояваме нулеви стойности на свободни променливи x 5 = x 6 = 0. В този случай основните променливи ще приемат стойностите x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , тоест ще получим първото допустимо решение (12, 30 , 6, 9, 0,) и Ф 1 = 0.

И двете свободни променливи влизат в целевата функция с положителни коефициенти, тоест е възможно по-нататъшно увеличение на F. Нека преведем, например, x 6 в броя на основните. Уравнение (1) показва, че x 1 = 0 при x 5 = 12, в (2) ÷ (4) x 6 влиза с положителни коефициенти. Нека преминем към нова основа: основни променливи - x 6, x 2, x 3, x 4, свободни - x 1, x 5. Нека изразим новите основни променливи чрез нови свободни

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

Целевата функция ще приеме формата Ф = 24 - 2 x 1 + 2 x 5 ;

Присвояваме нулеви стойности на свободни променливи x 1 = x 5 = 0. В този случай основните променливи ще приемат стойностите x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , тоест ще получим второто допустимо решение (0, 42 , 30, 21, 0, 12) и Ф 2 = 24.

Целевата функция x 5 влиза с положителен коефициент, тоест е възможно по-нататъшно увеличение на F. Да преминем към нова основа: основни променливи - x 6, x 5, x 3, x 4, свободни - x 1 , x 2. Нека изразим нови основни променливи чрез new free

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Целевата функция ще приеме формата Ф = 38 - 7/2 x 1 - 1/3 x 2;

Задайте нулеви стойности на свободни променливи x 1 = x 2 = 0. В този случай основните променливи ще приемат стойностите x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, тоест ще получим третото допустимо решение X 3 = (0, 0, 9, 7/2, 7, 5) и Ф 3 = 38.

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

Следователно последното възможно решение е оптимално, т.е. Х opt = (0, 0, 9, 7/2, 7, 5) и Ф max = 38.

Вариант 10. Максимизирайте целевата функция Ф \u003d x 2 + x 3

при ограничения: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Решение:

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

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

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

Целевата функция вече е изразена чрез x 2 и x 3 , тоест Ф = x 2 + x 3 .

При x 2 \u003d 0 и x 3 \u003d 0, основните променливи ще бъдат равни на x 1 = 1, x 4 \u003d 2.

Имаме първото допустимо решение X 1 = (1, 0, 0, 2), докато Ф 1 = 0.

Увеличаване на Ф е възможно с увеличаване например на стойността на x 3, която се включва в израза за Ф с положителен коефициент (x 2 остава равен на нула). В първото уравнение на системата (*) се вижда, че x 3 може да се увеличи до 1 (от условието x 1 ³0), тоест това уравнение налага ограничение за увеличаване на стойността на x 3. Първото уравнение на системата (*) е разрешаващо. На базата на това уравнение преминаваме към нова основа, променяйки x 1 и x 3 места. Сега основните променливи ще бъдат x 3 и x 4, свободните - x 1 и x 2. Сега изразяваме x 3 и x 4 чрез x 1 и x 2.

Получаваме: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Приравнявайки свободните променливи на нула, получаваме второто допустимо базисно решение X 2 = (0; 0; 1; 4), в което Ф 2 =1.

Възможно е увеличение на F с увеличение на x 2. Увеличението е същото х 2, съдейки по най-нова системауравнения (**), неограничен. Следователно Ф ще вземе всички големи положителни стойности, тоест Ф max = + ¥.

Така че целевата функция Ф не е ограничена отгоре, така че няма оптимално решение.

ЗАДАЧА 2.Г. Напишете задача, двойна на дадената.

първоначален проблем.

Вариант 7. Максимизиране на целевата функция Ф = 2× x 1 - x 4

с ограничения: x 1 + x 2 \u003d 20,

х 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Решение:

Ние привеждаме системата от ограничения до единична, например канонична форма, като въвеждаме допълнителни променливи във 2-ро и 3-то уравнения

x 1 + x 2 = 20,

х 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

Имаме асиметрична задача от 2-ри тип. Двойният проблем ще изглежда така:

Минимизиране на целевата функция F = 20 × y 1 + 5 × y 2 + 8 × y 3

за y 1 — y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Вариант 8. Максимизирайте целевата функция Ф \u003d x 2 - x 4 - 3× х 5

с ограничения: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (аз = 1, 6)

Решение:

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

Първоначален проблем: Двоен проблем:

F = C × X max F = B T × Имин

при А × X \u003d B в A T × Y ≥ C T

В оригиналната задача матрицата-ред от коефициенти за променливи в целевата функция има формата С = (0; 1; 0; -1; -3; 0),

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

B \u003d 2, A \u003d 0 - 4 1 2 -1 0

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

0 1 0 0 V T \u003d (1; 2; 5)

A T = -1 2 0 C T = -1

Двойният проблем може да бъде написан в следната форма:

намерете минималната стойност на целевата функция F = y 1 + 2 × y 2 + 5 × y 3

при ограничения y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Вариант 10. Минимизирайте функцията Ф = x 1 + x 2 + x 3

ограничено: 3× х 1 + 9× х 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Решение:

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

Първоначален проблем Двойна задача

F = C × X min F \u003d B T × Ymax

при А × х ≥ B в A T × Y ≤ C T

X ≥ 0 Y ≥ 0

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

C \u003d (1; 1; 1), B \u003d 3, A = 6 4 5

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

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Двойният проблем се формулира така:

Максимизиране на целевата функция F = 2y 1 + 3y 2 + 4y 3

под ограничения 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

ЗАДАЧА 2.В. Решаване на задача за линейно програмиране с помощта на симплексни таблици.

Вариант 7. Максимизиране на целевата функция Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

при ограничения: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Решение:

Ние свеждаме системата от ограничения до каноничната форма

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Имаме система от 3 уравнения със 7 неизвестни. Избираме x 1 , z 1 , z 3 като основни 3 променливи, x 2 , x 3 , x 4 , z 2 като свободни, изразяваме основните променливи чрез тях.

От (2) имаме x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Заместете в (1) и (3), получаваме

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

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

I итерация Таблица 1

Основен AC	Свободата. AC
х 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
Е	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II итерация Таблица 2

х 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
Е	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III итерация Таблица 3

х 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
х 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
Е	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

IV итерация Таблица 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
х 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
Е	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.

В индексния ред последната масаНе отрицателни числа, тоест в израза за целевата функция всички Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Отговор: Ф max = 149/14,

оптимално решение (0; 0; 25/14; 37/14; 1/2; 0; 0)

Вариант 8. Минимизиране на целевата функция Ф = 5 x 1 - x 3

при ограничения: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Решение:

Броят на променливите е 4, рангът на матрицата е ​​2, следователно броят на свободните променливи е r \u003d 4 - 2 \u003d 2, броят на основните променливи също е 2. Взимаме x 3, x 4 като свободни променливи, ние ще изразим основните променливи x 1, x 2 по отношение на свободните и привеждаме системата към базисната единица:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Записваме системата от уравнения и целевата функция във форма, удобна за симплексната таблица, т.е. x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ф + 11 х 3 - 15 х 4 \u003d 10

Да направим маса

I итерация Таблица 1

Основен AC	Свободата. AC
x1	2	1	0		— 3		1/2
x2	1	0	1	0	2
Е	10	0	0	11	— 15		— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

II итерация Таблица 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
Е	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

III итерация Таблица 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
Е	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

Няма последна таблица в индексния ред положителни числа, тоест в израза за целевата функция всички Г i > 0. Имаме случай I, следователно последното основно решение е оптимално.

Отговор: Ф min = -7/4, оптимално решение (0; 0; 7/4; 1/2)

********************

Вариант 10. Минимизирайте целевата функция Ф \u003d x 1 + x 2,

с ограничения: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Решение:

Броят на променливите е 5, рангът на матрицата е ​​3, следователно броят на свободните променливи е r \u003d 6-3 \u003d 2. Взимаме x 3 и x 4 като свободни променливи, x 1, x 2, x 5 като основни. Всички уравнения на системата вече са сведени до една основа (основните променливи са изразени чрез свободни), но са написани във форма, която не е удобна за използване на симплексни таблици. Записваме системата от уравнения във формата

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

x 5 + x 3 - x 4 . = 5

Изразяваме целевата функция чрез свободни променливи и я записваме във формата Ф - 3 x 3 +3 x 4 = 3

Да направим маса

I итерация Таблица 1

Основен AC	Свободата. AC
х 1	2	1	0	-2	1	0	2	-1/2
х 2	1	0	1	-1		0	1/2	1/2
х 5	5	0	0	1	-1	1		1/2
Е	3	0	0	-3	3	0		-3/2

X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.

таблица 2

х 1	3/2	1	-1/2	-3/2	0	0
х 4	1/2	0	1/2	-1/2	1	0
х 5	11/2	0	1/2	1/2	0	1
Е	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.

В индексния ред на последната таблица няма положителни числа, т.е. в израза за целевата функция всички Гi > 0. Имаме случай 1, следователно последното основно решение е оптимално.

Отговор: Ф min = 3/2, оптималното решение е (3/2; 0; 0; 1/2; 11/2).

Решение: намерете максималната и минималната стойност на функцията \(f (x, y)\) при следните ограничения $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
Графичен начинЦелесъобразно е да се използва решението на задачата за задачи с две променливи, които са записани в симетрична форма, както и за задачи с много променливи, при условие че тяхната канонична нотация съдържа не повече от две свободни променливи.

AT този случайзадача с две променливи.

Алгоритъм за решаване на задачата "геометрична интерпретация на задача за линейно програмиране":

1. Да построим областта на допустимите решения на равнината xOy.
2. Изберете областта на неотрицателните решения.

4. Нека построим семейство от целеви функции.
5. Намерете максималната (минималната) стойност на целевата функция.

1. Конструираме областта на допустимите решения на задачата \(D\).

За да изградите областта на осъществимите решения:
1) Изграждаме гранични линии:
преобразуваме неравенствата в равенства и след това в уравнение на права линия в сегменти по осите на формата \(\frac(x)(a)+\frac(y)(b) = 1\), тогава \ (x=a\) е сегмент, отрязан по оста Ox, \(y=b\) - по оста Oy $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ За всяка линия отделете сегменти на осите и ги свържете. Имаме правилните линии.

2) Намираме полуравнини, които удовлетворяват дадените неравенства:
За неравенството \(2x+3y\geq 6\) е полуравнината, която лежи над правата \(2x+3y = 6\). Директен климатик
За неравенството \(3x-2y\leq 18 => -3x+2y \geq -18\) е полуравнина, която лежи над правата \(3x-2y = 18\). Директен CB
За неравенството \(-x+2y\leq 8\) е полуравнината, която лежи под правата \(-x+2y = 8\). Директен АВ

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

Регионът \(D\) е триъгълникът \(ABC\), вижте фиг.

2. Изберете областта на неотрицателните решения.

Зоната на неотрицателните решения се намира в първата четвърт и е обща частот всичките пет полуравнини, три от които са областта \(D\), получена от неравенства и допълнително две неравенства \(x \geq 0\) - горната полуравнина (I и II четвърти) и \(y \ geq 0\) - дясната полуравнина (I и IV четвърти), които изразяват условието за неотрицателност на променливите \(x;y\). Получена е желаната област на неотрицателни решения \(DEBFG\)

3. Намерете координатите на върховете на областта.
Координатите на четирите върха вече са известни (това са точките на пресичане на правите с осите).
Нека запишем тези координати:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Намерете координатите на точката \(B\), като точки на пресичане на правите \(-x+2y = 8\) и \(3x-2y = 18\). Решете системата от уравнения и намерете координатите на тази точка $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
Получихме координатите на точката \(B(13;10.5)\)

4. Изграждаме семейство от целеви функции.
Уравнението \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) определя в равнината xOy семейство от концентрични окръжности с център в точка с координати \ (Q(4 ;3)\), всеки от които съответства определена стойностпараметър \(f\). Както знаете, за уравнението на окръжност параметърът \(f=R^2\).

Нека представим в една и съща координатна система семейство от концентрични окръжности \(f\) и семейство от прави. Проблемът за определяне на точката на максимум (минимум) на точката \(f\) ще бъде намален до намиране в допустима площточката, през която минава окръжността на семейството \(f=const\), което отговаря за най-голямата (най-малката) стойност на параметъра \(f\).

5. Намерете максималната (минималната) стойност на целевата функция.

Минимална стойност на целевата функция: начин постепенно нарастванерадиус на окръжността, получаваме, че първият връх, през който минава окръжността, е точката \(G(3;0)\). Целевата функция в този момент ще бъде минимална и равна на \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Максималната стойност на целевата функция: Чрез допълнително увеличаване на радиуса на окръжността, ние получихме, че последният връх, през който окръжността ще премине, е точката \(B(13;10.5)\). Целевата функция в тази точка ще бъде максимална и равна на \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

Можете да проверите правилността на решението, като замените координатите на останалите върхове в уравнението на целевата функция:
във върха \(D(0;2)\) стойността на целевата функция е равна на \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
във върха \(E(0;4)\) стойността на целевата функция е равна на \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
във върха \(F(6;0)\) стойността на целевата функция е \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Разбрах това

Отговор:
минималната стойност на целевата функция \(f_(min) = 10\)
максималната стойност на целевата функция \(f_(max) = 137,25\)

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

F= 2х 1 + 3х 2 ® макс

С ограничения

Решениекато се използва Excel таблици

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

Разгледайте първото неравенство.

Нека построим гранична линия от две точки. Обозначете линията с (L1) (или Ред1). Координати х 2 броим по формулите:

За да изградите, изберете точкова диаграма

Избор на данни за права линия

Променете името на реда:

Изберете оформление на диаграма. Променете името на координатните оси:

Права линия (L1) на графиката:

Решението на строгото неравенство може да се намери с помощта на една тестова точка, която не принадлежи на правата (L1). Например, използвайки точката (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

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

След това решаваме неравенство (2) .

Нека построим граничната линия 2 от две точки. Означаваме правата с (L2).

Права линия (L2) на графиката:

Решението на строго неравенство 2 може да бъде намерено с помощта на единствената тестова точка, която не принадлежи на правата (L2). Например, използвайки точката (0; 0)W(L2).

Замествайки координатите на точката (0; 0), получаваме неравенството

2 × 0 + 0< 16 или 0 < 16 .

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

След това решаваме неравенство (3) .

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

Права линия (L3) на графиката:

Решението на строго неравенство 2 може да бъде намерено с помощта на единствената тестова точка, която не принадлежи на правата (L3). Например, използвайки точката (0; 0)W(L3).

Замествайки координатите на точката (0; 0), получаваме неравенството

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

След това решаваме неравенство (4) .

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

Добавете данни към Excel лист

Права линия (L4) на графиката:

Решение на строго неравенство 3 х 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Замествайки координатите на точката (0; 0), получаваме неравенството

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

Чрез решаване на две неравенства (5) и (6)

е 1-вата четвърт, ограничена от координатните линии и .

Системата от неравенства е решена. Чрез решаване на системата от неравенства (1) - (6) в този примере изпъкнал многоъгълник в долния ляв ъгъл на фигурата, ограничен от линии L1, L2, L3, L4 и координатни линии и . Можете да се уверите, че многоъгълникът е избран правилно, като замените тестова точка, например (1; 1) във всяко неравенство на оригиналната система. Заменяйки точката (1; 1), получаваме, че всички неравенства, включително естествените ограничения, са верни.

Помислете сега за целевата функция

F= 2х 1 + 3х 2 .

Нека изградим линии на ниво за стойностите на функцията F=0и F=12 (числови стойностиизбран произволно). Добавете данни към Excel лист

Линии на ниво на диаграмата:

Нека построим вектор от посоки (или градиент) (2; 3). Координатите на вектора съвпадат с коефициентите на целевата функция Е.