Тема 3. Методи лінійного програмування

3.1. Коротке теоретичне викладення

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

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

Обмеження характеризують наявні можливості розв'язання завдання.

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

Рішення, що задовольняє умовам завдання і відповідає поставленій меті, називається оптимальним планом.

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

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

В загальному вигляді постановка завдання лінійного програмування полягає ось у чому.

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

j = 1,2,... n; i = 1,2,...,m; m<n; x_j≥0.

де x_j - шукані величини, що містять розв’язання поставленого завдання;

a_ij i b_i – відомі сталі величини, що характеризують умови завдання.

Цільова функція (лінійна форма) надається у вигляді:

де - сталі коефіцієнти (коефіцієнти вартості).

2. Оглядові питання

1. У чому полягає відмінність методу МДО від лінійного програмування?

2. У яких випадках застосовують методи нелінійного програмування?

3. Коли, у яких випадках варто застосовувати методи динамічного програмування?

4. Що собою являє сиплекс-метод?

2. Практичні завдання

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

Витрати	Партія із 10 плит		Наявні ресурси на місяць
	звичайні	покращенні
Матеріал (кг) Час на пересування (год.) Час на обробку (год.) Засоби (грн.)	20 4 4 30	40 6 4 50	4000 900 600 6000

За кожні 10 звичайних плит фірма дістає прибуток 80 грн., а за кожні 10 плит покращеноо виду — 100 грн.

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

Таблиця 2

Дані про завантаженість складів

		Вартість перевезень до споживачів (грн. зі 1 тис. шт.)			Наявність товару (тис. шт.)
		В1	В2	В3
Склади	А1	800	500	600	120
	А2	400	900	700	180
Замовлення (тис.шт.)		70	140	90	300

3. Невелика фірма виробляє два види продукції: столи і стільці. Для виготовлення одного стільця потрібно 3 кг деревини та 2 год робочого часу, а для одного стола — 7 кг та 8 год. Кожний стіл приносить прибуток 15 грн., а стілець — 5 грн. Скільки стільців і столів повинна виробляти фірма, якщо вона мас 420 кг деревини і 400 год робочого часу та хоче отримати максимальний прибуток?