Огляди методів вирішення завдань лінійного програмування. Графічний метод на прикладі

1. Виникнення лінійного програмування
2. Способи вирішення завдань лінійного програмування
3. Практичний приклад застосування графічного методу

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

Корисна сторінка? Збережи або розкажи друзям

Виникнення лінійного програмування

Лінійне програмування виникло на початку минулого століття працями радянського математика Леоніда Канторовича. Великий внесок у розвиток цього напрямку вніс також американець Джордж Данциг, який розробив універсальний симплекс-метод рішення задач лінійного програмування .

Лінійне програмування застосовується в наступних типах завдань:

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

Способи вирішення завдань лінійного програмування

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

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

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

Нехай введена лінійна функція $ Y = 3X + 4Z $ при цьому змінні підкоряються наступним обмеженням: $$ \ left \ {\ begin {array} {l} 0 \ le X \ le 6, \\ 0 \ le Z \ le 4. \ end {array} \ right. $$

Знайдемо значення $ X $ і $ Z $, при яких $ Y $ буде максимальним. Будуємо математичну модель: $$ Y = 3X + 4Z \ rightarrow \ max, $$ $$ \ left \ {\ begin {array} {l} 0 \ le X \ le 6, \\ 0 \ le Z \ le 4. \ end {array} \ right. $$ Малюємо пряму лінію $ 3X + 4Z = 0 $ або $ Z = -3 / 4 X $. Паралельним перенесенням в напрямку градієнта цієї функції $ n = (3,4) $ до правої верхньої вершині отриманого прямокутника допустимих рішень ми отримаємо точку $ (6,4) $. У цій точці функція $ Y $ має максимальне значення, рівне $ Y_ {max} = 34 $.

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

Сподобалося? Додайте в закладки

додатково:

Лінійне програмування на замовлення. Тільки на відмінно.