Методичні вказівки до виконання курсового проекту 4 страница

Таблиця42

Четверта ітерація ТТ

	B1	B2	B3	B4	Запаси ai		ai'
A1	4	7	–	–		7-4= 3
A2	3	6 –		–		6-3= 3	10-10=0 К
A3	–		–			К
Заявки bj
	4-3=1	7-6=1	К	К
bj'	80-10=70

 

Оскільки у таблиці 43 перший і другий стовпці містять по одному елементу, то різниця у цьому випадку знаходиться між ними, тобто дорівнює 0. У першої єдиної строчці знаходимо мінімальний елемент – це 4 у клітинці А₁В₁. Тому поміщаємо у цю клітинку максимально можливий обсяг вантажу – 70, при цьому виключаємо з подальшого розгляду перший стовпець, поставивши нижче різниці – букву К (кінець), тому що повністю задоволена уся заявка вантажу першого споживача.

У таблиці 44 заповнюється остання вільна клітинка ТТ, а саме А₁В₂ обсягом вантажу рівним 30 одиницям.

Таблиця43

П’ята ітерація ТТ

	B1	B2	B3	B4	Запаси ai		ai'
A1	4	7	–	–		7-4= 3	100-70=30
A2		–		–		К
A3	–		–			К
Заявки bj
	4-4=0 К	7-7=0	К	К
bj'	70-70=0

 

Таблиця44

Шоста ітерація ТТ

	B1	B2	B3	B4	Запаси ai		ai'
A1			–	–		7-7=0 К	30-30=0
A2		–		–		К
A3	–		–			К
Заявки bj
	К	7-7=0 К	К	К
bj'		30-30=0

 

В результаті одержано (m + n - 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

 

4. МЕТОДИ ЗНАХОДЖЕННЯ ОПТІМАЛЬНИХ ПЛАНІВ

ПЕРЕВЕЗЕНЬ ВАНТАЖУ

4.1. Симплексний метод оптимізації транспортних перевезень

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

Оскільки ТЗ є окремим випадком загальної задачі ЛП (ЗЗЛП), то до неї також цілком можливо застосувати всі стандартні методи її розв’язання (зокрема найвідоміший з них – симплексний метод), попередньо привівши ТЗ до вигляду задачі ЛП і врахувавши її специфічність. Для цього необхідно провести над математичною моделлю ТЗ ряд перетворень. Ці перетворення будемо здійснювати на конкретному прикладі ТЗ, а саме для m постачальників (m =3) і n споживачів продукції (n =4) (див. табл. 1).

а) спочатку запишемо вихідну систему рівнянь ТЗ у такому вигляді:

|| || || ||

b₁ b₂ b₃ b₄

 

де: x_ij –кількість продукції, відправленої від і-го постачальника до j-го споживача;

а_i – обсяг продукції наявної у і-го постачальника (i =1, 2, 3);

b_j –обсяг продукції необхідної j-ому споживачу (j =1, 2, 3, 4).

б) подамо її у вигляді системи (т + n)лінійних рівнянь таким чином:

в) замінимо x₁₁ на x₁, x₁₂ на x₂, x₁₃ на x₃,..., x₃₄ на x₁₂. Маємо:

г) додамо, як того вимагає симплексний метод, до всіх рівнянь додаткові перемінні, які становитимуть початковий базисний розв’язок ТЗ:

У результаті цих перетворень ми утворили систему (т + п)лінійних рівнянь з (m ´ п + т+ n)позитивними перемінними, розв’язати яку можна за допомогою симплекс-методу. Оскільки сума рівнянь системи в рядках дорівнює сумі рівнянь системи в стовпцях, то ми одержали лінійно-залежну систему рівнянь. Щоб привести її до нормального (лінійно-незалежного) виду, одне з рівнянь системи (переважно останнє) можна без шкоди для кінцевого результату розв’язку ТЗ відкинути. Тоді ми матимемо (т + п – 1)лінійних рівнянь і (m ´ п + т+ n - 1) перемінних.

Необхідно також відзначити те, що у класичній ТЗ перевезти продукцію від усіх постачальників (а_i)потрібно так, щоб усі замовлення були виконані (b_j),а загальна вартість (L) транспортних перевезень була б мінімальною, тобто:

