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

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

з дисципліни

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

Завдання 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
1	0	0	-3
0	0	1	5

З останньої таблиці, яка відповідає системі рівнянь з повністю виключеними змінними, знаходимо розв’язок системи рівнянь:

Завдання 4

 

1)  Розв’язати симплекс-методом задачу лінійного програмування, яка представлена у Завданні 2.

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

3)  Знайти розв’язок двоїстої задачі та дати економічну інтерпретацію отриманого розв’язку.

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

1)  Задача лінійного програмування:

а) Зводимо задачу до канонічної форми введенням додаткових змінних х₃та х₄.

б) Дана задача має початковий опорний план (0;0;6;6;), при якому цільова

 функція дорівнює нулю. У даному опорному плані базисними є додаткові змінні х₃та х₄, а змінні х₁та х₂ є вільними.

 в) Запишемо цільову функцію у вигляді, виразивши її через небазисні змінні,

г) Будуємо симплекс-таблицю, в яку заносимо початковий опорний план:

Базисні змінні	х1	х2	х3	х4	B	Базисний розв’язок
Х3	-1	3	1	0	6	(0;0;6;6)
Х4	3	-1	0	1	6
Z	-1	-1	0	0	0

Даний опорний план не є оптимальним, оскільки рядок цільової функції містить від’ємні значення (коефіцієнти при змінних). Перехід до нового опорного плану, виконуємо шляхом заміни змінної х₃ на змінну х₂. Вибір змінних для заміни базиса обумовлюється тим, що у записі змінної х₃ через небазисні змінні (х₁та х₂) коефіцієнт при змінній х₂ має найбільше негативне значення (-3). Отже, ведучим елементом обираємо а₁₂=3 (у таблиці виділений).

В результаті перехунку таблиці, отримуємо другу таблицю:

Базисні змінні	х1	х2	х3	х4	B	Базисний розв’язок
Х2		1		0	2	(0;2;0;8)
Х4		0		1	8
Z		0		0	2

Отриманий опорний план не є оптимальним, оскільки рядок цільової функції містить від’ємне значення (а₃₁=). Для переходу до нового базису і, відповідно нового опорного плану, обираємо ведучим елементом а₂₁= (він лежить у стовпчику, де знаходиться негативний коефіцієнт у виразі цільової функції, і є позитивним). В результаті перехунку, отримуємо наступну таблицю:

Базисні змінні	х1	х2	х3	х4	B	Базисний розв’язок
Х2	0	1			3	(3;3;0;0)
Х1	1	0			3
Z	0	0			6

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

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

2)Двоїста задача лінійного програмування формулюється відносно двоїстих змінних у₁, у₂ і утворюється шляхом транспонування матриці коефіцієнтів обмежень, взаємної заміни коефіцієнтів цільової функції і вільних членів системи обмежень і зміни типу нерівностей (>= на <= і навпаки), а також зміни критерія оптимізація цільової функції на протилежний (максимізація на мінімізацію і навпаки).

Двоїста задача:

2)Розв’язання двоїстої задачі виконуємо за допомогою процесора електронних таблиць MS Excel.

Створюємо робочий лист з математичною моделлю задачі, який наведено на малюнку:

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

Розв’язок задачі (оптимальний план двоїстої задачі) міститься у комірках В2 (змінна у₁), С2 (змінна у₂):

у₁ = 0,5; у₂:= 0,5

Вікно MS Excel з розв’язком задачі:

 

Економічна інтерпретація задачі.

Будемо розглядати пряму задачу як задачу про оптимальне використання обмежених ресурсів. Підприємство виготовляє два види продукції П1 і П2 у кількостях х₁та х₂ відповідно, використовуючи два види ресурсів Р1 та Р2, запаси яких обмежені і становлять 6 одиниць кожного; нормативи витрат ресурсів на одиницю продукції задані таблицею

	П1	П2
Р1	-1	3
Р2	3	-1

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

Математична модель прямої задачі:

за умов

Математична модель двоїстої задачі:

 

Економічна інтерпретація двоїстої задачі: двоїсті змінні у₁та у₂ – це ціни ресурсів Р1 та Р2 відповідно, і, таким чином, задача полягає у визначенні таких цін використовуваних ресурсів, при яких загальна вартість їх буде мінімальною.

Отриманий оптимальний план двоїстої задачі показує, що оптимальною ціною ресурсів Р1 та Р2 є у₁=0,5 та у₂ = 0,5 грошових одиниць.

Обидва ресурси використовуються повністю і є дефіцитними (оскільки їх двоїсті оцінки більші нуля у₁>0, у₂ > 0). Обидва види продукції є рентабельними (оскільки х₁>0 і х₂ > 0).

Двоїсті оцінки у₁=0,5 та у₂ = 0,5 показують, що величина доходу підприємства (значення цільової функції прямої задачі) збільшиться на 0,5 при збільшенні величини на одиницю величини запасу кожного з ресурсів.

Список використаної літератури

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высш.шк., 1986.

2. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч.–метод. посіб. для самост. вивч. дисц. – К.: КНЕУ, 2001.

3. Кабак Л.Ф., Суворовский А.А. Математическое программирование. – К.: ИМКВО, 1992.

4. Калихман И.А. Сборник задач по математическому программированию. – М.: Высш.шк., 1975.

5. Савчук М.В. Лінійне програмування: Навч. посібник. – К.: ІПК ДСЗУ, 2006.