ІІІ. Умови невід’ємності змінних

На базі наведеного математичного опису можна проілюструвати суть цієї моделі так: необхідно визначити значення n невід’ємних змінних , які задовольняють обмеженням 3.2та забезпечують екстремальне значення (максимальне або мінімальне) цільової функції, яка виражена рівнянням 3.1.

До методів вирішення задач ЛП відносяться графічний метод, симплекс-метод. Симплекс-метод є аналітичним методом знаходження рішення задач ЛП.

Приклад. Графічним методом розв’язати задачу лінійного програмування:

Z = 3x1+7x2-5 (extr),

4x1 -3х₂ 12,

10x1 + 13х₂ 130,

- 6х₁ + 8х₂ 48,

2х₁ +5х₂ 10,

4х₁ - х₂ 0,

х ₁ 0,

х ₂ 0.

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

Будуємо граничні прямі, які відповідають нерівностям системи обмежень задачі (кожне обмеження розглядаємо як рівняння). Для побудови довільної прямої нам потрібно дві точки. Якщо права частина рівняння не дорівнює нулю, то для простоти знаходження координат двох точок, через які проходить гранична пряма (наприклад L1), беремо спочатку x1=0 iзнаходимо х₂: 4·0–3х₂=12, звідси – 3х₂=12, а х₂= –4. Ми маємо координати однієї точки (0, -4). Потім підставляємо х₂=0 і визначаємо х1: 4х₁–3 0=12, звідси 4х1=12, а х1=3. Отже, координати другої точки (3,0). Аналогічно знаходимо координати точок для побудови граничних прямих L₂, L₃ та L₄.

В правій частині граничної прямої, що відповідає п'ятому обмеженню - нуль, тому ця пряма проходить через початок координат, отже координати першої точки (0;0). Для визначення координат другої точки беремо довільне значения однієї з невідомих (тільки не 0), наприклад, х1=1 і визначаємо х ₂: -х₂=0, звідси х₂= 4

L1	4x1 -3х2 = 12	(0;-4);	(3;0).
L2:	10x1 + 13х2 = 130	(0;10);	(13;0).
L3	- 6х1 + 8х2 = 48	(0;6);	(-8;0).
L4:	2х1 +5х2 = 10,	(0;2);	(5;0).
L5	4х1 - х2 = 0,	(0;0);	(1;4).
L6	x1 =0,	вісь	Ox 2.
L7	х2 =0,	вісь	Ox 1.

Знаходимо півплощини розв’язків, що відповідають нерівностям системи обмежень. Для цього беремо довільну точку координатної площини, через яку не проходить гранична пряма 4x1 -3х₂ = 12 (для простоти розрахунків візьмемо (0,0)) і підставляємо в першу нерівність. Отримаємо 4 0-3 0<12; 0<12, отже, нерівність справджується. А це значить, що півплощина розв’язків, яка відповідає першому обмеженню задачі, розміщена в напрямку точки (0,0). На рисунку вказуємо стрілкою, в якому напрямку від прямої L1 розміщена півплощина розв’язків. Аналогічні розрахунки проводимо з усіма граничними прямими. Тільки для визначення півплощини розв’язків, що відповідає п’ятому обмеженню, беремо координати довільної точки, що не належить прямій, тільки не точку (0,0), оскільки гранична пряма L₅ проходить через початок системи координат. Шукаємо спільну область, де перетинаються всі півплощини розв’язків. В нашому випадку багатокутником розв’язків є фігура ABCDE.

Будуємо вектор нормалі ={(0;0);(3;7)}. Перпендикулярно до нього - лінію рівнів. Паралельно переносимо цю лінію в напрямку вектора нормалі. Останньою вершиною багатокутника, яку перетне лінія рівнів є точка С - точка максимуму. Тоді паралельно переносимо лінію рівнів у напрямку, протилежному до напрямку вектора нормалі. Крайньою вершиною, яку перетне лінія рівнів, є точка А - точка мінімуму.

 

C

x 2

 

D

 

x1

Рисунок 3.1

Знайдемо координати оптимальних точок і найбільше та найменше значения функції Z. Точка С належить граничним прямим L₂ та L₃, тому її координати обчислимо, розв’язавши систему рівнянь цих граничних прямих:

10x1 + 13х₂ = 130,

- 6х₁ + 8х₂ = 48,