,

де: с₁ , с₂,... с_k –вартість перевезення одиниці продукції від кожного постачальника до кожного споживача (k = 1,т´ п).

Розглянемо розв'язання ТЗ на конкретному прикладі, умови якого дані у вигляді ТТ (табл. 45), де т = 3, n = 4. Відповідно, кількість рівнянь становитиме (m + n – 1) = 6, кількість вихідних перемінних – (m × n) = 12 і кількість додаткових перемінних – (т + п – 1) = 6.

Таблиця 45

Дані ТЗ у вигляді ТТ

	B1	B2	B3	B4	Запаси ai
A1	c1 = 4 x1	c2 = 7 x2	c3 = 2 x3	c4 = 5 x4
A2	c5 = 3 x5	c6 = 6 x6	c7 = 1 x7	c8 = 8 x8
A3	c9 = 9 x9	c10 = 3 x10	c11 = 6 x11	c12 = 2 x12
Заявки bj

 

Запишемо умову нашої ТЗ у термінах ЗЗЛП.

Необхідно мінімізувати цільову функцію L = 4 × x₁ + 7 × x₂ + 2 × x₃ + 5 × x₄ + 3 × x₅ + 6 × x₆ +1 ×x₇+ 8 × x₈ + 9 × x₉ + 3 × x₁₀ + 6 × x₁₁ +2 ×x₁₂,

за таких обмежень:

тобто кількість рівнянь становить 6, а кількість вихідних перемінних дорівнює 12.

Вводимо до обмежень нові змінні x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈. Значення відповідних коефіцієнтів впливу вибираємо набагато більші ніж існують. У нашому випадку приймемо за цю величину суму всіх коефіцієнтів при невідомих у початковій цільовій функції, тобто 56. Завдяки цьому перемінні x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈ з базисних поступово будуть переведені у вільні, що забезпечує тим самим мінімум цільової функції. Після введення нових перемінних маємо:

L = 4 × x₁ + 7 × x₂ + 2 × x₃ + 5 × x₄ + 3 × x₅ + 6 × x₆ +1 ×x₇+ 8 × x₈ + 9 × x₉ + 3 × x₁₀ + 6 × x₁₁ +2 ×x₁₂+ 56 × x₁₃ + 56 × x₁₄ + 56 × x₁₅ + 56 × x₁₆ +56 ×x₁₇+ 56 × x₁₈, → min,

за обмежень

Остаточна кількість рівнянь k = 6; кількість перемінних l = 18.

За базисні обираємо x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈ і отримуємо перше базисне рішення X = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100, 120, 140, 80, 100, 110}, що забезпечує L = 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 + 56 × 100 +56 × 110 = 36400 у.г.о.

Складемо першу симплекс-таблицю (СТ) – табл. 46. У першому рядку цієї таблиці знаходяться значення коефіцієнтів c_j при невідомих цільової функції; у першій графі СТ розташовані значення коефіцієнтів c_бі при базових невідомих цільової функції; друга графа містить самі базові невідомі х_бі; третя – значення базових невідомих b_бi (у першій СТ це значення правих частин останньої системи рівнянь) і частина СТ, що залишилася, крім останнього рядка, зайнята коефіцієнтами a_ij при невідомих також останньої системи рівнянь.

Останній рядок (індексний ряд) служить для розрахунків індексів ∆_j, що є характеристиками оптимальності отриманого плану. Індекси розраховуються за допомогою наступних формул:

Таблиця 46

Перша СТ

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

х13

х14

х15

х16

х17

х18

∆0 = 36400

∆1=

∆2=105

∆3=110

∆4=51

∆5=109

∆6=106

∆7=111

∆8=48

∆9=103

∆10=109

∆11=

∆12=54

∆13=0

∆14=0

∆15=0

∆16=0

∆17=0

∆18=0

Вважається, що отримане рішення х_бі є оптимальним, якщо .

Порахуємо значення індексів для першої СТ:

∆₀ = 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 +56 × 100 + 56 × 110 = 36400 у.г.о.

∆₁ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 4 = 108

