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

Завдання 1

Цех випускає вали і втулки. На виробництво одного вала робочий витрачає 3 год., однієї втулки – 2 год. Від реалізації одного вала підприємство одержує прибуток 80 грн., а від реалізації однієї втулки – 60 грн. Цех має випустити не менше 100 валів і не менше 200 втулок. Скільки валів і скільки втулок має випустити цех, щоб одержати найбільший прибуток, якщо фонд робочого часу робітників становить 900 людино-годин?

Розв’язок

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

∫ = 80х1+60х2.

Витрати ресурсів на виготовлення такої кількості виробів складають відповідно:

CI =3х1+2х2,

Оскільки запаси ресурсів обмежені, то повинні виконуватись нерівності:

3х1+2х2≤900

Окрім того, валів потрібно виготовити не менше 100 штук, а втулок – 200 шт., тобто повинні виконуватись ще нерівності: х1≥ 100, х2≥ 200.

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

Знайти х1, х2 такі, що функція ∫ = 80х1+60х2 досягає максимуму при системі обмежень:

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

Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних. Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.

3x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 900

1x1 + 0x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 100

0x1 + 1x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 200

Для постановки задачі на максимум цільову функцію запишемо так:

F(X) = 80 x1 +60 x2 - M x6 - M x7 => max

Отриманий базис називається штучним, а метод рішення називається методом штучного базису.

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

З метою формулювання задачі для вирішення її в табличній формі скористаємося виразами з системи рівнянь для штучних змінних:

x6 = 100-x1 +x4

x7 = 200-x2 +x5

які підставимо в цільову функцію:

F(X) = 80x1 + 60x2 - M(100-x1 +x4 ) - M(200-x2 +x5 ) => max

або

F(X) = (80+1M)x1 +(60+1M)x2 +(-1M)x4 +(-1M)x5 +(-300M) => max

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд: