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

У разі завдання із двома змінними.

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

1.Побудуємо на площині xOy область допустимих рішень.
2.Виділимо область невід'ємних рішень.

4. Побудуємо сімейство цільових функцій.
5. Знаходимо максимальне (мінімальне) значення цільової функції.

1. Будуємо область допустимих розв'язків задачі (D).

Для побудови області допустимих рішень:
1) Будуємо граничні прямі:
перетворимо нерівності до рівностей, а потім до рівняння прямої лінії у відрізках на осях виду \(\frac(x)(a)+\frac(y)(b) = 1\), тоді \(x=a\) - відрізок що відсікається на осі Ox, \(y=b\) - на осі Oy $$ \begin(cases) 2x+3y = 6 3x-2y = 18 -x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac(y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Для кожної прямої відкладаємо відрізки на осях і з'єднуємо їх. Отримали потрібні прямі.

2) Знаходимо напівплощини, які задовольняють заданим нерівностям:
Для нерівності \(2x+3y\geq 6\) - напівплощина, яка лежить вище за пряму \(2x+3y = 6\). Пряма AC
Для нерівності \(3x-2y\leq 18 => -3x+2y \geq -18\)- напівплощина, яка лежить вище за пряму \(3x-2y = 18\). Пряма CB
Для нерівності \(-x + 2y \ leq 8 \) - напівплощина, яка лежить нижче прямої \ (-x + 2y = 8 \). Пряма AB

Область допустимих рішень визначається як загальна частина трьох напівплощин, що відповідають даним нерівностям. Ця область є трикутником \(ABC\)

Областью (D) є трикутник (ABC) див. рис.

2.Виділимо область невід'ємних рішень.

Область невід'ємних рішень розташована в першій чверті і є загальною частиною всіх п'яти напівплощин, три з яких - область \(D\), отримана з нерівностей і додатково дві нерівності \(x \geq 0\) - верхня напівплощина (I і II чверті) та \(y \geq 0\) - права напівплощина (I і IV чверті), які виражають умову невід'ємності змінних \(x;y\). Отримали потрібну область невід'ємних рішень (DEBFG)

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

4. Будуємо сімейство цільових функцій.
Рівняння \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) визначає на площині xOy сімейство концентричних кіл з центом у точці з координатами \(Q(4 ;3)\), кожній з яких відповідає певне значення параметра \(f\). Як відомо, для рівняння кола параметр \(f=R^2\).

Зобразимо в одній системі координат сімейство концентричних кіл і сімейство прямих. Завдання визначення точки максимуму (мінімуму) точки (f) зведеться до знаходження в допустимій області точки, через яку проходить коло сімейства (f = const), що відповідає за найбільше (найменше) значення параметра (f).

5. Знаходимо максимальне (мінімальне) значення цільової функції.

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

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

Можна переконатися в правильності рішення шляхом підстановки координат вершин, що залишилися, в рівняння цільової функції:
у вершині \(D(0;2)\) значення цільової функції дорівнює \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
у вершині \(E(0;4)\) значення цільової функції дорівнює \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
у вершині \(F(6;0)\) значення цільової функції дорівнює \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Отримали, що

Відповідь:
мінімальне значення цільової функції \(f_(min) = 10\)
максимальне значення цільової функції (f_(max) = 137.25)

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

Приклади

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

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

( F 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. Постановка основного завдання лінійного програмування

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

,

.

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

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

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

ТЕМА: ЛІНІЙНЕ ПРОГРАМУВАННЯ

ЗАВДАННЯ 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; 1). У цьому Ф 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).

Розділимо третій рядок на ключовий елемент, що дорівнює 5, отримаємо третій рядок нової таблиці.

Базовим стовпцям відповідають поодинокі стовпці.

Розрахунок інших значень таблиці:

«БП – Базовий План»:

; ;

«х1»: ; ;

«х5»: ; .

Значення індексного рядка невід'ємні, отже отримуємо оптимальне рішення: ; .

Відповідь:максимальний прибуток від виготовленої продукції, рівну 160/3 од., забезпечує випуск лише продукції другого типу у кількості 80/9 одиниць.

Завдання №2

Дано завдання нелінійного програмування. Знайти максимум та мінімум цільової функції графоаналітичним методом. Скласти функцію Лагранжа і показати, що у точках екстремуму виконуються достатні умови мінімуму (максимуму).

Т.к. остання цифра шифру дорівнює 8, то А = 2; В=5.

Т.к. передостання цифра шифру дорівнює 1, слід вибрати завдання № 1.

Рішення:

1) Накреслимо область, яку задає система нерівностей.

Ця область – трикутник АВС із координатами вершин: А(0; 2); В(4; 6) та С(16/3; 14/3).

Рівні цільової функції є кола з центром у точці (2; 5). Квадрати радіусів будуть значеннями цільової функції. Тоді малюнку видно, що мінімальне значення цільової функції досягається у точці Н, максимальне – або у точці А, або у точці З.

Значення цільової функції у точці А: ;

Значення цільової функції у точці З: ;

Значить, найбільше значення функції досягається в точці А (0; 2) і 13.

Знайдемо координати точки Н.

Для цього розглянемо систему:

ó

ó

Пряма є дотичною до кола, якщо рівняння має єдине рішення. Квадратне рівняннямає єдине рішення, якщо дискримінант дорівнює 0.

Тоді ; ; - Мінімальне значення функції.

2) Складемо функцію Лагранжа для знаходження мінімального рішення:

При x 1 =2.5; x 2 =4.5 отримаємо:

ó

Система має рішення за , тобто. достатні умови екстремуму виконуються.