∆₂ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 7 = 105

∆₃ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 2 = 110

∆₄ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 5 = 51

∆₅ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 3 = 109

∆₆ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 6 = 106

∆₇ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 1 = 111

∆₈ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 8= 48

∆₉ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 1 +56 × 0 + 56 × 0 – 9 = 103

∆₁₀ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 1 + 56 × 0 – 3 = 109

∆₁₁ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 1 – 6 = 106

∆₁₂ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 2 = 54

∆₁₃ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₄ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₅ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₆ = 56 × 0 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 56 = 0

∆₁₇ = 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 56 = 0

∆₁₈ = 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 56 = 0

Очевидно, що базове рішення не є оптимальним, тому що усі індекси від ∆₁ до ∆₁₈ позитивні, тому продовжимо поліпшення (оптимізацію) базового плану далі.

У якості ключового стовпця, який містить внесену в базу вільну змінну, вибираємо стовпець х₇, що має максимальне позитивне значення ∆₇ = 111. Для визначення ключового рядка рахуємо відповідні відношення значень базових невідомих b_бi на не нульові значення елементів обраного ключового стовпця, а саме:

; і вибираємо з них мінімальне, тобто друге.

Тоді ключовим рядком буде шостий і він містить базову змінну х₁₈ , що виводиться з базису. Тобто змінна ключового шостого рядка базису х₁₈ має бути замінена на вільну змінну ключового стовпця х₇, при цьому ключове число a₆₇ = 1 (це число відмічено у СТ більшим розміром). Складаємо нову СТ (див. табл. 47).

Спочатку введемо в базис замість змінної х₁₈ змінну х₇ зі значенням її коефіцієнта c₇ = 1 і розділимо всі елементи цього рядка на ключове число a₆₇ = 1. Після цього перерахуємо значення частини елементів таблиці, що залишилася, таким способом:

,

де: НЕ і СЕ – відповідно будь-який новий елемент (a_ij^н або b_i^н) з не ключового рядка і той же старий елемент (a_ij або b_i) СТ, що перетворюється;

ЕК_р і ЕК_ст – відповідно елементи ключового рядка і ключового стовпчику СТ, що перетворюється;

К – ключовий елемент СТ, що перетворюється (у нашому випадку для першої СТ це a₆₇).

Порахуємо як приклад по цій формулі нові значення b₂, a₂₃ і a₂₇:

.

Інші елементи перенесемо в нову СТ без демонстрації аналогічних детальних розрахунків.

Як видно з таблиці 47 нове значення цільової функції дорівнює 24190 у.г.о., що значно менше попереднього її значення і, що, у свою чергу, свідчить про нормальний плин процесу оптимізації. Індексний рядок нової СТ містить позитивні елементи – це означає, що отримане значення не є оптимальним і план перевезень вимагає поліпшення. Відзначимо в СТ ключовий елемент a₂₅ і опускаючи всі розрахунки перейдемо до наступної СТ (див. табл. 48).

Таблиця 47

Друга СТ

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

х13

х14

-1

-1

-1

х15

х16

х17

х7

∆0 = 24190

∆1=

∆2=105

∆3= -1

∆4=51

∆5=109

∆6=106

∆7=0

∆8=48

∆9=103

∆10=109

∆11= -5

∆12=54

∆13=0

∆14=0

∆15=0

∆16=0

∆17=0

∆18= -111

 

Із цієї СТ також видно, що процес оптимізації триває (нове значення цільової функції дорівнює 23100), але в індексному рядку ще присутні позитивні елементи – це означає, що план перевезень вимагає подальшого поліпшення. Відзначимо також у СТ ключовий елемент a_5,10 і перейдемо до наступної СТ (див. табл. 49).

Таблиця 48

Третя СТ

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

х13

х5

-1

-1

-1

х15

х16

-1

-1

-1

х17

х7

∆0 = 23100

∆1=

∆2=105

∆3=

∆4=51

∆5=0

∆6= -3

∆7=0

∆8= -61

∆9=103

∆10=109

∆11=

∆12=54

∆13=0

∆14= -109

∆15=0

∆16=0

∆17=0

∆18= -2

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом – a₄₁ (див. табл. 50).