Розв’язком системи є С(2.64; 7.97). Визначимо значення цільової функції в цій екстремальній точці Zmax =Z(C)=58.71.

Аналогічно визначимо координати точки мінімуму та відповідне значення цільової функції. Точка А є перетином прямих L₄ та L5. Запишемо систему відповідних рівнянь та розв'яжемо її.

2х₁ +5х₂ = 10,

4х₁ - х₂ = 0,

Отже, А(0,45; 1,8). Z_mm =Z (A) = 8,95.

Приклад. Симплексним методом розв’язати задачу лінійного програмування: Для виготовлення двох видів продукції П₁ та П₂ використовуються три види сировини S ₁, S ₂ та S ₃. Запаси сировини, норми витрат сировини на виготовлення одиниці продукції кожного виду та оптова ціна одиниці продукції кожного виду наведені в таблиці:

 

 

 

Вид сировини	Запаси сировини	Витрати сировини на виготовлення одиниці продукції
П1	П2
S1
S2
S3
Оптова ціна одиниці продукції

Необхідно знайти такий план виробництва, який забезпечить найбільший сумарний дохід.

Розв'язування. Побудуємо математичну модель задачі. Нехай х1 та х₂ - загальна кількість відповідно продукції П1 та П₂; Z - сумарний дохід, який отримаємо від реалізації виробленої продукції. Тоді математична модель задачі матиме вигляд:

Z = 9х₁+ 6х₂ (max),

4 x 1 + 5х₂ 275,

13 x1 + 8х₂ 680,

x1 + х₂ 60,

x₁ 0,

х₂ 0.

Приведемо задачу до канонічного виду:

Z = 9х₁+ 6х₂ (max),

4х₁ + 5х₂ +х₃= 275,

13х1 +8х₂ +х₄ =680,

х₁ + х₂ + х₅ = 60,

хi 0, i = .

Розв’яжемо цю задачу симплекс-методом. Заповнимо початкову таблицю:

Таблиця 3.1

 

 

 

 

 

№ таблиці	№ рядка		Опорний план	Коефіцієнти при невідомих
х 1	х 2	х 3	х 4	х 5
		Z		-9	-6
	х 3
	x 4
	х 5

Ітерація 1. В нульовий рядок заносимо інформацію про цільову функцію, а в рядки 1-3 - дані з відповідних рівнянь системи обмежень. Для заповнення нульового рядка початкової симплекс-таблиці цільову функцію запишемо в такому ж вигляді, як обмеження задачі, тобто у вигляді рівняння Z - 9х₁ - 6х₂ = 0 (всі невідомі перенесемо в ліву частину), і в подальшому нульовий рядок будемо заповнювати так само, як і рядки 1-3, що відповідають обмеженням. В стовпчику «Базис» записуємо базисні невідомі з системи обмежень, а для нульового рядка базисною невідомою є Z. В стовпчику «Опорний план» записуємо значення базисних невідомих, коли вільні невідомі х ₁ та х ₂ дорівнюють нулю (праві частини рівнянь-обмежень та цільової функції). В наступних стовпчиках записуємо коефіцієнти при невідомих в цільовій функції та системі обмежень.

Випишемо з першої таблиці початковий опорний план х_опорн.= (0; 0; 275; 680; 60). Знайдемо значення цільової функції за цього плану Z (х_опорн.) = 9·0+6·0=0. Перевіримо, чи даний опорний план є оптимальним. Для визначення ступеня оптимальності опорного плану використовується нульовий рядок. Цільова функція досліджується на максимум, значить для оптимальності опорного плану в нульовому рядку не має бути від’ємних чисел. В задачі в нульовому рядку є два від’ємних числа ((-9) та (-6)), отже досліджуваний опорний план не є оптимальним. Вибираємо найменше з цих чисел (-9). Стовпець, в якому знаходиться це число є ключовим, а невідому x ₁, яка відповідає цьому стовпцю потрібно ввести в базис. Ставимо біля цієї невідомої стрілочку (якщо цільова функція мінімізується і в нульовому рядку є додатні числа, то вибираємо найбільше з цих чисел і за ним визначаємо, яку невідому потрібно ввести в базис). Щоб визначити, яку з невідомих потрібно вивести з базису, складаємо відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця і вибираємо найменше з цих відношень:

