Знайти графічний метод мінімум цільової функції. Знайти екстремуми функції графічним методом

Цільова функція- речова або цілочисленна функція кількох змінних, що підлягає оптимізації (мінімізації або максимізації) з метою вирішення певної оптимізаційної задачі. Термін використовується в математичному програмуванні, дослідженні операцій, лінійному програмуванні, теорії статистичних рішеньта інших галузях математики в першу чергу прикладного характеру, хоча метою оптимізації може бути рішення власне математичної задачі. Крім цільової функціїу задачі оптимізації для змінних можуть бути задані обмеження у вигляді системи рівностей чи нерівностей. У загальному випадкуаргументи цільової функції можуть задаватися на довільних множинах.

Приклади

Гладкі функції та системи рівнянь

Завдання розв'язання будь-якої системи рівнянь

( 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) та всі проектні параметри задовольняють умові невід'ємності, а умови у вигляді нерівностей відсутні:

Канонічну задачу ЛП можна також записати в матричній та векторній формі.

Матрична форма канонічної задачі ЛП має такий вигляд:

Векторна форма канонічного завдання ЛП.

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

«МЕТОДИ ОПТИМАЛЬНИХ РІШЕНЬ»

Варіант №8

1. Розв'язати графічним способом завдання лінійного програмування. Знайти максимум і мінімум функції при заданих обмеженнях:

Рішення

Необхідно знайти мінімальне значення цільової функції та максимальне при системі обмежень:

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

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Побудуємо область допустимих рішень, тобто. розв'яжемо графічно систему нерівностей. Для цього побудуємо кожну пряму та визначимо напівплощини, задані нерівностями (напівплощини позначені штрихом).

Перетином напівплощин буде область, координати точок якого задовольняють умові нерівностей системи обмежень задачі. Позначимо межі області багатокутника розв'язків.

Побудуємо пряму, що відповідає значенню функції F = 0: F = 2x 1 +3x 2 = 0. Вектор-градієнт, складений з коефіцієнтів цільової функції, вказує напрямок мінімізації F(X). Початок вектора – точка (0; 0), кінець – точка (2; 3). Рухатимемо цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, то рухаємо пряму до першого торкання зазначеної області. На графіці ця пряма позначена пунктирною лінією.

Пряма
перетинає область у точці C. Так як точка C отримана в результаті перетину прямих (4) та (1), то її координати задовольняють рівнянням цих прямих:
.

Розв'язавши систему рівнянь, отримаємо: x 1 = 3.3333, x 2 = 0.

Звідки знайдемо мінімальне значення цільової функції: .

Розглянемо цільову функцію завдання.

Побудуємо пряму, що відповідає значенню функції F = 0: F = 2x1 +3x2 = 0. Вектор-градієнт, складений з коефіцієнтів цільової функції, вказує напрямок максимізації F(X). Початок вектора – точка (0; 0), кінець – точка (2; 3). Рухатимемо цю пряму паралельним чином. Оскільки нас цікавить максимальне рішення, то рухаємо пряму до останнього дотику зазначеної області. На графіці ця пряма позначена пунктирною лінією.

Пряма
перетинає область у точці B. Оскільки точка B отримана в результаті перетину прямих (2) і (3), її координати задовольняють рівнянням цих прямих:

.

Звідки знайдемо максимальне значення цільової функції: .

Відповідь:
і
.

2 . Розв'язати завдання лінійного програмування симплекс-методом:

Рішення

Розв'яжемо пряме завдання лінійного програмування симплексним методом, з використанням симплексної таблиці.

Визначимо мінімальне значення цільової функції
за наступних умов-обмежень:
.

Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом запровадження додаткових змінних.

У 1-й нерівності сенсу (≥) вводимо базову змінну x 3 зі знаком мінус. У 2-й нерівності сенсу (≤) вводимо базову змінну x 4 . У 3-й нерівності сенсу (≤) вводимо базову змінну x 5 .

