Тема: Задачі лінійного програмування

↑

⇐ ПредыдущаяСтр 13 из 17Следующая ⇒

Лекція 11

План:

1. Приклади задач лінійного програмування.

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

3. Геометричний зміст задачі лінійного програмування.

Короткий зміст лекції:

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

Лінійне програмування – це галузь прикладної математики, яка розвинулась у 40-х–50-х роках ХХ століття у зв’язку з розв’язуванням економічних задач.

Економічні задачі – це екстремальні задачі на відшукання найбільш вигідного варіанту. В кожній з них треба відповісти на питання: як розпорядитися наданими нам обмеженими ресурсами, щоб одержати найбільший ефект.

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

 Приклад 1. На підприємстві, яке випускає вироби двох типів, виробнича потужність цеху зборки складає 100 виробів першого або 300 виробів другого типу на добу; в той же час відділ технічного контролю може перевірити не більш 150 виробів (будь-якого типу) на добу. Відомо, що виріб першого типу коштує вдвічі дорожче виробу другого типу. Треба при цих умовах знайти такий план випуску продукції, який забезпечував би підприємству найбільший прибуток.

Шуканий план випуску продукції задається за допомогою двох невід’ємних цілих чисел х, у (х – кількість виробів першого типу, у – другого), які повинні задовольняти наступним умовам:

Інакше кажучи, серед невід’ємних цілих розв’язків системи:

(1)

треба вибрати такий, при якому лінійна функція f = 2х +у  приймає найбільше значення.

Якщо на площині ввести прямокутну систему хОу, то множина розв’язків системи (1) зображується за допомогою заштрихованого многокутника (мал. 1).

З малюнку видно, що розв’язком задачі є точка Р – одна з вершин многокутника. Дійсно, розглянемо пряму 2х + у = С, С – деяке число. Позначимо цю пряму . З ростом числа С пряма  зміщується «вгору» (залишаючись паралельною своєму вихідному положенню).

                    y          

           300

                   150

           100                     P(75, 75)           

                        50   100             150                 300 x         

                                                                                  x + y = 150

             2x + y = 0 2x + y = C   2x + y = 225

                     (C = 0) (C = 100 < 225)          

Мал. 1

Найбільшим значенням С, при якому пряма  ще має спільні точки з заштрихованим многокутником, є те значення С, при якому ця пряма проходить через точку Р. Отже, в цій точці функція 2х + у досягає свого найбільшого значення (в порівнянні з її значеннями в інших точках многокутника).

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

Приклад 2.  Задача про дієту.

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

Розглянемо просту математичну модель цієї задачі.

Нехай є два види продуктів,  і , які містять поживні речовини А,В,С . Відомо, скільки поживної речовини того чи іншого виду міститься в 1 кг продуктів  або ; ці відомості вказані в таблиці:

А

В

С

В 1 кг

В 1 кг

Крім цих даних, нам відомі: а, b, с – добові потреби організму в А, В, С (відповідно) і ,  – вартість 1 кг продуктів ,  (відповідно).

Треба розрахувати кількість  продукту  і кількість  продукту  так, щоб забезпечити необхідну кількість поживних речовин при мінімальних витратах на харчі.

Очевидно, загальна вартість харчів буде:

.

Загальна кількість речовини А в обох видах їжі дорівнює . Вона повинна бути не менше а: .

Аналогічні нерівності повинні використовуватись для В і С: ; .

Отже, одержуємо наступну задачу:

Дано систему:

(2)

трьох лінійних нерівностей з двома невідомими  і  та лінійна функція . Треба серед невід’ємних розв’язків ( , ) системи (2) вибрати такий, при якому функція S досягає найменшого значення (мінімізується).

Приклад 3. Транспортна задача.

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

Будемо вважати, що сумарні запаси рівні сумарним потребам:

+ = + + .

Нарешті, задані числа  – вартості перевезення тони вугілля з  в . Задача полягає в знаходженні шести чисел  де  – кількість вугілля для відправки з  в .

Складемо для зручності таблицю:

В

В

В

Всього відправлено

З

З

Всього привезено

Загальна кількість вугілля, вивезеного з , дорівнює , звідси маємо умову: . Аналогічна умова повинна виконуватися для : .

Загальна кількість вугілля, привезеного в , дорівнює , звідси: .

Аналогічно одержуємо умови:

, .

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

Отже, одержуємо наступну задачу: дано систему

(3)

та лінійна функція S. Треба серед невід’ємних розв’язків системи (3) вибрати такий, при якому функція S досягає найменшого значення (мінімізується).

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

а) ці значення були невід’ємними;

б) ці значення задовольняли деякій системі лінійних рівнянь або лінійних нерівностей;

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

Загальне формулювання задачі лінійного програмування.

Задано систему рівнянь та нерівностей:

(4)

та лінійну функцію: . Треба знайти розв’язок системи (4), при якому функція f максимізується (або мінімізується).

Така задача називається загальною задачею лінійного програмування. Система (4) називається системою обмежень, а лінійна функція f – цільовою функцією.

Кожний розв’язок системи (4) називається допустимим розв’язком.

Розв’язок системи (4), при якому цільова функція f досягає максимуму (або мінімуму) називається оптимальним розв’язком задачі лінійного програмування, а mах f (min f) – оптимальним значенням задачі.

Якщо задача має оптимальний розв’язок, вона називається розв’язною, в противному випадку – нерозв’язною (якщо функція f не обмежена зверху або знизу на множині розв’язків системи (4)).

Задача знаходження невід’ємного розв’язку системи лінійних нерівностей:

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

Стандартна та канонічна задачі можуть бути перетвореними одна в другу.

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

,

причому будь-який невід’ємний розв’язок отриманої системи  дає невід’ємний розв’язок  для заданої системи обмежень стандартної задачі.

Значення f не залежить від , і тому завжди можна замінити задану систему лінійних нерівностей побудованою системою лінійних рівнянь, тобто перетворити стандартну задачу в канонічну.

Якщо задана канонічна задача, то замінюючи кожне рівняння системи її обмежень  двома лінійними нерівностями:

,

одержуємо стандартну задачу лінійного програмування.

Стандартну задачу можна тлумачити геометрично.

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

Значення цільової функції  в точці  можна розглядати як відхилення точки Х від гіперплощини .

Відхилення точки Х пропорційно відстані точки Х від цієї гіперплощини. Отже, з геометричної точки зору стандартна задача лінійного програмування полягає в знаходженні в многограннику М точки, яка найбільше (найменше) відхилена від гіперплощини.

Контрольні питання для самоперевірки:

1. Що вивчає математична дисципліна лінійне програмування?

2. Наведіть приклади задач лінійного програмування.

3. Сформулюйте загальну задачу лінійного програмування?

4. Що розуміють під системою обмежень і цільовою функцією в задачі лінійного програмування?

5. Який розв’язок називається допустимим? Оптимальним?

6. Сформулюйте стандартну задачу лінійного програмування?

7. Сформулюйте канонічну задачу?

8. Як перетворити стандартну задачу в канонічну і навпаки?

9. Який геометричний зміст стандартної задачі лінійного програмування?

Література:

1. Завало С.Т., Костарчук В.Н., Хацет Б.И. Алгебра и теория чисел. Ч. ІІ. – К.: Вища шк., 1980. – 402 с., гл. І, §3.1-3.3.

2. С.Г.Колесник, В.В.Цыбуленко. Алгебра и теория чисел. Ч. ІІ. – Х.: ХГПИ, 1992. – Гл. V, §2.1.

3. Солодовников А.С. Системы линейных неравенств. – М.: Наука, 1977. – 112с.

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США