Складемо функцію Лагранжа для знаходження максимального рішення:

Достатні умови екстремуму:

При x 1 =0; x 2 =2 отримаємо:

ó ó

Система також має рішення, тобто. достатні умови екстремуму виконуються.

Відповідь:мінімум цільової функції досягається при ; ; максимум цільової функції досягається при ; .

Завдання №3

Двом підприємствам виділяються кошти у кількості dодиниць. При виділенні першому підприємству на рік xодиниць коштів воно забезпечує дохід k 1 xодиниць, а при виділенні другому підприємству yодиниць коштів, воно забезпечує дохід k 1 yодиниць. Залишок коштів до кінця року для першого підприємства дорівнює nx, а для другого my. Як розподілити всі кошти протягом 4-х років, щоби загальний дохід був найбільшим? Завдання вирішити шляхом динамічного програмування.

i=8, k=1.

A=2200; k 1 =6; k 2 = 1; n=0.2; m=0.5.

Рішення:

Весь період тривалістю 4 роки розбиваємо на 4 етапи, кожен із яких дорівнює одному року. Пронумеруємо етапи, починаючи з першого року. Нехай Х k та Y k – кошти, виділені відповідно підприємствам А та В на k – тому етапі. Тоді сума Х k + Y k = а k є загальною кількістю коштів, що використовуються на k - тому етапі і залишилися від попереднього етапу k - 1. На першому етапі використовуються всі виділені кошти та а 1 = 2200 од. дохід, який буде отримано на k – тому етапі, при виділенні Х k та Y k одиниць становитиме 6Х k + 1Y k . нехай максимальний дохід, отриманий останніх етапах починаючи з k – того етапу становить f k (а k) од. запишемо функціональне рівняння Беллмана, що виражає принцип оптимальності: який би був початковий стан і початкове рішення наступне рішення має бути оптимальним стосовно стану, одержуваному результаті початкового стану:

Для кожного етапу потрібно вибрати значення Х k , а значення Y k=аk- хk. З огляду на це знайдемо дохід на k – тому етапі:

Функціональне рівняння Беллмана матиме вигляд:

Розглянемо всі етапи, починаючи з останнього.

(бо максимум лінійної функції досягається в кінці відрізка при х 4 = а 4);

Федеральне агентствоза освітою

Державна бюджетна освітня установа

вищої професійної освіти

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

РОЗРАХУНОВО-ГРАФІЧНА РОБОТА

з дисципліни "ТЕОРІЯ ОПТИМАЛЬНОГО УПРАВЛІННЯ »

на тему "МЕТОДИ ОПТИМІЗАЦІЇ І ДОСЛІДЖЕННЯ ОПЕРАЦІЙ »

варіант 7

Виконав:

студент заочного відділення

4-го курсу групи ЗА-419

ПІБ: Кужельов С. А.

Перевірила:

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

Київ – 2012 р.
^

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

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Крок 1. Побудова допустимої області

Умови невід'ємності змінних і квадратів обмежують область допустимих значень першим квадрантом. Кожному з чотирьох обмежень-нерівностей моделі, що залишилися, відповідає деяка напівплощина. Перетин цих напівплощин з першим квадрантом утворює безліч допустимих розв'язків задачі.

Перше обмеження моделі має вигляд . Замінивши в ньому знак ≤ на знак =, отримуємо рівняння . На рис. 1.1 воно визначає пряму (1), яка розбиває площину на дві напівплощини, в даному випадку вище лінії і нижче за неї. Щоб вибрати, яка з них задовольняє нерівність , підставимо в нього координати будь-якої точки, що не лежить на цій прямій (наприклад, початок координат х 1 = 0, х 2 = 0). Оскільки отримуємо правильне вираз (20 0 + 6 0 = 0 ≤15), то нерівності задовольняє напівплощину, що містить початок координат (позначена стрілкою). В іншому випадку інша напівплощина.

Аналогічно чинимо з іншими обмеженнями завдання. Перетин усіх побудованих напівплощин з першим квадрантом утворює ABCD(Див. рис. 1). Це і є допустима сфера завдання.

Крок 2. Побудова лінії рівня Лінія рівня цільова функція - це безліч точок площини, в яких цільова функція приймає постійне значення. Така множина задається рівнянням f ( x) = const. Припустимо, наприклад, const = 0 і побудуємо лінію біля рівня f ( x) = 0, тобто. у нашому випадку пряму 7 x 1 + 6x 2 = 0.

Ця пряма проходить через початок координат і перпендикулярна вектору. Цей вектор є градієнтом цільової функції у точці (0,0). Градієнт функції - це вектор значень приватних похідних цієї функції у точці, що розглядається. У разі завдання ЛП приватні похідні цільової функції дорівнюють коефіцієнтам Ci, j = 1 , ..., n.

Градієнт показує напрямок якнайшвидшого зростання функції. Переміщуючи лінію рівня цільової функції f ( x) = const. перпендикулярно до напрямку градієнта, знайдемо останню точку, В якій вона перетинається з областю. У нашому випадку це точка D, яка буде точкою максимуму цільової функції (див. рис. 2).

Вона лежить на перетині прямих (2) і (3) (див. рис. 1) і задає оптимальне рішення.

^ Зауважимо, що й потрібно знайти мінімальне значення цільової функції, лінію рівня переміщають у напрямі, протилежному напрямку градієнта.

^ Крок 3. Визначення координат точки максимуму (мінімуму) та оптимального значення цільової функції

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

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Отримаємо оптимальне рішення = 1,33.

^ Оптимальне значення цільової функції f * = f (х *) = 7 * 0 + 6 * 1,33 = 7,8