Введемо штучні змінні : в 1-й рівності вводимо змінну x 6 ;

Для постановки завдання мінімум цільову функцію запишемо так: .

За використання штучних змінних, що вводяться в цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.

Отриманий базис називається штучним, а метод розв'язання називається методом штучного базису.

Причому штучні змінні немає відношення до змісту поставленого завдання, проте дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення і забезпечити допустимість оптимального рішення.

З рівнянь виражаємо штучні змінні: x 6 = 4-x 1 -x 2 +x 3 які підставимо в цільову функцію: або.

Матриця коефіцієнтів
цієї системи рівнянь має вигляд:
.

Розв'яжемо систему рівнянь щодо базисних змінних: x 6 , x 4 , x 5.

Вважаючи, що вільні змінні дорівнюють 0, отримаємо перший опорний план:

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

Базисне рішення називається допустимим, якщо воно невід'ємне.

	x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Поточний опорний план не є оптимальним, оскільки в індексному рядку знаходяться позитивні коефіцієнти. Як ведучий виберемо стовпець, відповідний змінної x 2 так як це найбільший коефіцієнт. Обчислимо значення D i і їх виберемо найменше: min(4: 1 , 2: 2 , 10: 2) = 1.

Отже, другий рядок є провідним.

Роздільний елемент дорівнює (2) і знаходиться на перетині провідного стовпця та провідного рядка.

	x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Формуємо наступну частину сімплексної таблиці. Замість змінної x 4 план 1 увійде змінна x 2 .

Рядок, що відповідає змінній x 2 у плані 1, отримана в результаті поділу всіх елементів рядка x 4 плану 0 на роздільну здатність елемент РЕ=2. На місці роздільного елемента отримуємо 1. В інших клітинах стовпця x 2 записуємо нулі.

Таким чином, у новому плані 1 заповнені рядок х 2 і стовпець х 2 . Решта всіх елементів нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

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

Поточний опорний план неоптимальний, оскільки в індексному рядку є позитивні коефіцієнти. Як ведучий виберемо стовпець, відповідний змінної x 1, оскільки це найбільший коефіцієнт. Обчислимо значення D iпо рядках як приватне від поділу: і їх виберемо найменше: min (3: 1 1 / 2 , - , 8: 2) = 2.

Отже, перший рядок є провідним.

Роздільний елемент дорівнює (1 1 / 2) і знаходиться на перетині провідного стовпця та провідного рядка.

	x 1	x 2	x 3	x 4	x 5	x 6
x 6	1 1 / 2
x 2
x 5
	-1 1 / 2 +1 1 / 2 M

Формуємо наступну частину сімплексної таблиці. Замість змінної x6 у план 2 увійде змінна x1.

Отримуємо нову симплекс-таблицю:

	x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Серед значень індексного рядка немає позитивних. Тому ця таблиця визначає оптимальний план завдання.

Остаточний варіант симплекс-таблиці:

	x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Так як в оптимальному рішенні відсутні штучні змінні (вони дорівнюють нулю), то дане рішенняє допустимим.

Оптимальний план можна записати так: x1=2, x2=2:.

Відповідь:
,
.

3. Фірма «Три товстуни» займається доставкою м'ясних консервів із трьох складів, розташованих у різних точках міста в три магазини. Запаси консервів, що є на складах, а також обсяги замовлень магазинів та тарифи на доставку (в умовних грошових одиницях) представлені у транспортній таблиці.

Знайти план перевезень, що забезпечує найменші грошові витрати (початковий план перевезень виконати методом «північно-західного кута»).

Рішення

Перевіримо необхідну та достатню умову розв'язності задачі:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Умови балансу дотримуються. Запаси дорівнюють потребам. Отже, модель транспортного завдання закрита.

Занесемо вихідні дані у розподільчу таблицю.





Потреби

Використовуючи метод північно-західного кута, збудуємо перший опорний план транспортного завдання.

План починається заповнюватися з верхнього лівого кута.

