задача є закритою.
Перевірка на вирожденність: N = n + m - 1; N - кількість базисних клітин = 7, n - кількість рядків = 3, m - кількість стовпців = 5; 7 = 3 + 5 - 1 = 7? транспортна задача є невиродженому.
Початкові витрати: Р поч = 500 + 800 + 50 + 650 + 500 + 1350 + 200 = 4050.
Проведемо поетапне поліпшення опорного плану за допомогою методу потенціалів. Додамо до опорного плану додаткові рядок і стовпець (див. малюнок 1). Приймемо значення однієї з вийшов додаткових осередків за 0. Розрахуємо за формулою: В«значення витратиВ» = В«значення у клітинці додаткового рядкаВ» + В«значення комірки додаткового стовпцяВ» інші значення додаткових осередків. Після цього, складемо допоміжну матрицю, значення в якій розраховуються за такою формулою: В«значення в матриціВ» = В«значення витратиВ» - (В«значення у клітинці додаткового рядкаВ» + В«значення комірки додаткового стовпцяВ»). br/>
0 -1 -1 -1
0 0 0 8
-3 -1 0 0
У даній допоміжної матриці присутні негативні числа. Так як кожне число в матриці показує на скільки зміняться загальні транспортні витрати при завантаженні даної клітини одиницею вантажу, то даний план можна поліпшити перемістивши у відповідну клітку деяку кількість продукції (якщо число негативне, витрати зменшуються). З усіх негативних значень вибираємо найбільше за модулем, так як її вплив на загальні витрати є максимальним. Зазначимо знаком В«+В» в транспортній таблиці клітинку відповідну положенню максимального за модулем від'ємного числа в допоміжної матриці. Крім неї ми пометим знаками В«-В» і В«+В» інші зайняті числами осередку таким чином, що в кожному рядку і кожному стовпці транспортної таблиці число знаків В«+В» буде дорівнює числу знаків В«-В». Це завжди можна зробити єдиним чином, причому в кожному рядку і кожному стовпці міститься по одному В«+В» і В«-В». Тобто помічені знаками клітини повинні утворювати цикл (див. малюнок 1). Потім ми визначимо мінімум з усіх елементів, помічених знаком В«-В», і виберемо одну клітинку, де цей мінімум досягається. У нашому випадку такою є осередок, що містить 25 одиниць вантажу. Отже, дана осередок при перерахунку повинна стати вільною. br/>
МП/СП1001253252501002005 1008 100 -7103 +5450422 3255 1256-425073 25 +59 1252 100 -003692
Р 1 = 500 + 800 + 75 + 650 + 625 + 1125 + 200 = 3975. 4
мінімальна кількість вантажу в клітинці: 100
0 0 -4 -4 -
8 березня 0 0 8
0 -1 0 0
МП/СП1001253252501002005 1008 7103 1005450422 325 -5 125 +6025073 125 5 +9 125 -2 0 40-125-2
Р
