Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
ТРАНСПОРТНА ЗАДАЧА. МЕТОД ПОТЕНЦІАЛІВ
Лабораторна робота № 4
з дисципліни
" Методи методи дослідження операцій"
Виконав:
ст. гр. КН-4
Львів –2008
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel
Короткі теоретичні відомості
Постановка
В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1 i m, 1 j n.
Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами.
Розв’язування
Умови Т-задачі записуються у вигляді
ai
С = EMBED Equation.3 EMBED Equation.3
bj b1 b2 b3 … bn
Введемо змінні хij 0, 1 i m, 1 j n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва в пункт споживання j.
Необхідно знайти множину значень змінних хij 0, мінімізуючи функцію
L = EMBED Equation.3 ,
з виконанням умов
EMBED Equation.3
Матрицю
Х = EMBED Equation.3
називають планом перевезень Т-задачі.
Визначення початкового опорного плану.
Метод «північно-західного кута».
Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута.
Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n.
Припустимо, що вже виконано t кроків.
Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай + = t + 2. Знаходимо x = min{ EMBED Equation.3 }, де
EMBED Equation.3 .
Якщо EMBED Equation.3 , то заповнюється -ий рядок матриці, починаючи з (+1)-го елемента, нулями. Якщо EMBED Equation.3 , то заповнюється нулями -й стовбець, починаючи з (+1)-ї строки. При цьому
EMBED Equation.3
EMBED Equation.3
Приклад.
ai
С = EMBED Equation.3 EMBED Equation.3
bj 70 5 45 70
Перевіряємо умову балансу EMBED Equation.3 ; 190 = 190.
Будуємо початковий опорний план Х0:
Х0 = EMBED Equation.3
x11 = min{60,70} = 60;
x21 = min{55,70-60} = 10;
x22 = min{5, 55-10} = 5;
x23 = min{45,55-10-5} = 40;
x33 = min(40, 45-40} = 5;
x34 = min{70,40-5} = 35;
x44 = 35.
Отриманий початковий опорний план Х0 невироджений.
Метод потенціалів.
Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій.
Попередній етап.
Будується початковий опорний план Х0.
Обчислюється оціночна матриця
С1 = EMBED Equation.3 ,
де vj i ui – потенціали i-ого пункту виробництва та пункту споживання j, для яких виконується умова EMBED Equation.3 і хij 0. Для зручності вибирається u1 = 0. Позиція в матриці С1, яка відповідає базисному елементові плану Х0, буде зайнята нулем.
Якщо всі елементи матриці С1 – не від’ємні, то план Х0 – оптимальний. Якщо ні, то виконується наступна ітерація.
k + 1 ітерація.
Якщо в оціночній матриці С(к+1) всі елементи не від’ємні, то план Хк – оптимальний. Якщо ні, виконується наступний крок.
Вибирається найбільший по модулю від’ємний елемент EMBED Equation.3 і, починаючи з відповідного йому елемента EMBED Equation.3 в матриці Хк, будується замкнута послідовність, в яку входять елементи EMBED Equation.3 .Потім визначається - мінімальний елемент серед всіх непарних за порядком розміщення в послідовності, приймаючи першим елементом наступний за EMBED Equation.3 елемент.
Будується новий план Хк+1, додаванням до всіх парних елементів послідовності і відніманням від всіх непарних. Елементи матриці Хк, що не входять в послідовність, переносяться в матрицю Хк+1, без змін.
З матриці Ск будується оціночна матриця Ск+1 для нового плану Хк+1. Для цього підкреслюються в матриці Ск всі елементи, які відповідають ненульовим елементам матриці Хк+1 (вони обов’язково рівні нулю). В матриці Ск закреслюємо строку, яка містить елемент cst. Якщо в цьому рядку є підкреслені елементи, то закреслюються відповідні до цих елементів стовбці. Якщо в кожному закресленому стовбці є підкреслені елементи, то закреслюються відповідні до них рядки, і так до того моменту, доки описана процедура виконувана. Після того до всіх елементів закреслених рядків додається cst, а від елементів закреслених стовбців віднімається величина cst.
Якщо в матриці Ск+1 відсутні від’ємні елементи, то план Хк+1 – оптимальний, інакше перехід до наступної ітерації.
Продовження прикладу.
Для зручності обчислень потенціалів EMBED Equation.3 будується відповідний граф початкового опорного плану перевезень.
A4
A3
A2
A1
u1= 0 u2= -2 u3= -9 u4= -7
1 8 1
B4
B3
B2
B1
3 4 1 3
v1=1 v2=2 v3= -1 v4= -6
Будується оціночна матриця С1 з елементами
EMBED Equation.3 ;
EMBED Equation.3
………………………………………….
C1 = EMBED Equation.3
Оскільки в С1 є від’ємні елементи, то план Х0 - не оптимальний.
1-а ітерація. В матриці Х0, починаючи з елемента х32, відповідного в оціночній матриці до найбільшого від’ємного елемента, будуємо замкнену послідовність. Змінюючи елементи, які входять в послідовність, на величину = min{5,5} = 5,будуємо новий план перевезень Х1:
Х0 = EMBED Equation.3 , Х1 = EMBED Equation.3 .
Отриманий новий план Х1 є виродженим, через що (у випадку, коли необхідно обчислення Х2, Х3, ... і т.д.) один з нулів замкненої послідовності замінюється величиною 0. У випадку виродженості при побудові початкового опорного плану вводиться xij = по тій комунікації, яка необхідна для визначення потенціалів EMBED Equation.3 .
Отже отримуємо:
C1 = EMBED Equation.3 , C2 = EMBED Equation.3 .
В оціночній матриці C2 відсутні від’ємні елементи, отже, план
Х1 = EMBED Equation.3 є оптимальний, не дивлячись на те, що він вироджений.
Вартість перевезень в у.о. L = EMBED Equation.3 = 601 + 102 + 401 + 54 + 353 + 351 = 295.
Порядок роботи:
Заповнити початкову таблицю транспортної задачі лінійного програмування згідно заданого варіанту.
Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям методу потенціалів задачі лінійного програмування.
Знайти мінімальне значення цільової функції та оптимальний розв'язок.
Проінтерпретувати отримані результати для вихідної задачі.
Оформити звіт для захисту лабораторної роботи за зразком
назва роботи
мета роботи
порядок роботи
короткі теоретичні відомості
алгоритм розв'язку задачі
малюнки відповідних таблиць
аналіз отриманих результатів та висновки
Індивідуальне завдання
ai
16. С = EMBED Equation.3 EMBED Equation.3 .
bj 16 18 12 15
Результат виконання роботи в середивищі Excel.