Шуканий елемент дорівнює 4. Для цього елемента запаси дорівнюють 300, потреби 250. Оскільки мінімальним є 250, то віднімаємо його: .

			300 - 250 = 50


250 - 250 = 0

Шуканий елемент дорівнює 2. Для цього елемента запаси дорівнюють 50, потреби 400. Оскільки мінімальним є 50, то віднімаємо його: .

			50 - 50 = 0


	400 - 50 = 350

Шуканий елемент дорівнює 5. Для цього елемента запаси дорівнюють 300, потреби 350. Оскільки мінімальним є 300, то віднімаємо його:


			300 - 300 = 0

	350 - 300 = 50

Шуканий елемент дорівнює 3. Для цього елемента запаси дорівнюють 200, потреби 50. Оскільки мінімальним є 50, то віднімаємо його:



			200 - 50 = 150
	50 - 50 = 0

Шуканий елемент дорівнює 6. Для цього елемента запаси дорівнюють 150, потреби 150. Оскільки мінімальним є 150, то віднімаємо його:



			150 - 150 = 0
		150 - 150 = 0





Потреби

Побудуємо на площині безліч допустимих рішень системи лінійних нерівностейта геометрично знайдемо мінімальне значення цільової функції.

Будуємо в системі координат х 1 ох 2 прямі

