ка і стовпчика
При вирішенні завдань на мінімум оптимальний варіант вийде в тому випадку, коли у всіх завантажених клітинах знаходиться нульовий потенціал, а потенціали НЕ завантажених клітин є позитивними числами. Найбільш потенційної клітиною є така клітина, потенціал якої має найбільший негативний значення. p align="justify"> Найбільша потенційна клітина отримує завантаження, щоб це зробити, необхідно перерозподілити вантаж в таблиці. Це виконується таким чином: кількість завантажених клітин в попередньому кроці має дорівнювати m + n-1, якщо кількість завантажених клітин менш m + n-1, те відсутнє число клітин отримують шляхом завантаження відповідної кількості клітин нулями. Клітка, в якій поставлена ​​загрузка рівна 0, вважається завантаженою. Для найбільш потенційної клітини будується контур. Будується контур так, щоб всі кути крім одного розташовувалися в завантажених клітинах, а один єдиний перебував у вільній найбільш потенційної клітці. При дотриманні цього правила для кожної вільної клітини можна побудувати тільки один єдиний контур. Визначаються позитивні і негативні кути контуру, вважається, що перший позитивний кут лежить у вільній клітці, для якої побудований контур, негативні і позитивні кути чергуються, та їх кількість повинна дорівнювати. p align="justify"> Виявляється найменш завантажена клітина, зайнята негативним кутом у нашому контурі. Кількість вантажу вказане в цій клітці віднімається з усіх клітин з негативними кутами та додається в усі клітини з позитивними кутами. В результаті одна або кілька раніше завантажених клітин стають вільними, а найбільш потенційна клітина стає завантаженою. br/>
Таблиця № 4
ГОГПвивоз, тпотенціал Б 1 Б 2 Б 3 Б 4 Б 5 Б 6 Б 7 А 1 28 4 1316 212 39 37 5100-6 80 20 А 2 46811128711 5 березня 4780 -4 50 30А 3 7145 4112 7 145 10 1612 0-7 0100 20 А 4 5 58792115912470-5 10 40 20ввоз, т608010030402040370потенціал023-40 21
L (x) = 50 * 4 +10 * 5 +80 * 4 +0 * 5 +100 * 4 +30 * 8 +40 * 5 +20 * 5 +20 * 5 +20 * 4 = 1690 т * км
Умова m + n-1 дотримується - 7 +4-1 = 10.
Рішення є оптимальним,...