275: 4 = 68,75;

680:13 = 52,3; (min)

60:l=60.

Невідому, яка відповідає цьому найменшому відношенню (в нашому випадку х ₄) виводимо з базису. Відмічаємо цю невідому стрілочкою, а рядок, якому відповідає це найменше відношення називається ключовим. На перетині ключового рядка і ключового стовпця знаходиться ключовий (генеральний) елемент, рівний 13.

Ітерація 2. Переходимо до другої симплекс-таблиці. Замість невідомої х ₄ в базис вводимо невідому x ₁. На місці ключового елемента нам потрібно отримати 1, а всі інші елементи в стовпці повинні дорівнювати нулю. Для цього ключовий рядок ділимо на ключовий (генеральний) елемент, тобто на 13, і результат записуємо на місці другого рядка табл. 3.2. Усі інші рядки табл. 3.2 заповнюємо методом Жордана-Гауса, послідовно виключаючи невідому x ₁ з нульового, першого та третього рядків:

1) множимо всі елементи другого рядка на 9 і додаємо відповідні елементи нульового рядка табл. 3.1, результат записуємо на місці нульового рядка табл. 3.2;

2) множимо кожен елемент другого рядка на (–4) і додаємо відповідні елементи першого рядка табл. 3.1, результат записуємо на місці першого рядка табл. 3.2;

3) множимо кожен елемент другого рядка на (–1) і додаємо відповідні елементи третього рядка табл. 3.1, результат записуємо на місці третього рядка табл. 3.2.

Таблиця 3.2

№ таблиці	№ рядка		Опорний план	Коефіцієнти при невідомих
				х 1	х 2	х 3	х 4	х 5
		Z	6120 13		-6		9 13
		х 3	855 13		33 13		-4 13
		х 1	680 13		8 13		1 13
		х 5	100 13		5		-1 13

Із таблиці виписуємо новий опорний план:

Xопорн =.

Значення цільової функції за такого опорного плану

Z(xопорн) = 470.77

Перевіримо цей опорний план на оптимальність. В нульовому рядку є від'ємне число (-6/13), тому такий опорний план не є оптимальним. Невідому, яка відповідає цьому стовпцю (х₂) вводимо в базис. Відмічаємо цю невідому стрілочкою. Складаємо відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця і вибираємо найменше з цих відношень:

(min).

 

Невідому, яка відповідає цьому найменшому відношенню (в прикладі х ₅) виводимо з базису. Відмічаємо цю невідому стрілочкою. Ключовий елемент 5/13.

Ітерація 3. Переходимо до третьої симплекс-таблиці. Замість невідомої х ₅ в базис вводимо невідому х ₂. Ключовий (третій) рядок ділимо на 5/13 і результат записуємо на місці третього рядка табл. 3.3. Знову використаємо метод Жордана-Гауса, послідовно виключаючи невідому х ₂з нульового, першого та другого рядків:

1) множимо всі елементи третього рядка на 6/13 і додаємо відповідні елементи нульового рядка табл. 3.2, результат записуємо на місці нульового рядка табл. 3.3;

2) множимо кожен елемент третього рядка на (-33/13) і додаємо відповідні елементи першого рядка табл. 3.2, результат записуємо на місці першого рядка табл. 3.3;

3) кожен елемент третього рядка множимо на (- 8/13) і додаємо відповідні елементи другого рядка табл. 3.2, результат записуємо на місці другого рядка табл. 3.3.

Таблиця 3.3

 

 

 

 

 

№ таблиці	№ рядка	Базис	Опорний план	Коефіцієнти при невідомих
х 1	х 2	х 3	х 4	х 5
		Z					3	6
	х 3					1	-33
	х 1					1	-8
	х 2					-1	13

В нульовому рядку останньої таблиці немає від’ємних чисел, це означає наявність оптимального розв’язку: х_опт=(40; 20; 15; 0; 0), Z_max = 480.

Отже, максимальний дохід становитиме Z_max =480, якщо продукції П1виготовити 40 одиниць (х1 =40), а продукції П₂ - 20 одиниць (х ₂=20).

Перевірка: Z_max= 9*40 + 6*20 = 360 +120 = 480. Невідомі х ₄=0 та х ₅=0, а це означає, що сировина S₂ та S₃ використана повністю, х ₃=15, значить сировина S₁ є в залишку (недовикористана) 15 одиниць.

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

Лабораторна робота № 6
«Задача оптимального використання ресурсів»

Задача. Для виготовлення двох видів продукції П₁ і П₂ використовують три види сировини І, ІІ і ІІІ. Запаси сировини, норми їх витрат і прибуток від реалізації одиниці продукції задано у таблиці.

Знайти розмір максимального прибутку, який можна одержати за наявності даних запасів сировини.

Варіанти асортименту обрати з таблиці 6.1.

Таблиця 3.4

N°	Затрати ресурсів на одиницю продукції	Наявність ресурсів	Прибуток
І	ІІ	ІІІ
А1	А2	А1	А2	А1	А2	І	ІІ	ІІІ	П1	П2
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.							. 80
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

ТЕМА 4. МОДЕЛІ ОПТИМАЛЬНОГО ПЛАНУВАННЯ НА РІВНІ ПІДПРИЄМСТВА

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

Вирішення оптимізаційної задачі розподіляється на три етапи: побудування економіко-математичної моделі; находження оптимального рішення задачі; аналіз результатів рішення.

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

В задачі оптимізуємо виробничу програму підприємства по критерію максимального прибутку від реалізації продукції; відповідно мова піде про підвищення рентабельності виробництва та зниження собівартості.

Для побудування абстрактної економіко-математичної моделі асортиментної задачі введемо наступні умовні позначення:

j – індекс виду випускаємої продукції;

j = 1, 2,..., n – кількість видів випускаємої продукції;

x_j – шукаємий випуск продукції j-того виду;

і – індекс виду ведучого обладнання;

і = 1, 2,..., m – кількість одиниць ведучого обладнання;

а_ij – зв’язуючий коефіцієнт обмеження по обладнанню, визначаючий норму витрат часу роботи обладнання і -го виду на випуск одиниці продукції
j-го виду;

А_і – потужність обладнання і -го виду за плановий період (рік);

b – собівартість продукції звітного чи планового року;

B_j – питома собівартість j-го виду продукції;

D_j¢, D_j – границя попиту на продукцію j-го виду, відповідно верхній і нижній;

p_j – питомий прибуток від реалізації одиниці продукції j-го виду;

S_j – оптово-відпускна ціна одиниці продукції j-го виду (діюча);

S – вартість порівняльної товарної продукції звітного чи планового року.

Цільова функція має наступний вигляд:

При обмеженнях:

1. По ведучому обладнанню:

2. По випуску товарної продукції:

3. По попиту на окремі види продукції:

4. По собівартості продукції:

5. Умова невід’ємності змінних:

x_j ³ 0, j = 1, 2,..., n.

Лабораторна робота № 7
«Розрахунок оптимальної виробничої програми карамельного цеху»

Задача. У карамельному цеху випускають декілька видів продукції (табл.7.2). Продуктивність ліній визначається по варочному апарату. Кількість варильних апаратів – 1.

Задано: оптова ціна, собівартість продукції і попит, річна продуктивність апаратів по карамелі.

Потрібно:

1. Розрахувати обсяг ресурсів на свій асортимент (табл. 7.3).

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

3. За допомогою отриманих нерівностей чи рівнянь побудувати та записати матрицю коефіцієнтів і функцію цілі.

4. Вирішити задачу за допомогою функції "Поиск решения" табличного процесора Мicrisoft Ехсеl.

5. Заповнити вихідну таблицю та дати економічний аналіз.

Варіанти асортименту обрати з таблиці 7.1.

Таблиця 7.1

	Х1	Х2	Х3	Х4	Х5
Варіант 1
Варіант 2
Варіант 3
Варіант 4
Варіант 5
Варіант 6
Варіант 7
Варіант 8
Варіант 9
Варіант 10

Згідно варіанту завдання обрати продуктивність ліній з таблиці 7.4. Обрати обмеження по попиту з таблиці 7.5.

Таблиця 7.4

	Продуктивність ліній (т/рік)
Непарні варіанти	Парні варіанти:
Варіант 1
Варіант 2
Варіант 3
Варіант 4
Варіант 5
Варіант 6
Варіант 7
Варіант 8
Варіант 9
Варіант 10

Таблиця 7.5

Обмеження по попиту (т/рік)

	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Х8	Х9
max
min

 

Таблиця 7.2