Знаходимо напівплощини, що визначаються системою. Так як нерівності системи виконується для будь-якої точки з відповідної напівплощини, їх достатньо перевірити для будь-якої однієї точки. Використовуємо точку (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 неможливе, і ми отримали оптимальний план.

Якщо задачі лінійного програмування є лише дві змінні, її можна вирішити графічним методом.

Розглянемо задачу лінійного програмування з двома змінними та :
(1.1) ;
(1.2)
Тут є довільні числа. Завдання може бути як на знайдення максимуму (max), так і на знайдення мінімуму (min). У системі обмежень можуть бути як знаки, і знаки.

Побудова області допустимих рішень

Графічний метод розв'язання задачі (1) наступний.
Спочатку ми проводимо осі координат і вибираємо масштаб. Кожна з нерівностей системи обмежень (1.2) визначає напівплощину, обмежену відповідною прямою.

Так, перша нерівність
(1.2.1)
визначає напівплощину, обмежену прямою . З одного боку від цієї прямої, а з іншого боку. На самій прямій. Щоб дізнатися, з якого боку виконується нерівність (1.2.1), ми вибираємо довільну точку, що не лежить на прямий. Далі підставляємо координати цієї точки (1.2.1). Якщо нерівність виконується, то напівплощина містить вибрану точку. Якщо нерівність не виконується, напівплощина розташована з іншого боку (не містить обрану точку). Заштриховуємо напівплощину, на яку виконується нерівність (1.2.1).

Те саме виконуємо для інших нерівностей системи (1.2). Так ми отримаємо заштрихованих напівплощин. Точки області допустимих рішень задовольняють всі нерівності (1.2). Тому, графічно, область допустимих рішень (ОДР) є перетином всіх побудованих напівплощин. Заштриховуємо ОДР. Вона є опуклим багатокутником, грані якого належать побудованим прямим. Також ОДР може бути необмеженою опуклою фігурою, відрізком, променем чи прямою.

Може виникнути і такий випадок, що напівплощини не містять загальних точок. Тоді областю допустимих рішень є безліч. Таке завдання рішень немає.

Можна спростити метод. Можна не заштрихувати кожну напівплощину, а спочатку збудувати всі прямі
(2)
Далі вибрати довільну точку, що не належить жодній із цих прямих. Підставити координати цієї точки у систему нерівностей (1.2). Якщо всі нерівності виконуються, то область допустимих рішень обмежена побудованими прямими і включає обрану точку. Заштриховуємо область допустимих рішень за межами прямих так, щоб воно включало обрану точку.

Якщо хоча б одна нерівність не виконується, вибираємо іншу точку. І так далі, доки не буде знайдено одну точку, координати якої задовольняють системі (1.2).

Знаходження екстремуму цільової функції

Отже, маємо заштриховану область допустимих рішень (ОДР). Вона обмежена ламаною, що складається з відрізків та променів, що належать побудованим прямим (2). ОДР завжди є опуклим безліччю. Воно може бути як обмеженою безліччю, так і не обмеженим вздовж деяких напрямків.

Тепер ми можемо шукати екстремум цільової функції
(1.1) .

Для цього вибираємо будь-яке число і будуємо пряму
(3) .
Для зручності подальшого викладу вважаємо, що ця пряма проходить через ОДР. На цій прямій цільова функція постійна і рівна. така пряма називається лінією рівня функції. Ця пряма розбиває площину на дві напівплощини. На одній півплощині
.
На іншій напівплощині
.
Тобто з одного боку від прямої (3) цільова функція зростає. І що далі ми відсунемо крапку від прямої (3), то більше значення буде . З іншого боку від прямої (3) цільова функція зменшується. І що далі ми відсунемо точку від прямої (3) в іншу сторону, тим менше буде значення . Якщо ми проведемо пряму, паралельну до прямої (3), то нова пряма також буде лінією рівня цільової функції, але з іншим значенням .

Таким чином, щоб знайти максимальне значення цільової функції, треба провести пряму, паралельну прямій (3), максимально віддалену від неї у бік зростання значень і проходить хоча б через одну точку ОДР. Щоб знайти мінімальне значення цільової функції, треба провести пряму, паралельну прямій (3) і максимально віддалену від неї у бік зменшення значень, і проходить хоча б через одну точку ОДР.

Якщо ОДР необмежена, може виникнути випадок, коли таку пряму провести не можна. Тобто як би ми не видаляли пряму від лінії рівня (3) у бік зростання (зменшення), то пряма завжди проходитиме через ОДР. В цьому випадку може бути як завгодно великим (малим). Тому максимального (мінімального) значення немає. Завдання рішень немає.

Розглянемо випадок, коли крайня пряма, паралельна довільному прямому виду (3), проходить через одну вершину багатокутника ОДР. З графіка визначаємо координати цієї вершини. Тоді максимальне (мінімальне) значення цільової функції визначається за такою формулою:
.
Розв'язанням задачі є
.

Також може зустрітися випадок, коли пряма паралельна до однієї з граней ОДР. Тоді пряма проходить через дві вершини багатокутника ОДР. Визначаємо координати цих вершин. Для визначення максимального (мінімального) значення цільової функції можна використовувати координати будь-якої з цих вершин:
.
Завдання має безліч рішень. Рішенням є будь-яка точка, розташована на відрізку між точками та , включаючи самі точки та .

Приклад розв'язання задачі лінійного програмування графічним методом

Умова задачі

Фірма випускає сукні двох моделей А та В. При цьому використовується тканина трьох видів. На виготовлення однієї сукні моделі А потрібно 2 м тканини першого виду, 1 м тканини другого виду, 2 м тканини третього виду. На виготовлення однієї сукні моделі потрібно 3 м тканини першого виду, 1 м тканини другого виду, 2 м тканини третього виду. Запаси тканини першого виду становлять 21 м, другого виду – 10 м, третього виду – 16 м. Випуск одного виробу типу А приносить дохід 400 ден. од., одного виробу типу В – 300 ден. од.

Скласти план виробництва, що забезпечує фірмі максимальний дохід. Завдання вирішити графічним способом.

Рішення

Нехай змінні та означають кількість вироблених суконь моделей А та В, відповідно. Тоді кількість витраченої тканини першого виду становитиме:
(м)
Кількість витраченої тканини другого виду становитиме:
(м)
Кількість витраченої тканини третього виду складе:
(м)
Оскільки вироблена кількість суконь не може бути негативною, то
та .
Дохід від вироблених суконь складе:
(Ден. од.)

Тоді економіко-математична модель завдання має вигляд:

Вирішуємо графічним способом.
Проводимо осі координат і .

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 7) та (10,5; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 10) та (10; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 8) та (8; 0).

