Методи побудови опорного плану тз

Як і в звичайному симплексному методі, розв'язування транс­портної задачі полягає в цілеспрямованому переборі та перевірці на оптимальність опорних планів. Початком такого ітераційного процесу є побудова першого опорного плану.

Перший опорний план транспортної задачі, як і будь-якої за­дачі лінійного програмування можна побудувати методом, який було розглянуто в розділі 2, що призведе до необхідності надто складних розрахунків. Завдяки вищезгаданим особливостям бу­дови математичної моделі транспортної задачі існують кілька простих методів побудови опорного плану. Розглянемо методи північно-західного кута, мінімальної вартості та метод подвійної відмітки. Побудову опорного плану зручно подавати у вигляді таблиці, в якій постачальники продукції від­повідають рядкам, а споживачі — стовпчикам.

Детальніше розглянемо методи побудови опорного плану задачі.

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

Побудова опорного плану діагональним методом починається із заповнення верхньої лівої клітини (північно-західного кута, звідси і назва методу діагональний або метод північно-західного кута)

x₁₁=min {a₁; b₁}, якщо x₁₁=a_1, то перший виробник повністю вивіз свою продукцію, і наступною обчислюється величина

x₂₁=min {a₂; b₁- a₁}.

Якщо ж x₁₁ = b₁, то всі x_і1 = 0 і наступною обчислюється величина x₁₂=min {a₁ - b₁; b₂}.

Розглянемо цей процес на нашому прикладі.

Спочатку, не враховуючи вартості перевезень, завжди задово­льняють потреби першого споживача В₁ використовуючи запаси першого постачальника А₁. У нашому прикладі потре­би споживача В₁ становлять 80, а запаси постачальника A₁ 100 одиниць (тобто із запасів першого постачальника можна повністю задовольнити потреби першого споживача), тому в клі­тинку (1,1) записуємо менше із значень a₁ i b₁, тобто 80. Тепер потреби першого споживача повністю задоволені, і переходимо до задоволення потреб наступного (другого) споживача В₂. Обсяг його потреб В₂ - 140. Після задоволення потреб першого спожива­ча залишок запасів першого постачальника становить 100-80 = 20. Отже, від першого виробника другому споживачеві можна перевезти лише 20 одиниць продукції, тому в клітину (1,2) записуємо число 20. Після цього, оскільки запаси першого поста­чальника повністю вичерпані, переходимо до використання запа­сів наступного постачальника A₂. Його запаси а₂ - 200, а незадоволені потреби другого споживача 140-20= 120, тому в клітинку (2,2) записуємо число 120, і другий споживач у такий спосіб також повністю отримав необхідну кількість продукції. Переходимо до задоволення потреб наступного споживача В₃ і т.д. Розрахунки проводяться до моменту виконання умов:

(2)

(3)

					ai
	2 80	5 20	4	6	a1=100
	8	4 – 120	3 + 80	8	a2=200
	5	1 +	4 – 20	5 80	a3=100
bj	b1=80	b2=140	b3=100	b4=80	400 400

Ідея методу мінімальної вартості полягає в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції. Суть методу мінімальної вартості полягає в тому, що спочатку заповнюються ті клітини таблиці, в яких вартості перевезень дорівнюють найменшому елементу матриці С//с_ij//. Потім заповнюються клітини, які мають найменшу вартість перевезення, що залишилися незаповненими після першого кроку і знову вибираємо найменшу вартість для клітин таблиці, що залишилися пустими, і продовжуємо процес доти, поки всі запаси не будуть розподілені, а потреби — задоволені , тобто аж до виконання умов (2)–(3).

Складемо за допомогою цього методу план розглядуваної задачі .

					ai
	2 80	5	4	6 20	a1=100
	8	4 40	3 100	8 60	a2=200
	5	1 100	4	5	a3=100
bj	b1=80	b2=140	b3=100	b4=80	400 400

Метод подвійних відміток. Якщо розмірність задачі досить велика, то перебір за методом мінімальної вартості ускладнюєть­ся. В такому разі спростити пошук клітин з найменшими вартос­тями можна, застосовуючи метод подвійної відмітки (переваги).

Метод подвійних відміток працює за таким правилом: проглядають рядки і позначають певними відмітками клітини, що характеризуються найменшими транспортними витратами, потім, аналогічно по колонках. У результаті таких дій отримаємо таблицю, позначену певним чином: деякі клітини –подвійною відміткою, інші –одинарною, деякі – непомічені. Таблицю починають заповнювати з клітинок, позначених двічі (які містять вартості, що є мінімальними і в рядку, і в стовпчику). Далі заповнюють клітинки, позначені один раз (що містять міні­мальні вартості або в рядку, або в стовпчику), а вже потім — за методом мінімальної вартості.

При знаходженні опорного плану необхідно максимально заповнити клітини з подвійною відміткою, потім – з одинарною, і, якщо необхідно – непомічені аж до виконання умов (2)–(3).

Третій крок розв’язку транспортної задачі – перевірка опорного плану на виродженість.

План транспортної задачі є невиродженим, якщо кількість відмінних від нуля елементів матриці плану (базисних клітин) дорівнює k=m+n –1 ,

де m – кількість рядків (пунктів виробництва), а n – кількість колонок (пунктів споживання).

Для нашої задачі – k=3+4-1=6

План теж містить 6 заповнених клітин, тому він є невиродженим. У випадку невиродженості плану до сукупності базисних (ненульових) клітин таблиці додається небазисна (нульова) клітина, але так, щоб вона не утворювала циклу зі сукупністю базисних клітин таблиці.

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