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

ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

1.1. Для виготовлення трьох видів виробів А, В і С використовується токарне, фрезерне, зварювальне і шліфувальне обладнання. Витрати часу на обробку одного виробу для кожного з типів устаткування зазначені в табл. 1.1. У ній же зазначений загальний фонд робочого часу кожного з типів обладнання, що використовується, а також прибуток від реалізації одного виробу кожного виду.

Таблиця 1.1

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

Розв’язок. Припустимо, що буде виготовлено х ₁одиниць виробів виду А, х ₂одиниць – виду В і х ₃одиниць – виду С. Тоді для виробництва такої кількості виробів потрібно буде затратити 2х ₁+4 х ₂+5х₃ станко-годин фрезерного обладнання.

Так як загальний фонд робочого часу верстатів даного типу не може перевищувати 120, то повинна виконуватись нерівність

2х ₁+4 х ₂+5 х ₃ ≤ 120.

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

х ₁+8 х ₂ +6 х ₃ ≤ 280

7 х ₁+4 х ₂ +5 х ₃ ≤ 240

4 х ₁+6 х ₂ +7 х ₃ ≤ 360

При цьому так як кількість виготовлених виробів не може бути від’ємною, то

х ₁≥0, х ₂≥0, х ₃≥0 (1)

Далі, якщо буде виготовлено х ₁одиниць виробів виду А, х ₂одиниць виробів виду В і х ₃одиниць виробів виду С, то прибуток від їхньої реалізації складе F= 10 х ₁+14 х ₂+12 х ₃.

Таким чином, приходимо до наступної математичної задачі: дана система

чотирьох лінійних нерівностей із трьома невідомими x_j (j = і лінійна функція відносно цих же змінних

F= 10 х ₁+14 х ₂+12 х ₃; (3)

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

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

Так як функція (3) лінійна, а система (2) містить тільки лінійні нерівності, то задача (1) - (3) є задачею лінійного програмування.