Заштрихуємо область, щоб точка (2; 2) потрапила до заштрихованої частини. Отримуємо чотирикутник OABC.

(П1.1) .
При .
При .
Проводимо пряму через точки (0; 4) та (3; 0).

Далі помічаємо, оскільки коефіцієнти при і цільової функції позитивні (400 і 300), вона зростає зі збільшенням і . Проводимо пряму, паралельну до прямої (П1.1), максимально віддалену від неї у бік зростання , і проходить хоча б через одну точку чотирикутника OABC. Така пряма проходить через точку C. З побудови визначаємо її координати.
.

Рішення задачі: ;

Відповідь

.
Тобто для отримання найбільшого доходу необхідно виготовити 8 суконь моделі А. Дохід при цьому складе 3200 ден. од.

Приклад 2

Умова задачі

Розв'язати задачу лінійного програмування графічним методом.

Рішення

Вирішуємо графічним способом.
Проводимо осі координат і .

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 6) та (6; 0).

Будуємо пряму.
Звідси.
При .
При .
Проводимо пряму через точки (3; 0) та (7; 2).

Будуємо пряму.
Будуємо пряму (вісь абсцис).

Область допустимих рішень (ОДР) обмежена побудованими прямими. Щоб дізнатися, з якого боку, зауважуємо, що точка належить ОДР, оскільки задовольняє системі нерівностей:

Заштриховуємо область за межами побудованих прямих, щоб точка (4; 1) потрапила до заштрихованої частини. Отримуємо трикутник ABC.

Будуємо довільну лінію рівня цільової функції, наприклад,
.
При .
При .
Проводимо пряму лінію рівня через точки (0; 6) та (4; 0).
Оскільки цільова функція збільшується зі збільшенням і , то проводимо пряму, паралельну лініїрівня та максимально віддалену від неї у бік зростання , і проходить хоча б через одну точку трикутника АВС. Така пряма проходить через точку C. З побудови визначаємо її координати.
.

Рішення задачі: ;

Відповідь

Приклад відсутності рішення

Умова задачі

Розв'язати графічно завдання лінійного програмування. Знайти максимальне та мінімальне значення цільової функції.

Рішення

Розв'язуємо задачу графічним методом.
Проводимо осі координат і .

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 8) та (2,667; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 3) та (6; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (3; 0) та (6; 3).

Прямі є осями координат.

Область допустимих рішень (ОДР) обмежена побудованими прямими та осями координат. Щоб дізнатися, з якого боку, зауважуємо, що точка належить ОДР, оскільки задовольняє системі нерівностей:

Заштрихуємо область, щоб точка (3; 3) потрапила до заштрихованої частини. Отримуємо необмежену область, обмежену ламаною ABCDE.

Будуємо довільну лінію рівня цільової функції, наприклад,
(П3.1) .
При .
При .
Проводимо пряму через точки (0; 7) та (7; 0).
Оскільки коефіцієнти при позитивні, то зростає при збільшенні і .

Щоб знайти максимум, потрібно провести паралельну пряму, максимально віддалену у бік зростання і проходить хоча б через одну точку області ABCDE. Однак, оскільки область необмежена з боку великих значеньі таку пряму провести не можна. Яку б пряму ми провели, завжди знайдуться точки області, більш віддалені убік збільшення і . Тому максимуму немає. можна зробити як завгодно великий.

Шукаємо мінімум. Проводимо пряму, паралельну до прямої (П3.1) і максимально віддалену від неї у бік спадання , і проходить хоча б через одну точку області ABCDE. Така пряма проходить через точку C. З побудови визначаємо її координати.
.
Мінімальне значенняцільової функції:

Відповідь

Максимального значення немає.
Мінімальне значення
.