Розв'язання задачі лінійного програмування. Знайти екстремуми функції графічним методом
Цільова функція- речова або цілочисленна функція кількох змінних, що підлягає оптимізації (мінімізації або максимізації) з метою вирішення певної оптимізаційної задачі. Термін використовується в математичному програмуванні, дослідженні операцій, лінійному програмуванні, теорії статистичних рішеньта інших галузях математики в першу чергу прикладного характеру, хоча метою оптимізації може бути рішення власне математичної задачі. Крім цільової функції задачі оптимізації для змінних можуть бути задані обмеження у вигляді системи рівностей або нерівностей. У загальному випадкуаргументи цільової функції можуть задаватися на довільних множинах.
Приклади
Гладкі функції та системи рівнянь
Завдання розв'язання будь-якої системи рівнянь
( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\right.)
може бути сформульована як завдання мінімізації цільової функції
S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad (1))
Якщо функції гладкі, завдання мінімізації можна вирішувати градієнтними методами.
Для будь-якої гладкої цільової функції можна прирівняти до 0 (displaystyle 0) приватні похідні по всіх змінних. Оптимум цільової функції буде одним із рішень такої системи рівнянь. У разі функції (1) (\displaystyle (1)) це буде система рівнянь методу найменших квадратів(МНК). Будь-яке рішення вихідної системи є рішенням системи МНК. Якщо вихідна система несумісна, то система МНК, що завжди має рішення, дозволяє отримати наближене рішення вихідної системи. Число рівнянь системи МНК збігається з числом невідомих, що іноді полегшує і вирішення спільних вихідних систем.
Лінійне програмування
Іншим відомим прикладомцільової функції є лінійна функція, яка виникає в задачах лінійного програмування. На відміну від квадратичної цільової функції оптимізація лінійної функції можлива лише за наявності обмежень як системи лінійних рівностей чи нерівностей.
Комбінаторна оптимізація
Типовим прикладом комбінаторної цільової функції є цільова функція завдання комівояжера. Ця функція дорівнює довжині гамільтонового циклу на графі. Вона задана на безлічі перестановок n − 1 (displaystyle n-1) вершини графа і визначається матрицею довжин ребер графа. Точне вирішення подібних завдань часто зводиться до вибору варіантів.
Глава 1. Постановка основного завдання лінійного програмування
Лінійне програмування
Лінійне програмування – це напрямок математичного програмування, що вивчає методи вирішення екстремальних завдань, що характеризуються лінійною залежністюміж змінними та лінійним критерієм. Такі завдання знаходять великі програми в різних сферахлюдської діяльності. Систематичне вивчення завдань такого типу почалося у 1939 – 1940 роках. у роботах Л.В. Канторович.
До математичних завдань лінійного програмування відносять дослідження конкретних виробничо-господарських ситуацій, які в тому чи іншому вигляді інтерпретуються як задачі оптимальному використанніобмежених ресурсів.
Коло завдань, що вирішуються за допомогою методів лінійного програмування, досить широке. Це, наприклад:
завдання про оптимальне використання ресурсів під час виробничого планування;
завдання про суміші (планування складу продукції);
завдання про знаходження оптимальної комбінації різних видівпродукції для зберігання на складах (управління товарно-матеріальними запасами чи);
транспортні завдання (аналіз розміщення підприємства, переміщення вантажів).
Лінійне програмування – найбільш розроблений та широко застосовуваний розділ математичного програмування (крім того, сюди відносять: ціле чисельне, динамічне, нелінійне, параметричне програмування). Це пояснюється так:
математичні моделі великої кількості економічних завданьлінійні щодо шуканих змінних;
даний тип завдань у час найбільш вивчений. Для нього розроблені спеціальні методи, за допомогою яких ці завдання вирішуються, та відповідні програми для ЕОМ;
багато завдань лінійного програмування, будучи вирішеними, знайшли широке застосування;
деякі завдання, які в початковому формулюванні не є лінійними, після низки додаткових обмежень і припущень можуть стати лінійними або можуть бути приведені до такої форми, що можна вирішувати методами лінійного програмування.
Економіко-математична модель будь-якого завдання лінійного програмування включає: цільову функцію, оптимальне значення якої (максимум або мінімум) потрібно знайти; обмеження у вигляді системи лінійних рівняньчи нерівностей; вимога невід'ємності змінних.
У загальному виглядімодель записується так:
цільова функція
(1.1) при обмеженнях
(1.2) вимоги невід'ємності
(1.3) де x j- Змінні (невідомі);
- Коефіцієнти завдання лінійного програмування.
Завдання полягає у знаходженні оптимального значення функції (1.1) при дотриманні обмежень (1.2) та (1.3).
Систему обмежень (1.2) називають функціональними обмеженнями завдання, а обмеження (1.3) – прямими.
Вектор, що відповідає обмеженням (1.2) і (1.3), називається допустимим рішенням (планом) завдання лінійного програмування. План, у якому функція (1.1) досягає свого максимального (мінімального) значення, називається оптимальним.
1.2. Симплекс метод вирішення задач лінійного програмування
Симплекс-метод був розроблений і вперше застосований для вирішення завдань 1947 р. американським математиком Дж. Данцигом.
Двовимірні завдання лінійного програмування вирішуються графічно. Для випадку N=3 можна розглянути тривимірний простір і цільова функція досягатиме своє оптимальне значення в одній з вершин багатогранника.
Допустимим рішенням (допустимим планом) завдання ЛП, даної в стандартній формі, називається впорядкована множина чисел (х1, х2, ..., хn), що задовольняють обмеженням; це точка в n-мірному просторі.
Багато допустимих рішень утворює область допустимих рішень (ОДР) задачі ЛП. ОДР є опуклим багатогранником (багатокутником).
У загальному вигляді, коли в задачі беруть участь N-невідомих, можна сказати, що область допустимих рішень, що задається системою обмежувальних умов, видається опуклим багатогранником в n-мірному просторі і оптимальне значення цільової функції досягається в одній або декількох вершинах.
Базисним називається рішення, у якому всі вільні змінні дорівнюють нулю.
Опорне рішення - це базове невід'ємне рішення. Опорне рішення може бути невиродженим та виродженим. Опорне рішення називається невиродженим, якщо число його ненульових координат дорівнює рангу системи, інакше воно є виродженим.
Допустиме рішення, при якому цільова функція досягає свого екстремального значення, називається оптимальним і позначається 
.
Вирішити ці завдання графічно, коли кількість змінних більше 3 дуже важко. Існує універсальний спосіб розв'язання задач лінійного програмування, що називається симплекс-методом.
Симплекс-метод - це універсальний методвирішення завдань ЛП, що є ітераційний процес, який починається з одного рішення і в пошуках кращого варіанту рухається по кутових точках області допустимих рішень до тих пір, поки не досягне оптимального значення.
З його допомогою можна вирішити будь-яку задачу лінійного програмування.
В основу симплексного методу покладено ідею послідовного поліпшення одержуваного рішення.
Геометричний зміст симплексного методу полягає в послідовному переході від однієї вершини багатогранника обмежень до сусідньої, в якій цільова функція набуває кращого (або принаймні не гіршого) значення доти, доки не буде знайдено оптимальне рішення - вершина, де досягається оптимальне значення функції мети (якщо завдання має кінцевий оптимум).
Таким чином, маючи систему обмежень, наведену до канонічної форми (всі функціональні обмеження мають вигляд рівностей), знаходять будь-яке базисне рішення цієї системи, дбаючи лише про те, щоб знайти його якомога простіше. Якщо перше знайдене базисне рішення виявилося допустимим, то перевіряють його на оптимальність. Якщо воно не оптимальне, здійснюється перехід до іншого, обов'язково допустимого базисного рішення. Симплексний метод гарантує, що при цьому новому рішенні цільова функція, якщо і не досягне оптимуму, то наблизиться до нього (або принаймні не відійде від нього). З новим допустимим базовим рішенням надходять так само, поки не знайдеться рішення, яке є оптимальним.
Процес застосування симплексного методу передбачає реалізацію трьох його основних елементів:
спосіб визначення будь-якого початкового допустимого базового рішення задачі;
правило переходу на краще (точніше, не гіршому) рішенню;
критерій перевірки оптимальності знайденого рішення.
Симплексний метод включає ряд етапів і може бути сформульований у вигляді чіткого алгоритму (чіткого припису про виконання послідовних операцій). Це дозволяє успішно програмувати та реалізовувати його на ЕОМ. Завдання з невеликою кількістю змінних та обмежень можуть бути вирішені симплексним методом вручну.
6.1.
Оптимізація. Частина 1
Методи оптимізації дозволяють вибрати найкращий варіантконструкції з усіх можливих варіантів. У Останніми рокамицим методам приділялася велика увага, і в результаті було розроблено цілий рядвисокоефективних алгоритмів, що дозволяють знайти оптимальний варіантконструкції за допомогою ЕЦОМ. У цьому розділі викладаються основи теорії оптимізації, розглядаються принципи, що лежать в основі побудови алгоритмів оптимальних рішень, описуються найбільш відомі алгоритми, аналізуються їх переваги та недоліки.
6.2.Основи теорії оптимізації
Терміном «оптимізація» у літературі позначають процес чи послідовність операцій, що дозволяють отримати уточнене рішення. Хоча кінцевою метоюОптимізації є відшукання найкращого, чи «оптимального», рішення, зазвичай доводиться задовольнятися поліпшенням відомих рішень, а чи не доведенням їх до досконалості. Тому під оптимізацією розуміють скоріше прагнення досконалості, яке, можливо, й не буде досягнуто.
Розглядаючи деяку довільну систему, що описується m рівняннями з n невідомими, можна виділити три основні типи завдань. Якщо m=n, завдання називають алгебраїчною. Таке завдання зазвичай має одне рішення. Якщо m>n, то завдання перевизначено і, зазвичай, немає рішення. Зрештою, при m
Перш ніж розпочати обговорення питань оптимізації, введемо низку визначень.
Проектні параметри
Цим терміном позначають незалежні змінні параметри, які повністю і однозначно визначають завдання проектування, що вирішується. Проектні параметри - невідомі величини, значення яких обчислюються у процесі оптимізації. В якості проектних параметрів можуть служити будь-які основні або похідні величини, що служать для кількісного опису системи. Так, це можуть бути невідомі значення довжини, маси, часу, температури. Число проектних параметрів характеризує ступінь складності даної задачі проектування. Зазвичай число проектних параметрів позначають через n, а самі проектні параметри через x з відповідними індексами. Таким чином n проектних параметрів даної задачі будемо позначати через
X1, x2, x3, ..., xn.
Цільова функція
Це вираз, значення якого інженер прагне зробити максимальним або мінімальним. Цільова функція дозволяє кількісно порівняти два альтернативні рішення. З математичної погляду цільова функція описує деяку (n+1) - мірну поверхню. Її значення визначається проектними параметрами
M = M (x 1, x 2, ..., x n).
Прикладами цільової функції, які часто зустрічаються в інженерній практиці, є вартість, вага, міцність, габарити, ККД. Якщо є лише один проектний параметр, то цільову функцію можна подати кривою на площині (рис.6.1). Якщо проектних параметрів два, то цільова функція зображуватиметься поверхнею у просторі трьох вимірів (рис.6.2). При трьох і більше проектних параметрах поверхні, що задаються цільовою функцією, називаються гіперповерхнями і не піддаються обра-
ження звичайними засобами. Топологічні властивості поверхні цільової функції відіграють велику рольу процесі оптимізації, оскільки від них залежить вибір найефективнішого алгоритму.
Цільова функція в ряді випадків може набувати найнесподіваніших форм. Наприклад, її не завжди вдається висловити в
Рис.1.Одномірна цільова функція.
Рис.6.2.Двовимірна цільова функція.
замкненою математичної форми, в інших випадках вона може
являти собою шматково-гладку функцію. Для завдання цільової функції іноді може бути потрібна таблиця технічних даних (наприклад, таблиця стану водяної пари) або може знадобитися провести експеримент. У ряді випадків проектні параметри набувають лише цілі значення. Прикладом може бути кількість зубів у зубчастій передачі або число болтів у фланці. Іноді проектні параметри мають лише два значення - так чи ні. Якісні параметри, такі як задоволення, яке відчуває покупець, що набув виріб, надійність, естетичність, важко враховувати в процесі оптимізації, тому що їх практично неможливо охарактеризувати кількісно. Однак у якому б вигляді не було представлено цільову функцію, вона має бути однозначною функцією проектних параметрів.
У низці завдань оптимізації потрібно введення більше однієї цільової функції. Іноді одна з них може виявитися несумісною з іншою. Прикладом є проектування літаків, коли одночасно потрібно забезпечити максимальну міцність, мінімальну вагу та мінімальну вартість. У таких випадках конструктор повинен ввести систему пріоритетів і поставити у відповідність кожної цільової функції деякий безрозмірний множник. В результаті з'являється «функція компромісу», що дозволяє в процесі оптимізації користуватися однією складовою цільовою функцією.
Пошук мінімуму та максимуму
Одні алгоритми оптимізації пристосовані для пошуку максимуму, інші – для пошуку мінімуму. Однак незалежно від типу розв'язуваної задачі на екстремум можна користуватися одним і тим же алгоритмом, так як задачу мінімізації можна легко перетворити на задачу на пошук максимуму, змінивши знак цільової функції на зворотний. Цей прийом ілюструється рис.6.3.
Простір проектування
Так називається область, яка визначається усіма n проектними параметрами. Простір проектування не настільки великий, як може здатися, оскільки він зазвичай обмежений поруч
умов, пов'язаних з фізичною сутністюзавдання. Обмеження можуть бути настільки сильними, що завдання не матиме жодного
Рис.6.3.Зміною знака цільової функції на протилежний
завдання на максимум перетворюється на завдання на мінімум.
задовільного рішення. Обмеження поділяються на дві групи: обмеження – рівності та обмеження – нерівності.
Обмеження – рівності
Обмеження – рівності – це залежність між проектними параметрами, які мають враховуватися при знайденні рішення. Вони відображають закони природи, економіки, права, панівні смаки та наявність необхідних матеріалів. Число обмежень – рівностей може бути будь-яким. Вони мають вигляд
C 1 (x 1 x 2, ..., x n) = 0,
C 2 (x 1 x 2 ..., x n) = 0,
..................
C j (x 1 x 2 ... x n) = 0.
Якщо якесь із цих співвідношень можна дозволити щодо одного з проектних параметрів, це дозволяє виключити даний параметр з процесу оптимізації. Тим самим зменшується кількість вимірювань простору проектування та спрощується розв'язання задачі.
Обмеження – нерівності
Це особливий вид обмежень, виражених нерівностями. У загальному випадку їх може бути скільки завгодно, причому всі вони мають вигляд
z 1 r 1 (x 1 , x 2, ..., x n) Z 1
z 2 r 2 (x 1, x 2, ..., x n) Z 2
.......................
z k r k (x 1, x 2, ..., x n) Z k
Слід зазначити, що дуже часто через обмеження оптимальне значення цільової функції досягається не тим, де її поверхня має нульовий градієнт. Нерідко краще рішеннявідповідає одній з меж області проектування.
Локальний оптимум
Так називається точка простору проектування, в якій цільова функція має найбільше значення, порівняно з її значеннями у всіх інших точках її найближчого околиці.
Довільна цільова функція може мати декілька
локальних оптимумів.
На рис. 6.4 показана одновимірна цільова функція, що має два локальні оптимуми. Часто простір проектування містить багато локальних оптимумів і слід бути обережними, щоб не прийняти перший з них за оптимальне рішення завдання.
Глобальний оптимум
Глобальний оптимум – це оптимальне рішення для всього простору проектування. Воно краще за всіх інших рішень, що відповідають локальним оптимумам, і саме його шукає конструктор. Можливий випадок кількох рівних глобальних оптимумів, розташованих у різних частинахпростору проектування. Як ставиться завдання оптимізації, найкраще показати з прикладу.
Приклад 6.1
Нехай потрібно спроектувати прямокутний контейнер об'ємом 1м, призначений для перевезення невпакованого волокна. Бажано, щоб виготовлення таких контейнерів витрачалося як можна менше матеріалу(За умови постійності товщини стінок це означає, що площа поверхні повинна бути мінімальною), так як при цьому він буде дешевше. Щоб контейнер було зручно брати автонавантажувачем, його ширина повинна бути не менше 1,5м.
Сформулюємо це завдання у вигляді, зручному застосування алгоритму оптимізації.
Проектні параметри: x 1, x 2, x 3.
Цільова функція (яку потрібно мінімізувати) - площа бічної поверхні контейнера:
A = 2 (x 1 x 2 + x 2 x 3 + x 1 x 3), м2.
Обмеження - рівність:
Об'єм = x 1 x 2 x 3 = 1м3.
Обмеження - нерівність:
Завдання лінійного програмування
Лінійне програмування (ЛП)є одним із розділів математичного програмування – дисципліни, що вивчає екстремальні (оптимізаційні) завдання та розробку методів їх вирішення.
Оптимізаційне завдання– це математична задача, що полягає у знаходженні оптимального (тобто максимального або мінімального) значення цільової функції, причому значення змінних повинні належати певній області допустимих значень(ОДЗ).
У загальному вигляді постановка екстремальної задачі математичного програмування полягає у визначенні найбільшого чи найменшого значенняфункції , званої цільовою функцією, за умов (обмеження), де і – задані функції, а - задані постійні величини. При цьому обмеження у вигляді рівностей та нерівностей визначають безліч (область) допустимих рішень (ОДР), а називають проектними параметрами.
Залежно від виду функцій та завдання математичного програмування поділяються на ряд класів (лінійне, нелінійне, опукле, цілочисленне, стохастичне, динамічне програмування та ін.).
У загальному виглядізавдання ЛП має наступний вид:
, (5.1)
, , (5.2)
, 
, (5.3)
де , , – задані постійні величини.
Функцію (5.1) називають цільовою функцією; системи (5.2), (5.3) – системою обмежень; умова (5.4) – умовою невід'ємності проектних властивостей.
Сукупність проектних параметрів, що задовольняють обмеженням (5.2), (5.3) та (5.4), називають допустимим рішеннямабо планом.
Оптимальним рішенням або оптимальним планом Завдання ЛП називається допустиме рішення , при якому цільова функція (5.1) набуває оптимального (максимальне або мінімальне) значення.
Стандартним завданнямЛП називають завдання знаходження максимального (мінімального) значення цільової функції (5.1) за умови (5.2) та (5.4), де , , тобто. тобто. обмеження лише у вигляді нерівностей (5.2) та всі проектні параметри задовольняють умові невід'ємності, а умови у вигляді рівностей відсутні:
,
, , (5.5)
.
Канонічним (основним) завданнямЛП називають завдання знаходження максимального (мінімального) значення цільової функції (5.1) за умови (5.3) та (5.4), де , , тобто. тобто. обмеження лише у вигляді рівностей (5.3) та всі проектні параметри задовольняють умові невід'ємності, а умови у вигляді нерівностей відсутні:
,
.
Канонічну задачу ЛП можна також записати в матричній та векторній формі.
Матрична форма канонічної задачі ЛП має такий вигляд:
Векторна форма канонічного завдання ЛП.
Лабораторна робота № 1. Розв'язання задач лінійного програмування
Мета роботиОтримання навички вирішення задач лінійного програмування графічним, симплексним методом та засобами Excel.
Завдання лінійного програмування полягає у вивченні способів відшукання максимального чи мінімального значень лінійної функції за наявності лінійних обмежень. Цільовою функцією називається функція, максимальне чи мінімальне значення якої. Сукупність значень змінних, у яких досягається максимальне чи мінімальне значення, називається оптимальним рішенням (оптимальним планом), будь-яка інша сукупність значень, яка б обмеженням, називається допустимим рішенням (допустимим планом).
Геометричний метод розв'язано яЗавдання лінійного програмування розглянемо з прикладу.
приклад. Знайти максимальне значення цільової функції L=2x 1 +2x 2 при заданих обмеженнях
Рішення.Побудуємо область рішень системи обмежень, змінюючи знаки нерівностей на знаки точних рівностей:
l 1: 3x 1 -2x 2 +6=0,
l 2: 3x 1 +x 2 -3=0,
l 3:x 1 -3=0.
DЗ
2 0 1 3 х 1
(l 1) (l 3)
Пряма l 1 ділить площину хПро уна дві напівплощини, з яких потрібно вибрати одну, що задовольняє першу нерівність у системі (3). І тому візьмемо т. Про(0; 0) і підставимо у нерівність. Якщо воно вірне, то потрібно заштрихувати ту напівплощину від прямої, в якій знаходиться т.п. Про(0; 0). Аналогічно надходять із прямими l 2 та l 3 . Областью розв'язків нерівностей (3) є багатокутник АВСD. Для кожної точки площини функція Lнабуває фіксованого значення L=L 1 . Безліч всіх токах точок є пряма L=c 1 x 1 +c 2 x 2 (у нашому випадку L=2x 1 +2x 2), перпендикулярна вектору З(з 1 ;з 2) (З(2; 2)), що виходить із початку координат. Якщо цю пряму переміщати у позитивному напрямку вектора з, то цільова функція Lзростатиме, у протилежному випадку буде спадати. Таким чином, у нашому випадку, пряма при виході з багатокутника АВСDрішень пройде через т.п. У(3; 7,5), тому у т.ч. Уцільова функція набуває максимального значення, тобто. L max =2?3+2?7,5=21. Аналогічно визначається, що мінімальне значення функція набирає в т.ч. D(1; 0) та L min =2?1+2?0=2.
Алгоритм симплексного методу розв'язання задачі лінійного програмування полягає в наступному.
1. Загальне завданнялінійного програмування зводиться до канонічної задачі (в обмеженнях стоять знаки рівності) запровадженням стільки допоміжних змінних, скільки нерівностей містить система обмежень.
2. Функція мети виражається через базисні та допоміжні змінні.
3. Складається перша симплекс-таблиця. У базис записуються змінні, щодо яких дозволено систему обмежень (найкраще за базисні прийняти допоміжні змінні). У першому рядку таблиці перераховуються всі змінні і відводиться стовпець для вільних членів. В останній рядок таблиці записують коефіцієнти функції цілі із протилежними знаками
4. Кожна симплекс-таблиця дає рішення задачі лінійного програмування: вільні змінні дорівнюють нулю, базисні змінні рівні відповідно вільним членам.
5. Критерієм оптимальності є відсутність негативних елементів в останньому рядку таблиці для вирішення задачі на максимум та позитивних елементів на мінімум.
6. Для покращення рішення необхідно від однієї симплекс-таблиця перейти до іншої. Для цього в попередній таблиці знаходять ключовий стовпець, що відповідає найменшому негативному елементу в останньому рядку таблиці в задачі на максимум і найбільший позитивний коефіцієнт задачі на мінімум. Потім знаходять ключовий рядок, що відповідає мінімальному відношенню вільних членів до відповідних позитивних елементів ключового стовпця. На перетині ключового стовпця та ключового рядка знаходиться ключовий елемент.
7. Заповнення наступної симплекс-таблиці починаємо із заповнення базису: з базису виводиться змінна, що відповідає ключовому рядку, і на її місце вводиться змінна, що відповідає ключовому стовпцю. Елементи колишнього ключового рядка виходять розподілом колишнього елемента на ключовий. Елементи колишнього ключового стовпця стають нулями, крім ключового елемента, що дорівнює одиниці. Решта елементів обчислюються за правилом прямокутника:
8. Перетворення симплекс-таблиц проводять до того часу, поки отримають оптимального плану.
приклад. Знайти максимальне значення функції 
, якщо змінні 
задовольняють системі обмежень:
Рішення. 1. Вводимо нові змінні 
, за допомогою яких нерівності системи перетворюємо на рівняння:
У коефіцієнтів цільової функції змінюємо знак або записуємо її як 
. Заповнюємо першу симплексну таблицю, у нульовому рядку записуємо х 1 ,х 2 та 
(Вільні коефіцієнти). У нульовому стовпці – х 3 ,х 4 ,х 5 та F. Заповнюємо цю таблицю за отриманою системою рівнянь та перетвореною цільовою функцією.
|
|
|
|
|
|
| |||
|
| |||
|
| |||
|
|
Перевіряємо критерій оптимальності на перебування максимального значення: в останньому рядку всі коефіцієнти повинні бути позитивними. Цей критерій не виконується, переходимо до складання другої таблиці.
2. Знаходимо роздільний елемент першої таблиці наступним чином. Серед елементів останнього рядка вибираємо найбільший за модулем негативний коефіцієнт (це -3) і другий стовпець приймаємо як роздільну здатність. Якщо всі коефіцієнти стовпця непозитивні, то 
.
Для визначення роздільної здатності рядка вільні коефіцієнти ділимо на відповідні елементи роздільної здатності стовпця і вибираємо мінімальне відношення, при цьому негативні коефіцієнти не беремо. Маємо 
, другий рядок є роздільною. Перетин роздільної здатності і стовпця дає роздільний елемент – це 3.
3. Заповнюємо другу симплексну таблицю. Змінні на перетині яких отримуємо роздільну здатність, змінюємо місцями, тобто. 
і 
. Дозволяючий елемент замінюємо йому зворотним, тобто. на. Елементи роздільної здатності рядка і стовпця (крім роздільної здатності) ділимо на роздільний елемент. При цьому у коефіцієнтів роздільного стовпця змінюємо знак.
Інші елементи другої таблиці отримуємо за правилом прямокутника з елементів першої таблиці. Для клітини, що заповнюється, і клітини з роздільним елементом складаємо прямокутник. Потім з елемента для клітини, що заповнюється, віднімаємо добуток елементів двох інших вершин, поділений на дозвільний елемент. Покажемо розрахунки за цим правилом для заповнення першого рядка другого таблиці:
.
Заповнення таблиць за такими правилами продовжуємо доти, доки буде виконано критерій. Маємо для нашого завдання ще дві таблиці.
|
х 1 |
х 4 |
х 3 |
х 2 | ||||||
|
х 3 |
х 1 |
| |||||||
|
х 2 |
|
х 2 |
|
|
|
||||
|
х 5 |
|
х 5 |
| ||||||
|
|
4. Результат виконання цього алгоритму записують так. У заключній таблиці елемент, що стоїть на перетині рядка 
та стовпця bдає максимальне значення цільової функції. У нашому випадку 
. Значення змінних по рядках дорівнюють вільним коефіцієнтам. Для нашого завдання маємо 
.
Існують і інші способи складання та заповнення симплексних таблиць. Наприклад, для етапу 1 у нульовому рядку таблиці записують усі змінні та вільні коефіцієнти. Після знаходження роздільника за тими ж правилами в наступній таблиці замінюємо змінну в нульовому стовпці, а в рядку немає. Всі елементи роздільної здатності ділимо на роздільний елемент, і записуємо в новій таблиці. Для інших елементів роздільного стовпця записуємо нулі. Далі виконуємо вказаний алгоритм з урахуванням цих правил.
При розв'язанні задачі лінійного програмування на мінімум в останньому рядку вибирають найбільший позитивний коефіцієнт і виконують зазначений алгоритм доти, поки в останньому рядку не буде позитивних коефіцієнтів.
Розв'язання задач лінійного програмування засобами Excel виконується в такий спосіб.
Для вирішення завдань лінійного програмування використовується надбудова Пошук рішення. Спочатку необхідно переконатися, що ця надбудова присутня на вкладці Дані у групі Аналіз (для 2003 дивитися Сервіс). Якщо команда Пошук рішення або група Аналіз відсутня, необхідно завантажити цю надбудову.
Для цього клацніть Файл Microsoft Office(2010), клацніть кнопку Параметри Excel. У вікні Параметри Excel виберіть ліворуч поле Надбудови. У правій частині вікна має бути встановлене значення поля Управління рівним Надбудови Excel, натисніть кнопку «Перейти», яка знаходиться поруч із цим полем. У вікні Надбудови встановіть прапорець поруч із пунктом Пошук рішення та натисніть кнопку ОК. Далі можна працювати із встановленою надбудовою Пошук Рішення.
До виклику Пошук Рішення необхідно підготувати дані для вирішення задачі лінійного програмування (з математичної моделі) на робочому аркуші:
1) Визначити осередки, в які буде поміщено результат рішення для цього, у першому рядку вводимо змінні та цільову функцію. Другий рядок не заповнюємо (змінювані осередки) у цих осередках буде отримано оптимальний результат. У наступному рядку вести дані для цільової функції, а в наступні рядки системи обмежень (коефіцієнти при невідомих). Праву частинуобмежень (вільні коефіцієнти) вводимо, залишаючи вільний осередок після запису коефіцієнтів системи обмежень.
2) Ввести залежність від змінних осередків для цільової функції та залежності від змінних осередків для лівих частин системи обмежень у залишені вільні осередки. Для запровадження формул залежностей зручно користуватися математичною функцією СУММПРОИЗВ.
Далі необхідно скористатись надбудовою Пошук рішення. На вкладці Дані у групі Аналіз виберіть команду Пошук рішення. З'явиться діалогове вікно Пошук рішення, яке потрібно заповнити так:
1) Вказати комірку, що містить цільову функцію в полі «Оптимізувати цільову функцію» (ця комірка повинна містити формулу для цільової функції). Вибираємо варіант оптимізації значення цільового осередку (максимізація, мінімізація):
2) У полі «Змінюючи комірки змінних» вводимо комірки, що змінюються. У наступному полі «Відповідно до обмежень» вводимо задані обмеження за допомогою кнопки «Додати». У вікні вводимо комірки, що містять формули системи обмежень, вибираємо знак обмеження і значення обмеження (вільний коефіцієнт):
3) Ставимо прапорець у полі «Зробити змінні без обмежень невід'ємними». Вибрати метод розв'язання «Пошук розв'язання лінійних задач симплекс-методом». Після натискання кнопки «Знайти рішення» запускається процес розв'язання задачі. У результаті з'являється діалогове вікно «Результати пошуку рішення» та вихідна таблиця із заповненими осередками для значень змінних та оптимальним значенням цільової функції.
приклад.Вирішити, використовуючи надбудову «Пошук рішення» Excel завдання лінійного програмування: знайти максимальне значення функції 
при обмеженнях
,
;
,
.
Рішення.Для вирішення нашого завдання на робочому аркуші Excel виконаємо вказаний алгоритм. Вводимо вихідні дані у вигляді таблиці
Вводимо залежності для цільової функції та системи обмежень. Для цього в комірку С2 вводимо формулу СУММПРОИЗВ(A2:B2;A3:B3). У комірки С4 і С5 відповідно формули: = СУММПРОИЗВ(A2:B2;A4:B4) і =СУММПРОИЗВ(A2:B2;A5:B5). У результаті одержуємо таблицю.
Запускаємо команду «Пошук рішення» і заповнюємо вікно Пошук рішення наступним чином. У полі «Оптимізувати цільову функцію» вводимо комірку С2. Вибираємо оптимізації значення цільового осередку «Максимум».
У полі «Змінюючи комірки змінних» вводимо комірки A2:B2, що змінюються. У полі «Відповідно до обмежень» вводимо задані обмеження за допомогою кнопки «Додати». Посилання на комірку $C$4:$C$5 Посилання на обмеження =$D$4:$D$5 між ними знак<= затем кнопку «ОК».
Ставимо прапорець у полі "Зробити змінні без обмежень невід'ємними". Вибрати метод розв'язання «Пошук розв'язання лінійних задач симплекс-методом».
Натисканням кнопки «Знайти рішення» запускається процес розв'язання задачі. У результаті з'являється діалогове вікно «Результати пошуку рішення» та вихідна таблиця із заповненими осередками для значень змінних та оптимальним значенням цільової функції.
У діалоговому вікні «Результати пошуку рішення» зберігаємо результат x1=0,75, x2=0,75, F=1,5-рівний максимальному значенню цільової функції.
Завдання для самостійної роботи
Завдання 1.Графічним, симплексним методами та засобами Excel знайти максимальне та мінімальне значення функції F(x) при заданій системі обмежень.
1. F(x)=10x 1 +5x 2 2. F(x)=3x 1 -2x 2
3. F(x)=3x 1 +5x 2 4. F(x)=3x 1 +3x 2
5. F(x)=4x 1 -3x 2 6. F(x)=2x 1 -x 2
7. F(x)=-2x 1 +4x 2 8. F(x)=4x 1 -3x 2
9. F(x)=5x 1 +10x 2 10. F(x)=2x 1 +x 2
11. F(x)=x 1 +x 2 12. F(x)=3x 1 +x 2
13. F(x)=4x 1 +5x 2 14. F(x)=3x 1 +2x 2
15. F(x)=-x 1 -x 2 16. F(x)=-3x 1 -5x 2
17. F(x)=2x 1 +3x 2 18. F(x)=4x 1 +3x 2
19. F(x)=-3x 1 -2x 2 20. F(x)=-3x 1 +4x 2
21. F(x)=5x 1 -2x 2 22. F(x)=-2x 1 +3x 3
23. F(x)=2x 1 +3x 2 24. F(x)=4x 1 +3x 2
25. F(x)=-3x 1 -2x 2 26. F(x)=-3x 1 +4x 2
27. F(x)=-2x 1 +4x 2 28. F(x)=4x 1 -3x 2
29. F(x)=-x 1 -x 2 30. F(x)=-3x 1 -5x 2
Контрольні питання.
1. Які завдання називаються задачами лінійного програмування?
2. Наведіть приклади задач лінійного програмування.
3. Як розв'язується задача лінійного програмування графічним методом?
4. Опишіть алгоритм симплекс-методу розв'язання задач лінійного програмування.
5. Опишіть алгоритм розв'язання задач лінійного програмування засобами Excel.
ТЕМА: ЛІНІЙНЕ ПРОГРАМУВАННЯ
ЗАВДАННЯ 2.А. Розв'язання задачі лінійного програмування графічним методом
Увага!
Це ОЗНАКОМНА ВЕРСІЯ роботи №2073, ціна оригіналу 200 рублів. Оформлена у програмі Microsoft Word.
Оплата. Контакти.
Варіант 7. Знайти максимальне та мінімальне значеннялінійної функції Ф = 2x 1 - 2 · x 2при обмеженнях: x 1 + х 2 ≥ 4;
- х 1 + 2 · х 2 ≤ 2;
x 1 + 2 · х 2 ≤ 10;
х i ≥ 0, i = 1,2.
Рішення:
Замінивши умовно знаки нерівностей на знаки рівностей, отримаємо систему рівнянь x1 + x2 = 4;
- х1 + 2 · х2 = 2;
x1 + 2 · х2 = 10.
Побудуємо за цими рівняннями прямі, потім відповідно до знаків нерівностей виділимо напівплощини та отримаємо їх загальну частину- Область допустимих рішень ОДР - чотирикутник MNPQ.
Мінімальне значення функці-
ції - у точці М(2; 2)
Ф min = 2 · 2 - 2 · 2 = 0.
Максимальне значення досягається в точці N (10; 0),
Ф max = 2 · 10 - 2 · 0 = 20.
Варіант 8. Знайти максимальне та мінімальне значення
лінійної функції Ф = х 1 + х 2
при обмеженнях: x 1 - 4 · х 2 - 4 ≤ 0;
3 · х 1 - х 2 ≥ 0;
x 1 + х 2 - 4 ≥ 0;
х i ≥ 0, i = 1,2.
Рішення:
Замінивши умовно знаки нерівностей на знаки рівностей, отримаємо систему рівнянь x1 - 4 · х2 = 4;
3 · х1 - х2 = 0;
Побудуємо за цими рівняннями прямі, потім відповідно до знаків нерівностей виділимо напівплощини та отримаємо їхню загальну частину – область допустимих рішень ОДР – необмежений багатокутник MNPQ.
Мінімальне значення функці-
ції – на прямій NP, наприклад
у точці Р(4; 0)
Ф min = 4+0 = 4.
ОДР зверху не обмежена, отже, Ф max = + ∞.
Варіант 10. Знайти максимальне та мінімальне значення
лінійної функції Ф = 2 · x 1 - 3 · x 2
при обмеженнях: x 1 + 3 x 2 ≤ 18;
2 · х 1 + х 2 ≤ 16;
х 2 ≤ 5;
х i ≥ 0, i = 1,2.
Замінивши умовно знаки нерівностей знаками рівностей, отримаємо систему рівнянь
x 1 + 3 · x 2 = 18 (1);
2 · х 1 + х 2 = 16 (2);
3 · х 1 = 21 (4).
Побудуємо за цими рівняннями прямі, потім відповідно до знаків нерівностей виділимо напівплощини та отримаємо їхню загальну частину — область допустимих рішень ОДР – багатокутник MNPQRS.
Побудуємо вектор Г(2; -3) і через початок координат проведемо лінію рівня- Пряму.
Переміщуємо лінію рівня у напрямі, значення Ф у своїй зростає. У точці S(7; 0) цільова функція досягає максимуму Ф max =2·7–3·0= = 14. Переміщуємо лінію рівня у напрямку, значення Ф при цьому зменшується. Мінімальне значення функції - у точці N(0; 5)
Ф min = 2 · 0 - 3 · 5 = -15.
ЗАВДАННЯ 2.B. Розв'язання задачі лінійного програмування
аналітичним симплексним методом
Варіант 7. Мінімізувати цільову функцію Ф = 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 = 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 виразимо через вільні і приведемо систему до одиничного базису
х 2 = 2 - 3 · x 1 + 4 · x 3 - 2 · x 6
x 4 = 9 - x 1 - 6 · x 6 (*)
x 5 = 6 - x 1 - 2 · x 3 - 2 · x 6
Цільова функція матиме вигляд:
Ф = 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 = x 3 = x 6 = 0, причому базисні змінні приймуть значення x 2 = 2; x4 = 9; x 5 = 6, тобто перше допустиме рішення (0; 2; 0; 9; 6; 0), цільова функція Ф 1 = 13.
Змінні х 3 і х 6 входять до цільової функції з негативними коефіцієнтами, отже, зі збільшенням їх значень величина Ф буде зменшуватися. Візьмемо, наприклад, х 6 . З одного рівняння системи (*) видно, що збільшення значення x 6 можливе до x 6 = 1 (поки x 2 ³ 0). При цьому x 1 і x 3 зберігають значення, що дорівнюють нулю. Тепер в якості базисних змінних прийомів х 4, х 5, х 6, як вільні - х 1, х 2, х 3. Висловимо нові базисні змінні через нові вільні. Отримаємо
х 6 = 1 - 3/2 · x 1 - 1/2 · x 2 + 2 · x 3
x 4 = 3 + 8 · x 1 + 3 · x 2 - 12 · x 3
x 5 = 4 + 2 · x 1 + x 2 - 6 · x 3
Ф = 6 + 25/2 · x 1 + 7/2 · x 2 - 19 · x 3
Надамо вільним змінним нульові значення, тобто x 1 = x 2 = x 3 = 0, при цьому х 6 = 1, x 4 = 3, x 5 = 4, тобто, третє допустиме рішення (0; 0; 0; 3; 4; У цьому Ф 3 = 6.
Змінна x 3 входить до цільової функції з негативним коефіцієнтом, отже збільшення x 3 щодо нульового значення призведе до зниження Ф. З 2-го рівняння видно, що x 3 може зростати до 1/4, з 3-го рівняння – до 2/3 . Друге рівняння критичніше. Змінну x 3 переведемо до базисних, x 4 — до числа вільних.
Тепер як нові вільні змінні приймемо x 1 , x 2 і x 4 . Виразимо через них нові базисні змінні x3, x5, x6. Отримаємо систему
х 3 = 1/4 + 2/3 · x 1 + 1/4 · x 2 - 1/12 · x 4
x 5 = 5/2 - 2 · x 1 - 1 / 2 · x 2 + 1 / 2 · x 4
x 6 = 3/2 - 1/6 · x 1 - 1/6 · x 4
Цільова функція набуде вигляду
Ф = 5/4 - 1/6 · x 1 - 5/4 · x 2 + 19/12 · x 4
Змінні х 1 і х 2 входять до цільової функції з негативними коефіцієнтами, отже, зі збільшенням їх значень величина Ф буде зменшуватися. Візьмемо, наприклад, х2. З 2-го рівняння системи видно, що збільшення значення x 2 можливе до x 2 = 5 (поки x 5 ³ 0). При цьому x 1 та x 4 зберігають нульові значення, значення інших змінних дорівнюють x 3 = 3/2; x 5 = 0, x 6 = 3/2, тобто четверте допустиме рішення (0; 5; 3/2; 0; 0; 3/2). У цьому Ф 4 = 5/4.
Тепер як нові вільні змінні приймемо x 1 , x 4 і x 5 . Виразимо через них нові базисні змінні x2, x3, x6. Отримаємо систему
х 2 = 5 - 4 · x 1 + x 4 - 2 · x 5
x 3 = 3/2 - 1/3 · x 1 + 1/6 · x 4 - 1/2 · x 5
x 6 = 3/2 - 1/6 · x 1 - 1/6 · x 4
Цільова функція набуде вигляду
Ф = - 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
при обмеженнях: x1+x5+x6=12;
x 2 + 5 · x 5 - x 6 = 30;
x 3 + x 5 - 2 · x 6 = 6;
2 · x 4 + 3 · x 5 - 2 · x 6 = 18;
Рішення:
Кількість рівнянь дорівнює 4, кількість невідомих - 6. Отже r = n - m = 6 - 4 = 2 змінних можемо вибрати як вільні, 4 змінні - як базисні. Як вільні виберемо x 5 і x 6 , як базисні - x 1 , x 2 , x 3 , x 4 . Висловимо базисні змінні через вільні та наведемо систему рівнянь до одиничного базису
x 1 = 12 - x 5 - x 6;
x 2 = 30 - 5 · x 5 + x 6;
x 3 = 6 - x 5 + 2 · x 6;
x 4 = 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.
У цільову функцію обидві вільні змінні входять з позитивними коефіцієнтами, тобто, можливо подальше збільшення Ф. Переведемо, наприклад, 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. Виразимо нові базисні змінні через нові вільні
х 6 = 12 - x 1 - x 5;
x 2 = 42 - x 1 - 6 · x 5;
x 3 = 30 - 2 · x 1 - 3 · x 5;
x 4 = 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 входить з позитивним коефіцієнтом, тобто, можливо подальше збільшення Ф. Перейдемо до нового базису: базисні змінні - x 6 x 5 x 3 x 4 вільні x 1 x 2. Виразимо нові базисні змінні через нові вільні
х 6 = 5 - 5/6 · x 1 + 1/6 · x 2;
x 5 = 7 - 1/6 · x 1 - 1/6 · x 2;
x 3 = 9 - 3/2 · x 1 + 1/2 · x 2;
x 4 = 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, тобто отримаємо третє допустиме рішення Х 3 = (0, 0, 9, 7/2, 7, 5) та Ф 3 = 38.
У цільову функцію обидві змінні входять з негативними коефіцієнтами, тобто подальше збільшення Ф неможливе.
Отже, останнє допустиме рішення є оптимальним, тобто Х опт = (0, 0, 9, 7/2, 7, 5) та Ф max = 38.
Варіант 10. Максимізувати цільову функцію Ф = х 2 + х 3
при обмеженнях: x 1 - x 2 + x 3 = 1,
x 2 - 2 · х 3 + х 4 = 2.
Рішення:
Система рівнянь - обмежень спільна, тому що ранги матриці системи рівнянь і розширеної матриці однакові і рівні 2. Отже, дві змінні можна прийняти як вільні, дві інші змінні - базисні - виразити лінійно через дві вільні.
Приймемо за вільні змінні x 2 і х 3. Тоді базисними будуть змінні х 1 і х 2, які виразимо через вільні
x 1 = 1 + x 2 - x 3; (*)
x 4 = 2 - x 2 + 2 · x 3;
Цільова функція вже виражена через x 2 і x 3 тобто Ф = x 2 + x 3 .
При х 2 =0 і х 3 =0 базисні змінні дорівнюватимуть х 1 = 1, х 4 = 2.
Маємо перше допустиме рішення Х1 = (1, 0, 0, 2), при цьому Ф1 = 0.
Збільшення Ф можливе при збільшенні, наприклад, значення х 3 який входить у вираз для Ф з позитивним коефіцієнтом (x 2 при цьому залишається рівним нулю). У перше рівняння системи (*) видно, що х 3 можна збільшувати до 1 (з умови х 1 0), тобто це рівняння накладає обмеження на збільшення значення х 3 . Перше рівняння системи (*) є вирішальним. На основі цього рівняння переходимо до нового базису, змінивши х 1 і 3 місцями. Тепер базовими змінними будуть х 3 і х 4, вільними - х 1 і х 2 . Виразимо тепер х 3 і х 4 через х 1 і х 2 .
Отримаємо: x 3 = 1 - x 1 + x 2; (**)
x 4 = 4 - 2 · x 1 + x 2;
Ф = х 2 + 1 - х 1 + х 2 = 1 - x 1 + 2 · x 2
Прирівнявши нулю вільні змінні, отримаємо друге допустиме базисне рішення Х 2 = (0; 0; 1; 4), у якому Ф 2 =1.
Збільшення Ф можливе зі збільшенням х 2 . Збільшення ж х 2 , судячи з останньої системи рівнянь (**), не обмежена. Отже, Ф прийматиме все більші позитивні значення, тобто Ф мах = + ¥.
Отже, цільова функція Ф не обмежена зверху, тому оптимального рішення немає.
ЗАВДАННЯ 2.D. Скласти завдання, подвійне до наведеного
вихідної задачі.
Варіант 7. Максимізувати цільову функцію Ф = 2× х 1 - х 4
при обмеженнях: х 1 + х 2 = 20,
х 2 + 2× х 4 ≥ 5,
х 1 + х 2 + х 3 ≤ 8,
х i ≥ 0 (i = 1, 2, 3, 4)
Рішення:
Наведемо систему обмежень до єдиного, наприклад, канонічного виду, ввівши додаткові змінні у 2-е та 3-е рівняння
х 1 + х 2 = 20,
х 2 + 2 × х 4 - х 5 = 5,
- х 1 + х 2 + х 3 + х 6 = 8.
Отримали несиметричне завдання 2 типу. Подвійне завдання матиме вигляд:
Мінімізувати цільову функцію F = 20 × у 1 + 5 × y 2 + 8 × y 3
при y 1 - y 3 ≥ 2,
y 1 + y 2 + y 3 ≥ 0,
y 3 ≥ 0,
2× y 2 ≥ 1,
Y 2 ≥ 0,
y 3 ≥ 0.
Варіант 8. Максимізувати цільову функцію Ф = х 2 - х 4 - 3× х 5
при обмеженнях: х 1+2× х 2 - х 4 + х 5 = 1,
— 4 × х 2 + х 3 + 2× х 4 - х 5 = 2,
3 × х 2 + х 5 + х 6 = 5,
x i ≥ 0, (i = 1, 6)
Рішення:
Маємо вихідне завдання на максимізацію із системою обмежень у вигляді рівнянь, тобто пара двоїстих завдань має несиметричний вигляд 2-го типу, математична модель яких у матричній формі має вигляд:
Вихідне завдання: Подвійне завдання:
Ф = С × Х max F = B Т × Y min
при А × Х = В при A Т × Y ≥ С Т
У вихідному завданні матриця-рядок коефіцієнтів при змінних у цільовій функції має вигляд С = (0; 1; 0; -1; -3; 0),
матриця-стовпець вільних членів та матриця коефіцієнтів при змінних у системі обмежень мають вигляд
В = 2, А = 0 - 4 1 2 -1 0
Знайдемо транспоновану матрицю коефіцієнтів, матрицю-рядок коефіцієнтів при змінних у цільовій функції та матрицю-стовпець вільних членів
0 1 0 0 В Т = (1; 2; 5)
A T = -1 2 0 С Т = -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. Мінімізувати функцію Ф = х1+х2+х3
при обмеженнях: 3× х 1 + 9× х 2 + 7× х 3 ≥ 2,
6 × х 1 + 4 · х 2 + 5× х 3 ≥ 3,
8 × х 1 + 2 · х 2 + 4× х 3 ≥ 4,
Рішення:
Маємо вихідне завдання на мінімізацію із системою обмежень у вигляді нерівностей, тобто пара двоїстих завдань має симетричний вигляд 3-го типу, математична модель яких у матричній формі має вигляд:
Вихідне завдання Подвійне завдання
Ф = С × Х min F = B Т × Y max
при А × Х ≥ В при A Т × Y ≤ З Т
Х ≥ 0 Y ≥ 0
У вихідному завданні матриця-рядок коефіцієнтів при змінних у цільовій функції, матриця-стовпець вільних членів та матриця коефіцієнтів при змінних у системі обмежень мають вигляд
С = (1; 1; 1), В = 3, А = 6 4 5
Знайдемо матриці двоїстої задачі
T = (2; 3; 4) 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-ма невідомими. Виберемо в якості базисних 3 змінних x 1, z 1, z 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 = 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 = 2.
Складемо симплекс-таблицю
I ітерація Таблиця 1
| Базисн. перем. | Свобод. перем. | |||||||||
| x 1 | 1 | 1 | — 2 | 5 | — 3 | 0 | — 1 | 0 | 3/8 | |
| z 1 | 2 | 0 | 7 | -11 | 1 | 2 | 0 | 1/ 4 | 1/8 | |
| z 3 | 4 | 0 | 18 | -17 | 13 | 0 | 4 | 1 | 4/13 | 13/8 |
| Ф | 2 | 0 | — 3 | 7 | — 8 | 0 | — 2 | 0 | 1 |
Х 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.
ІІ ітерація Таблиця 2
| x 1 | 14/8 | 1 | 5/8 | 7/8 | 0 | 3/8 | -2/8 | 0 | 2 | — 1 |
| x 4 | 1/ 4 | 0 | 7/8 | -11/8 | 1 | 1/8 | 2/8 | 0 | 11/7 | |
| z 3 | 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 |
Х 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.
ІІІ ітерація Таблиця 3
| x 1 | 1 | 1 | — 6 | 0 | 0 | -1 | — 1 | 1/2 | ||
| x 4 | 10/ 7 | 0 | 79/7 | 0 | 1 | -17/7 | 10/7 | 11/7 | 11/7 | |
| x 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 |
Х 3 = (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 = 52/7.
IV ітерація Таблиця 4
| z 1 | 1/ 2 | 1/2 | — 3 | 0 | 0 | 1 | -1/2 | -1/2 | ||
| x 4 | 37/ 14 | 17/14 | 56/14 | 0 | 1 | 0 | 3/14 | 5/14 | ||
| x 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 |
Х 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) Ф 4 = 149/14.
У індексному рядку останньої таблиці немає негативних чисел, тобто, у виразі для цільової функції все Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.
Відповідь: Ф m ax = 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 = 3,
x 2 + 2 · x 4 = 1,
Рішення:
Кількість змінних дорівнює 4, ранг матриці - 2, отже кількість вільних змінних дорівнює r = 4 - 2 = 2, кількість базисних теж 2. Як вільні змінні прийоми х 3 , х 4 , базисні змінні x 1 , x 2 виразимо через вільні і наведемо систему до одиничного базису:
x 2 = 1 - 2 · x 4 ,
x 1 = 3 - x 2 - 2 · x 3 + x 4 = 3 - 1 + 2 · x 4 - 2 · x 3 + x 4 = 2 - 2 · x 3 + 3 · x 4
Ф = 5 · x 1 - x 3 = 5 · (2 - 2 · x 3 + 3 · x 4) - x 3 = 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 · x 3 - 15 · x 4 = 10
Складемо таблицю
I ітерація Таблиця 1
| Базисн. перем. | Свобод. перем. | ||||||
| X 1 | 2 | 1 | 0 | — 3 | 1/2 | ||
| X 2 | 1 | 0 | 1 | 0 | 2 | ||
| Ф | 10 | 0 | 0 | 11 | — 15 | — 11/2 |
Х 1 = (2; 1; 0; 0) Ф 1 = 10.
ІІ ітерація Таблиця 2
| X 3 | 1 | 1/2 | 0 | 1 | -3/2 | 3/4 | |
| X 2 | 1 | 0 | 1 | 0 | 1/2 | ||
| Ф | — 1 | — 11/2 | 0 | 0 | 3/2 | — 3/4 |
Х 2 = (0; 1; 1; 0) Ф 2 = -1.
ІІІ ітерація Таблиця 3
| X 3 | 7/4 | 1/2 | 3/4 | 1 | 0 | ||
| X 4 | 1/2 | 0 | 1/2 | 0 | 1 | ||
| Ф | — 7/4 | — 11/2 | — 3/4 | 0 | 0 |
Х 3 = (0; 0; 7/4; 1/2) Ф 3 = -7/4.
В індексному рядку останньої таблиці немає позитивних чисел, тобто, у виразі для цільової функції все Г i > 0. Маємо випадок I, отже, останнє базисне рішення є оптимальним.
Відповідь: Ф min = -7/4, оптимальне рішення (0; 0; 7/4; 1/2)
********************
Варіант 10. Мінімізувати цільову функцію Ф = x1 + x2,
при обмеженнях: x 1 -2 · x 3 + x 4 = 2,
x 2 - x 3 + 2 · x 4 = 1,
Рішення:
Кількість змінних дорівнює 5, ранг матриці - 3, отже кількість вільних змінних дорівнює r = 6-3 = 2. Як вільні змінні прийоми х 3 і х 4, як базові - x 1 , x 2 , x 5 . Всі рівняння системи вже приведені до одиничного базису (базисні змінні виражені через вільні), але записані у вигляді, не зручному для застосування симплекс-таблиць. Запишемо систему рівнянь у вигляді
x 1 - 2 · x 3 + x 4 = 2
x 2 - x 3 +2 · x 4 = 1
x 5 + x 3 - x 4 . = 5
Цільову функцію виразимо через вільні змінні і запишемо у вигляді Ф - 3 x 3 +3 x 4 = 3
Складемо таблицю
I ітерація Таблиця 1
| Базисн. перем. | Свобод. перем. | |||||||
| х 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 |
Х 1 = (2; 3; 0; 0; 5) Ф 1 = 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 |
Х 2 = (3/2; 0; 0; 1/2; 11/2) Ф 2 = 3/2.
У індексному рядку останньої таблиці немає позитивних чисел, тобто у виразі для цільової функції все Гi > 0. Маємо випадок 1, отже, останнє базисне рішення є оптимальним.
Відповідь: Ф min = 3/2, оптимальне рішення (3/2; 0; 0; 1/2; 11/2).
Побудуємо на площині безліч допустимих рішень системи лінійних нерівностейта геометрично знайдемо мінімальне значення цільової функції.
Будуємо в системі координат х 1 ох 2 прямі
Знаходимо напівплощини, що визначаються системою. Так як нерівності системи виконується для будь-якої точки з відповідної напівплощини, їх достатньо перевірити для будь-якої однієї точки. Використовуємо точку (0; 0). Підставимо її координати у першу нерівність системи. Т.к. , то нерівність визначає напівплощину, що не містить точку (0; 0). Аналогічно визначаємо інші напівплощини. Знаходимо безліч допустимих рішень як загальну частину отриманих напівплощин - це заштрихована область.
Будуємо вектор та перпендикулярно до нього пряму нульового рівня.
Переміщуючи пряму (5) у напрямку вектора і бачимо, що область максимальна точка буде в точці А перетину прямий (3) і прямий (2). Знаходимо розв'язання системи рівнянь:
Отже, отримали точку (13; 11) і.
Переміщуючи пряму (5) у напрямку вектора і бачимо, що область мінімальна точка буде в точці В перетину прямий (1) і прямий (4). Знаходимо розв'язання системи рівнянь:
Отже, отримали точку (6; 6) і.
2. Меблева фірма виробляє комбіновані шафи та комп'ютерні столики. Їх виробництво обмежене наявністю сировини (високоякісних дощок, фурнітури) і часом роботи верстатів, що їх обробляють. Для кожної шафи потрібно 5 м2 дощок, для столу – 2 м2. На одну шафу витрачається фурнітури на 10 $, на один столик також на 8 $. Фірма може отримувати від своїх постачальників до 600 м2 дощок на місяць та фурнітури на 2000 $. Для кожної шафи потрібно 7 годин роботи верстатів, для столу – 3 години. На місяць можна використовувати всього 840 годин роботи верстатів.
Скільки комбінованих шаф та комп'ютерних столиків фірмі слід випускати на місяць для отримання максимального прибутку, якщо одна шафа приносить 100 $ прибутку, а кожен стіл - 50 $?
- 1. Скласти математичну модель завдання та вирішити її симплексним методом.
- 2. Скласти математичну модель двоїстої задачі, записати її рішення, виходячи з рішення вихідної.
- 3. Встановити ступінь дефіцитності використовуваних ресурсів та обґрунтувати рентабельність оптимального плану.
- 4. Дослідити можливості подальшого збільшення випуску продукції залежно від використання кожного виду ресурсів.
- 5. Оцінити доцільність запровадження нового виду продукції - книжкових полиць, якщо виготовлення однієї полиці витрачається 1 м 2 дошок і фурнітури на 5$,і потрібно витратити 0,25 години роботи верстатів і прибуток від однієї полиці становить 20$.
- 1. Побудуємо математичну модель для цієї задачі:
Позначимо через x 1 – обсяг виробництва шаф, а х 2 – обсяг виробництва столиків. Складемо систему обмежень та функцію мети:
Завдання вирішуємо симплекс-метод. Запишемо її в канонічному вигляді:
Запишемо ці завдання у вигляді таблиці:
Таблиця 1
Т.к. тепер все дельта більше нуля, то подальше збільшення значення функції мети f неможливе, і ми отримали оптимальний план.
Якщо обмежуючий фактор один (наприклад, дефіцитний верстат), рішення може бути знайдено із застосуванням простих формул (див. посилання на початку статті). Якщо обмежуючих чинників кілька, застосовується метод лінійного програмування.
Лінійне програмування- це назва, дана комбінації інструментів, що використовуються в науці про управління. Цей метод вирішує проблему розподілу обмежених ресурсів між конкуруючими видами діяльності для того, щоб максимізувати або мінімізувати деякі чисельні величини, такі як маржинальний прибуток або витрати. У бізнесі він може використовуватися в таких галузях як планування виробництва для максимального збільшення прибутку, підбір комплектуючих для мінімізації витрат, вибір портфеля інвестицій для максимізації прибутковості, оптимізація перевезень товарів з метою скорочення відстаней, розподіл персоналу з метою максимально збільшити ефективність роботи та складання графіка робіт цілях економії часу.
Завантажити нотатку у форматі , малюнки у форматі
Лінійне програмування передбачає побудову математичної моделі розглянутого завдання. Після чого рішення може бути знайдено графічно (розглянуто нижче), з використанням Excel (розглянуто окремо) або спеціалізованих комп'ютерних програм.
Мабуть, побудова математичної моделі – найбільше складна частиналінійного програмування, що вимагає переведення розглянутої задачі до системи змінних величин, рівнянь і нерівностей – процес, зрештою залежить від навичок, досвіду, здібностей та інтуїції укладача моделі.
Розглянемо приклад побудови математичної моделі лінійного програмування
Микола Кузнєцов керує невеликим механічним заводом. Наступного місяця він планує виготовляти два продукти (А і В), за якими питомий маржинальний прибуток оцінюється в 2500 і 3500 руб. відповідно.
Виготовлення обох продуктів потребує витрат на машинну обробку, сировину та працю (рис. 1). На виготовлення кожної одиниці продукту А відводиться 3 години машинної обробки, 16 одиниць сировини та 6 одиниць праці. Відповідні вимоги до одиниці продукту складають 10, 4 і 6. Микола прогнозує, що наступного місяця він може надати 330 годин машинної обробки, 400 одиниць сировини і 240 одиниць праці. Технологія виробничого процесу така, що не менше 12 одиниць продукту необхідно виготовляти в кожен конкретний місяць.
Мал. 1. Використання та надання ресурсів
Микола хоче побудувати модель для того, щоб визначити кількість одиниць продуктів А і В, які він повинен виробляти наступного місяця для максимізації маржинального прибутку.
Лінійна модель може бути побудована у чотири етапи.
Етап 1. Визначення змінних
Існує цільова змінна (позначимо її Z), яку необхідно оптимізувати, тобто максимізувати чи мінімізувати (наприклад, прибуток, виторг чи витрати). Микола прагне максимізувати маржинальний прибуток, отже, цільова змінна:
Z = сумарний маржинальний прибуток (у рублях), отриманий наступного місяця в результаті виробництва продуктів А і Ст.
Існує ряд невідомих шуканих змінних (позначимо їх х 1 , х 2 , х 3 та ін), чиї значення необхідно визначити для отримання оптимальної величини цільової функції, яка, у нашому випадку є сумарним маржинальним прибутком. Цей маржинальний прибуток залежить від кількості вироблених продуктів А і В. Значення цих величин необхідно розрахувати, і тому вони є шуканими змінними в моделі. Отже, позначимо:
х 1 = кількість одиниць продукту А, вироблених наступного місяця.
х 2 = кількість одиниць продукту, вироблених наступного місяця.
Дуже важливо чітко визначити усі змінні величини; особливу увагуприділіть одиницям виміру та періоду часу, до якого відносяться змінні.
Етап. 2. Побудова цільової функції
Цільова функція – це лінійне рівняння, яке має бути максимізовано або мінімізовано. Воно містить цільову змінну, виражену за допомогою змінних, тобто шукану через х 1 , х 2 ... у вигляді лінійного рівняння.
У нашому прикладі кожен виготовлений продукт приносить 2500 руб. маржинального прибутку, а при виготовленні х 1 одиниць продукту А, маржинальний прибуток становитиме 2500 * х 1 . Аналогічно маржинальний прибуток від виготовлення х 2 одиниць продукту складе 3500 * х 2 . Таким чином, сумарний маржинальний прибуток, отриманий наступного місяця за рахунок виробництва х 1 одиниць продукту А і х 2 одиниць продукту, тобто, цільова змінна Z складе:
Z = 2500 * х 1 + 3500 * х 2
Миколай прагне максимізувати цей показник. Таким чином, цільова функція у нашій моделі:
Максимізувати Z = 2500*х1+3500*х2
Етап. 3. Визначення обмежень
Обмеження – це система лінійних рівнянь та/або нерівностей, які обмежують величини змінних, що шукаються. Вони математично відбивають доступність ресурсів, технологічні чинники, умови маркетингу та інші вимоги. Обмеження може бути трьох видів: «менше чи одно», «більше чи одно», «строго одно».
У нашому прикладі для виробництва продуктів А і В необхідний час машинної обробки, сировина та праця та доступність цих ресурсів обмежена. Обсяги виробництва цих двох продуктів (тобто значення х 1 їх 2) будуть, таким чином, обмежені тим, що кількість ресурсів, необхідних у виробничому процесі, не може перевищувати наявне. Розглянемо ситуацію з часом машинної обробки. Виготовлення кожної одиниці продукту А вимагає трьох годин машинної обробки, і якщо виготовлено х 1 одиниць, то буде витрачено З * х 1 годин цього ресурсу. Виготовлення кожної одиниці продукту вимагає 10 годин і, отже, якщо вироблено х 2 продуктів, то знадобиться 10 * х 2 годин. Таким чином, загальний обсяг машинного часу, необхідного для виробництва х 1 одиниць продукту А і х 2 одиниць продукту, становить 3 * х 1 + 10 * х 2 . Це загальне значеннямашинного часу не може перевищувати 330 годин. Математично це записується так:
3 * х 1 + 10 * х 2 ≤ 330
Аналогічні міркування застосовуються до сировини та праці, що дозволяє записати ще два обмеження:
16 * х 1 + 4 * х 2 ≤ 400
6 * х 1 + 6 * х 2 ≤ 240
Нарешті слід зазначити, що існує умова, згідно з якою має бути виготовлено не менше 12 одиниць продукту:
Етап 4. Запис умов невід'ємності
Перемінні, що шукаються, не можуть бути негативними числами, що необхідно записати у вигляді нерівностей х 1 ≥ 0 і х 2 ≥ 0. У нашому прикладі друга умова є надмірною, оскільки вище було визначено, що х 2 не може бути менше 12.
Повна модель лінійного програмування для виробничого завдання Миколи може бути записана у вигляді:
Максимізувати: Z = 2500*х1+3500*х2
За умови, що: 3 * х 1 + 10 * х 2 ≤ 330
16 * х 1 + 4 * х 2 ≤ 400
6 * х 1 + 6 * х 2 ≤ 240
Розглянемо графічний метод розв'язання задачі лінійного програмування.
Цей метод підходить тільки для завдань з двома змінними, що шукаються. Модель, побудована вище, буде використано для демонстрації методу.
Осі на графіці є дві шукані змінні (рис. 2). Не має значення, яку змінну відкласти вздовж якої осі. Важливо вибрати масштаб, який зрештою дозволить побудувати наочну діаграму. Оскільки обидві змінні мають бути невід'ємними, малюється лише перший квадрант.
Мал. 2. Осі графіка лінійного програмування
Розглянемо, наприклад, перше обмеження: 3 * х 1 + 10 * х 2 ≤ 330. Ця нерівність описує область, що лежить нижче за пряму: 3 * х 1 + 10 * х 2 = 330. Ця пряма перетинає вісь х 1 при значенні х 2 = 0, тобто рівняння виглядає так: 3 * х 1 + 10 * 0 = 330, а його розв'язання: х 1 = 330 / 3 = 110
Аналогічно обчислюємо точки перетину з осями х 1 та х 2 для всіх умов-обмежень:
| Область допустимих значень | Кордон допустимих значень | Перетин з віссю х 1 | Перетин з віссю х 2 |
| 3 * х 1 + 10 * х 2 ≤ 330 | 3 * х 1 + 10 * х 2 = 330 | х 1 = 110; х 2 = 0 | х 1 = 0; х 2 = 33 |
| 16 * х 1 + 4 * х 2 ≤ 400 | 16 * х 1 + 4 * х 2 = 400 | х 1 = 25; х 2 = 0 | х 1 = 0; х 2 = 100 |
| 6 * х 1 + 6 * х 2 ≤ 240 | 6 * х 1 + 6 * х 2 = 240 | х 1 = 40; х 2 = 0 | х 1 = 0; х 2 = 40 |
| х 2 ≥ 12 | х 2 = 12 | не перетинає; йде паралельно осі х 1 | х 1 = 0; х 2 = 12 |
Графічно перше обмеження відбито на рис. 3.
Мал. 3. Побудова області допустимих рішень для першого обмеження
Будь-яка точка в межах виділеного трикутника або на його межах буде відповідати цьому обмеженню. Такі точки називаються допустимими, а точки поза трикутника називаються недопустимими.
Аналогічно відбиваємо на графіку інші обмеження (рис. 4). Значення х 1 та х 2 на або всередині заштрихованої області ABCDE будуть відповідати всім обмеженням моделі. Така сфера називається областю допустимих рішень.
Мал. 4. Область допустимих рішень для моделі загалом
Тепер у галузі допустимих рішень необхідно визначити значення х 1 і х 2 , які максимізують Z. Для цього рівняння цільової функції:
Z = 2500 * х 1 + 3500 * х 2
розділимо (або помножимо) коефіцієнти перед х 1 і х 2 на одне і те ж число, так щоб значення, що вийшли, потрапили в діапазон, що відображається на графіку; у разі такий діапазон – від 0 до 120; тому коефіцієнти можна поділити на 100 (або 50):
Z = 25х1 + 35х2
потім надамо Z значення рівне добутку коефіцієнтів перед х 1 і х 2 (25 * 35 = 875):
875 = 25х1 + 35х2
і, нарешті, знайдемо точки перетину прямої з осями х 1 і х 2:
Нанесемо це цільове рівнянняна графік аналогічно обмеженням (рис. 5):
Мал. 5. Нанесення цільової функції (чорна пунктирна лінія) на область допустимих рішень
Значення Z постійно протягом усього лінії цільової функції. Щоб знайти значення х 1 і х 2 які максимізують Z, потрібно паралельно переносити лінію цільової функції до такої точки в межах області допустимих рішень, яка розташована на максимальному віддаленні від вихідної лінії цільової функції вгору і вправо, тобто до точки С (рис. 6).
Мал. 6. Лінія цільової функції досягла максимуму в межах області допустимих рішень (у точці С)
Можна зробити висновок, що оптимальне рішення перебуватиме в одній із крайніх точок області ухвалення рішення. В якій саме залежатиме від кута нахилу цільової функції і від того, яке завдання ми вирішуємо: максимізації або мінімізації. Таким чином, не обов'язково креслити цільову функцію – все, що необхідно, це визначити значення х 1 і х 2 у кожній із крайніх точок шляхом зчитування з діаграми або рішення відповідної пари рівнянь. Знайдені значення х 1 і х 2 потім підставляються в цільову функцію для розрахунку відповідної величини Z. Оптимальним рішенням є те, при якому отримана максимальна величина Z при розв'язанні задачі максимізації, і мінімальна при вирішенні задачі мінімізації.
Визначимо, наприклад, значення х 1 і х 2 у точці С. Зауважимо, що точка С знаходиться на перетині ліній: 3х 1 + 10х 2 = 330 і 6х 1 + 6х 2 = 240. Розв'язання цієї системи рівнянь дає: х 1 = 10, х 2 = 30. Результати розрахунку всім вершин області допустимих рішень наведено у таблице:
| Крапка | Значення х 1 | Значення х 2 | Z = 2500х1 + 3500х2 |
| А | 22 | 12 | 97 000 |
| У | 20 | 20 | 120 000 |
| З | 10 | 30 | 130 000 |
| D | 0 | 33 | 115 500 |
| E | 0 | 12 | 42 000 |
Таким чином, Микола Кузнецом має запланувати на наступний місяцьвиробництво 10 виробів А і 30 виробів, що дозволить йому отримати маржинальний прибуток у розмірі 130 тис. руб.
Стисло графічного методу розв'язання задач лінійного програмування можна викласти так:
- Накресліть на графіці дві осі, що є двома параметрами рішення; намалюйте лише перший квадрант.
- Визначте координати точок перетину всіх граничних умов з осями, підставляючи рівняння граничних умов по черзі значення х 1 = 0 і х 2 = 0.
- Нанести лінії обмежень моделі на графік.
- Визначте на графіку область (звану допустимою областю прийняття рішення), яка відповідає всім обмеженням. Якщо така область відсутня, то модель не має рішення.
- Визначте значення змінних, що шукаються, в крайніх точках області прийняття рішення, і в кожному випадку розрахуйте відповідне значення цільової змінної Z.
- Для задач максимізації рішення - точка, в якій Z максимально, для задач мінімізації, рішення - точка, в якій мінімально.
