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

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

11

КОНТРОЛЬНА РОБОТА

з дисципліни

„Математичне програмування”

Завдання 1

1) Побудувати математичну модель задачі лінійного програмування.

2) Звести дану задачу до канонічного вигляду.

Діва вироби В1 і В2 обробляються послідовно на трьох верстатах. Кожний виріб типу В1 потребує 1 год. для обробки на першому верстаті, 2 год. - на ІІ-му і А год. - на третьому.

Кожний виріб В2 потребує для обробки 2 год, А год. і 3 год. відповідно на І-му, ІІ-му і ІІІ-му верстатах.

Час роботи на першому верстаті не повинен перевищувати 10N год., на ІІ-му - 15N год., на ІІІ-му - 50 год.

Скласти план виробництва при максимальному прибутку, якщо відомо, що продаж одного виробу типу В1 приносить прибуток 5 грн., а типу В2 - 3 грн.

Примітка: А=, тобто А=.

Розв'язання.

Типи верстатів	Затрати часу, год	Час роботи, год
	В1	В2
І в	1	2	60
ІІ в	2	А	90
ІІІ в	А	3	50
Прибуток, грн	5	3

1) Математична модель задачі.

Позначимо кількість виробів В1 і В2 відповідно х₁ та х₂.

Цільова функція (величина прибутку), яку потрібно максимізувати

Спеціальні обмеження задачі визначаються обмеженнями часу роботи верстатів і нормативами часу обробки виробів на верстатах. При обсягу випуску виробів В1 і В2 відповідно х₁ та х₂ і заданих нормативах часу обробки час роботи першого верстату дорівнює

час роботи другого верстату

час роботи третього верстату

Спеціальні обмеження є наступними:

Загальні обмеження задачі витікають з природи економічних змінних і полягають у тому, що вони не можуть мати від'ємні значення, тобто

Отже маємо математичну модель задачі:

за умов

Словесно задача формулюється таким чином: знайти значення змінних х₁ та х_2, які задовольняють заданій системі обмежень і доставляють максимальне значення цільовій функції Z.

2) У канонічній формі задачі лінійного програмування спеціальні обмеження подаються рівностями. Перехід до канонічної форми здійснюється шляхом введення додаткових (фіктивних) змінних, які перетворюють нерівності на рівності. В даному випадку до першого обмеження вводиться змінна х₃, до другого - х_4, до третього - х_5. Додаткові змінні вводяться зі знаками „+”, оскільки обмеження мають тип „”. Математична модель задачі у канонічній формі:

за умов

Завдання 2

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

за умов

Розв'язання.

В декартовій системі координат х₁Ох₂ будуємо прямі, які визначаються нерівностями системи обмежень. Це прямі ; ; . Кожна пряма ділить площину х₁Ох₂ на дві половини, в одній з яких виконується відповідна нерівність системи обмежень, а в іншій не виконується. Півплощини, в яких виконуються нерівності системи обмежень позначені штриховою біля прямих. Переріз цих півплощин являє собою область припустимих планів задачі. Це - чотирикутник ОАВС.

Цільова функція визначає сімейство паралельних прямих ліній з різними значеннями параметра z. При z=0 маємо пряму , що проходить через початок координат. Збільшенню значення параметра z відповідає переміщення прямої цільової функції у напрямку, позначеному вектором n₊. Безпосередньо з креслення видно, що максимальному значенню параметра z (максимуму цільової функції при заданих обмеженнях) відповідає точка припустимої області, яка є вершиною В чотирикутника ОАВС (це остання точка припустимої області, яка належить прямій цільової функції z при її переміщенні у напрямку збільшення параметра z). Координати (х₁, х₂) цієї точки є шуканим оптимальним планом задачі.

З креслення визначаємо: .

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

Завдання 3

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

змінних з використанням розрахункових таблиць.

Будуємо розрахункову таблицю і обираємо за ведучий елемент а₂₁=1 (у таблиці виділений):

х1	х2	х3	B
3	-2	2	-3
1	4	-1	0
4	-1	4	6

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

х1	х2	х3	B
0	-14	5	-3
1	4	-1	0
0	-17	8	6

Обираємо за ведучий елемент а₁₂=-14 (у таблиці виділений) і, виконавши перерахунок, виключаємо змінну х₂ з другого і третього рівнянь.

Отримуємо таблицю

х1	х2	х3	B
0	1	-5/14	3/14
1	0	3/7	-6/7
0	0	27/14	135/14

Обираємо за ведучий елемент а₃₃=-27/14 (у таблиці виділений) і, виконавши перерахунок, виключаємо змінну х₃ з першого і другого рівнянь. Отримуємо таблицю

х1	х2	х3	B
0	1	0	2