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

За допомогою лінійного програмування керівник може (наприклад) отримати відповіді на такі питання:

1) як краще спланувати час роботи обладнання (машинний час), якщо він обмежений;

2) що продавати в умовах, коли є дозвіл на продаж не всіх видів продукції, робіт;

3) як краще використати обмежену кількість сировини, щоб оптимізувати прибуток;

4) як спланувати транспортні маршрути для доставки…

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

Задача 5.1.

В задачі є 2 обмеження: кількості продажу продуктів А і Б та машинного часу.

Таблиця 5.1 Умова задачі лінійного програмування з двома обмеженнями.

Цільва функція: зробити виручку махимальною 2* А +3* Б.

Виробниче обмеження часу: 1*А + 2*Б <= 2000; Обмеження обсягу реалізації А <= 1500; Б <=800.

Дані можна ввести в програму і отримати результат: А = 1500; Б = 250.

у

1500

0

500 1000 1500 х

Така задача вирішується і геометричним методом (Рис 6.1). По осі х позначене обмеження обсягу реалізації прод Б; по осі у – прод А. Далі – позначається на графіку виробниче обмеження: 1*А + 2*Б <= 2000. Якщо взяти Б =0, то А = 2000; при А = 0, Б = 1000. Позначимо на графіку точки по у 2000 та по х 1000 і з’єднуємо їх прямою.

Оптимальне рішення можке бути в точці х1 або в точці у1. Точка x1 має координати: 1500 А та 250 Б; точка у1 – 400А та 800Б. В точці х1 виручка = 1500*2 + 250*3 = 3750 грн; В точці у1 = 400*2 + 800*3 = 3200 грн. Якщо прибуток на 1 год машинного часу для прод-ів А і Б будуть однакові, то оптимальне рішення буде в будь-якій точці прямої Х1У1.

Графічний метод можна використовувати для 2-х подуктів та для 3-х – коли треба будувати сиситему координат у 3-х вимірах. А якщо продукти виготовляти на двох різних типах обладнання, то – в 6-ти вимірах.

Таку просту задачу можна розв’язати і не графічно. Якщо відомо, що за 1год машинного часу виручка при виробництві прод А становить 2грн, а для прод Б – 1,5грн (3грн/2год), то при вирішенні треба мах використати машиний час для для виготовлення прод А, тобто 1500кг (займе 1500год/1грн/кг); а залишок машиного часу (500год) – на прод Б – 250кг (500год *2год/кг). Також маємо: 1500 А і 250 Б.

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

Таблиця 5.2 Вхідні дані для задачі лінійного програмування

Через Ts позначено час роботи спец обладнання, через Tz ‑ обладнання загального призначення. Тоді цільова функція буде:

4*А* Ts + 3*Б* Ts +3*В* Ts +3*А* Tz + 4*Б* Tz + 2*В* Tz = ‑‑‑ max.

Виробничі обмеження:

Щодо спец обладнання:

1,5*А*Ts <= 1500; 2*Б*Ts <= 1000; 1*В*Ts <= 800.

щодо обладнання загального призначення:

2*А* Tz + 3*Б* Tz + 2*В* Tz <= 4000.

Обмеження обсягу продажу:

А*Ts + А*Tz <= 1800; Б*Ts + Б*Tz* <= 900; В*Ts + В*Tz <= 1000.

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

Далі цільова функція і обмеження вводяться в програму і результати – в Табл 5.3.

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

Поиск по сайту: