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

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

Якщо цільова функція вимагає знаходження максимуму, то якщо її помножити на “-1” функція змінються на знаходження мінімуму. В системі обмежень для перехіду від знаку “” до знаку “=” треба додати додаткову зміну, а від знаку “” до знаку “=” додати додаткову зміну з відємним значенням.

Приклад 1. Економіко-математична модель задачі лінійного програмування, яку треба привести до канонічного виду має вигляд

F = 10x₁ + 12 x₂  max

при обмеженнях

4x₁ + 5x₂  300

2x₁ + x₂  100

2x₁ + 3x₂  160

x₁  0; x₂  0

Для приведення цільової функції до канонічного виду виконуємо множення її на “-1”. В кожному обмеженні для зміни знака “” на знак “=” додаємо додаткову змінну. Ця змінна компенсує різницю між математичною формулою ліворуч та встановленою величиною праворуч. Таким чином задача у канонічному виді

F = - 10x₁ - 12 x₂  min

при обмеженнях

4x₁ + 5x₂ + x₃ = 300

2x₁ + x₂ + x₄ = 100

2x₁ + 3x₂ + x₅ = 160

x₁  0; x₂  0; x₃  0; x₄  0; x₅  0

Приклад 2. Економіко-математична модель задачі лінійного програмування, яку треба привести до канонічного виду має вигляд

F(x) = х₁ - х₂ - 3х₃  min

при обмеженнях

2х₁ - х₂ - 3х₃  1

4х₁ - 2х₂ + х₃  -2 ,

2x₁ + x₃  5

x_j  0 ( j = 1, 2, 3)

В цьому прикладі цільова функція вже встановлює пошук найменшого значення. Тому вона не змінюється. В кожному обмеженні для зміни знака “” на знак “=” додаємо додаткову змінну, а для зміни знака “” на знак “=” додаємо додаткову змінну з відємним значенням. Ця змінна компенсує різницю між математичною формулою ліворуч та встановленою величиною праворуч. Таким чином задача у канонічному виді

F(x) = х₁ - х₂ - 3х₃  min

при обмеженнях

2х₁ - х₂ - 3х₃ + х₄ = 1

4х₁ - 2х₂ + х₃ - х₅ = -2 ,

2x₁ + x₃ + х₆ = 5

x_j  0 ( j = 1, 2, ..., 6)

1.5 Симплексний метод рішення задач лінійного програмування

Існує багато методів які дозволяють знайти оптимальне рішення в задачах лінійного програмування (ЗЛП). Одним з таких методів, який дозволяє ефективно вирішувати такі задачі є симплекс метод. Ідея цього методу складається з переходів від одного розв’язку x_k до другого x_k+1 , для яких виконується умова f(x_k) > f(x_k+1). Для переходу від одного розв’язку до другого використовуються симлексні таблиці. Кожній симплексній таблиці відповідає один з розв’язків задачі. По змісту симплексної таблиці можна визначити, чі оптимальне рішення знайдено, або що задача рішень не має.

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

Крок 1. Здійснюється перевірка економіко-математичної моделі на відповідність канонічному виду. Якщо модель не відповідає вимогам, то виконується приведення моделі до канонічного виду.

Крок 2. Для таблиці обмежень будується матриця коефіцієнтів та визначається базіс. Якщо треба, то послідовно у кожній строці визначається базисна змінна і за методом Гауса проводяться необхідні перетворення. Кожна базисна зміна має бути присутньою тільки в одній строці обмежень. Нехай X_k , X_k+1, …, X_k+j - є базіс, тогда X_k= B_{1 ,} X_k+1= B_{2 , …,} X_k+j= B_m – є базисний розв’язок. Подальша задача полягає в тому, щоб від початкового допустимого базисного розв’язку перейти до іншого базисного розв’язку, при якому значення лінійної форми зменшиться. Лінійна форма при початковому базисному розв’язку дорівнюєнулю. Для поліпшення результатів розв’язку на кожному кроці треба перевести одну змінну з неосновних в основні і одну змінну з основних в неосновні, тобто дві змінні міняються місцями.

Крок 3. Будуємо симлекс таблицю для лінійної моделінаступного виду:

Таблиця 1.5.1

e	X1	X2	…	Xn	B
Xk	a11	a12	…	a1n	B1
Xk+1	a21	a22	…	a2n	B2
…	…	…	…	…	…
Xk+j	am1	am2	…	amn	Bm
F (x)	C1	C2	…	Cn	C0

В таблиці k, k+1, k+j < n, (X_k , X_k+1, …, X_k+j ) – початковий базіс рішення.

Крок 4. Серед коефіцієтів C_i (i = 1,n)обираємо C_i < 0 той , що має найменше значення (найбільше за абсолютним значенням). Стовпець з обраним C_i визначає змінну, яку треба перенести до базису. Щоб обрати змінну, яку треба виключити з бази розраховуємо оценку, яка визнається як B_i /a_ij . Виключати треба змінну, яка буде мати найменшу оцінку.

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

Крок 6. За результатми проведених змін оновлюємо симплекс таблицю. Якщо серед коефіцієтів C_i (i = 1,n) є C_i < 0 , то переходимо до кроку 4. Якщо всі C_i  0, то знайдено оптимальне рішення.

Приклад 1. В прикладі 1 розділа 1.1 на підставі умов завдання побудована економіко-математична модель для пошуку рішення. Ця модель вимагає знайти максимальне значення цільової функції

F = 10x₁ + 12 x₂  max

при обмеженнях на ресурси виробництвапо металу, склу та трудовим ресурсам відповідно до технологічних норм,

4x₁ + 5x₂  300

2x₁ + x₂  100

2x₁ + 3x₂  160

x₁  0; x₂  0

Приводимо модель до канонічного виду

F = - 10x₁ - 12 x₂  min

при обмеженнях

4x₁ + 5x₂ + x₃ = 300

2x₁ + x₂ + x₄ = 100

2x₁ + 3x₂ + x₅ = 160

x₁  0; x₂  0; x₃  0; x₄  0; x₅  0

Будуємо сімплекс таблицю і визначаємо базіс. Так як додаткові змінні x₃, x₄, x₅ мають кофецієнт одиницю та присутні тільке один раз в кожній строці обмежень, то ці змінні можуть створювати базіс.

Таблиця 1.5.2

e	X1	X2	X3	X4	X5	B
X3	4	5	1	0	0	300
X4	2	1	0	1	0	100
X5	2	3	0	0	1	160
F (x)	-10	-12	0	0	0	0

Аналізуємо остнню строку таблиці та визначаємо стовпець зі змінною, яку треба перенести до базису. В нашому випадку найменше значення “-12”, що відповідає знмінній x₂.

Визначаємо змінну, яку треба вивести з базісу. Для цього вільні значення (стовпець В) ділимо на коефіцієнти у відповідних строках стовпця x₂. За підсумками маємо значення

300 / 5 ; 100 / 1 ; 160 / 3 або 60; 100; 53,33333

Найменше значення знаходиться в строці зі змінною x₅. Таким чином треба провести перетворення моделі за методом Гауса і перенести в базіс x₂ замість x₅. Обмеження, у якому визначено x₂ і x₅ поділимо на 3 і отримуємо (2/3)x₁ + x₂ + (1/3)x₅ = 160/3. Вирішуємо рівняння відносно x₂

x₂ = 160/3 - (2/3)x₁ - (1/3)x₅

Отримане значення x₂ підставляємо в інші обмеження і цільову функцію.

4x₁ + 5(160/3 - (2/3)x₁ - (1/3)x₅) + x₃ = 300 або (2/3)x₁+ x₃ - (5/3)x₅ = 100/3,

2x₁ + 160/3 - (2/3)x₁ - (1/3)x₅ + x₄ = 100 або (4/3)x₁+ x₄ - (1/3)x₅ = 140/3.

Підставляємо значення x₂ в цільову функцію

F = - 10x₁ - 12 (160/3 - (2/3)x₁ - (1/3)x₅) або - 2x₁ + 4x₅ – 640  min,

і отримуємо нову систему цільової функції і обмежень

F = - 2x₁ + 4x₅ – 640  min,

при обмеженнях

(2/3)x₁+ x₃ - (5/3)x₅ = 100/3

(4/3)x₁+ x₄ - (1/3)x₅ = 140/3

(2/3)x₁ + x₂ + (1/3)x₅ = 160/3

Будуємо нову сімлекс таблицю:

Таблиця 1.5.3

e	X1	X2	X3	X4	X5	B
X3	2/3	0	1	0	-5/3	100/3
X4	4/3	0	0	1	-1/3	140/3
X2	2/3	1	0	0	1/3	160/3
F (x)	-2	0	0	0	4	640

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

Визначаємо змінну, яку треба вивести з базісу. Для цього вільні значення (стовпець В) ділимо на коефіцієнти у відповідних строках стовпця x₁. За підсумками маємо значення

(100/3):(2/3) = 50 ; (140/3):(4/3) = 35 ; (160/3):(2/3) = 80

На цьому кроці найменше значення знаходиться в строці зі змінною x₄. Таким чином треба провести перетворення моделі за методом Гауса і перенести в базіс x₁ замість x₄. Обмеження, у якому визначено x₁ і x₄ поділимо на 4/3 і отримуємо x₁ + (3/4)x₄ - (1/4)x₅ = 35. Вирішуємо рівняння відносно x₁

x₁ = 35 - (3/4)x₄ + (1/4)x₅

Отримане значення x₁ підставляємо в інші обмеження і цільову функцію.

2/3(35 - (3/4)x₄ + (1/4)x₅) + x₃ + (5/3)x₅ = 100/3 або x₃ - (1/2)x₄ - (3/2)x₅ = 10,

2/3(35 - (3/4)x₄ + (1/4)x₅) + x₂ + (1/3)x₅ = 160/3 або x₂ - (1/2)x₄ + (1/2)x₅ = 30,

Підставляємо значення x₂ в цільову функцію

F = - 2(35 - (3/4)x₄ + (1/4)x₅) + 4x₅ – 640  min, або 1,5 x₄ + 3,5x₅ – 710  min,

і отримуємо нову систему цільової функції і обмежень

F = 1,5x₄ + 3,5x₅ – 710  min,

при обмеженнях

x₃ - (1/2)x₄ - (3/2)x₅ = 10

x₁ + (3/4)x₄ - (1/4)x₅ = 35

x₂ - (1/2)x₄ + (1/2)x₅ = 30,

Будуємо нову сімлекс таблицю:

Таблиця 1.5.4

e	X1	X2	X3	X4	X5	B
X3	0	0	1	-1/2	-3/2	10
X1	1	0	0	3/4	-1/4	35
X2	0	1	0	-1/2	1/2	30
F (x)	0	0	0	1,5	3,5	710

В нової таблиці немає відємних значень в останій строці. Тому ми маємо оптимальне розв’язування задачі. Змінні x₄ , x₅ , які не входять до бази, дорівнюємо нулю і отримуваємо результат: (x₁ = 35; x₂ = 30; x₃ = 10; x₄ = 0; x₅ = 0;) , максимальне значення функції дорівнює 710. Подставляємо значення x₁ = 35 і x₂ = 30 до цільової функції і отримуваємо:

F = 10x₁ + 12 x₂ = 10*35 + 12*30 = 350 + 360 = 710

Це визначає, що рішення вірно.

Приклад 2. На двох складах зберегається 12т. та 15т. товару який треба перевезти до трьох крамниць (до 1-й крамниці – 8т., до 2-й крамниці – 10т., до 3-й крамниці – 9 т.). Необхідно скласти оптимальний план перевезень якщо вартість перевезення в у.о. 1т. товару зі складів до крамниць наведено в таблиці:

Таблиця 1.5.5

Крамниці Склади	Крамниця 1 8	Крамниця 2 10	Крамниця 3 9
Склад1 12	30	46	32
Склад2 15	20	53	40

Ця задача наведена в прикладі 2 розділа 1.2 на підставі умов завдання побудована економіко-математична модель для пошуку рішення. Ця модель вимагає знайти минимальне значення цільової функції:

F(x) = 30 x₁ + 46 x₂ +32 x₃ + 20 x₄ + 53 x₅ + 40 x₆  min

З обмеженнями

x₁ + x₂ + x₃ = 12

x₄ + x₅ + x₆ = 15

x₁ + x₄ = 8

x₂ + x₅ = 10

x₃ + x₆ = 9

x_i  0 i = 1,2,…,6

У даному випадку задача лінійного програмування вже має канонічний вид. Треба будувати симлекс таблицю, але спочатку необхідно визначити базіс. За методом Гауса виконуємо наступні перетворення, щоб визначити базові змінні. З першого рівняння x₁ = 12 - x₃ - x_{2 .} Підставляємо значення x₁ до третього рівняння, та виводимо x₁ до бази. З четвертого рівняння x₂ = 10 - x_{5 .} Підставляємо значення x₂ до першого і третього рівняння, та виводимо x₂ до бази. З п’ятого рівняння x₃ = 9 - x_{6 .} Підставляємо значення x₃ до першого і третього рівняння, та виводимо x₃ до бази. Після ціх перетворень маємо наступні обмеження

x₁ - x₅ - x₆ = -7

x₄ + x₅ + x₆ = 15

x₄ + x₅ + x₆ = 15

x₂ + x₅ = 10

x₃ + x₆ = 9

x_i  0 i = 1,2,…,6

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

Таблиця 1.5.6

e	X1	X2	X3	X4	X5	X6	B
X 1	1	0	0	0	-1	-1	-7
X 4	0	0	0	1	1	1	15
X2	0	1	0	0	1	0	10
X 3	0	0	1	0	0	1	9
F (x)	30	46	32	20	53	40	0

В таблиці немає в останій строці коефіцієнтів, які мають відємне значення, тому подальша оптимізація за допомогою симплекс перетворень не можлива. Для пошуку остаточного рішення треба змінні, які не є базовими дорівняти 0. Якщо за першим рівнянням одночасно x₅ та x₆ дорівняти 0, то x₁ буде мати відємне значення, а це суперечить умовам. Для подальшого пошуку рішення треба застосовувати інши логічно математичні перетворення, за результатами яких остаточне рішення (0;3; 9; 8; 7; 0), а значення цільової функції F(x) = 30*0 + 46*3 +32*9 + 20*8 + 53*7 + 40*0 = 957.

Остаточне рішення має вигляд: Таблиця 1.5.7

Крамниці Склади	Крамниця1 (потрібно 8т)	Крамниця2 (потрібно10т)	Крамниця3 (потрібно 9т)
Склад1 (усього 12т)	Х1=0	Х2=3	Х3=9
Склад2 (усього 15т)	Х4=8	Х5=7	Х6=0

У даному прикладі наведено рішення транспортної задачі симплекс методом. Використання цього методу для вирішення транспортних задач не є ефективним. Для розв’язування транспортних задач більш ефективними є спеціальні методи, які будуть наведени при розгляді транспортних задач.