Схема алгоритма метода sumTransport

4.4 Схема алгоритма метода CiclePr

4.5 Схемы алгоритма метода searchCycle

4.6 Схемы алгоритма метода firstPlan

5 РУЧНОЙ ПРОСЧЕТ

Даны сходные данные:

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

Таблица 5.1 – Опорный план

Стоимость плана

14*2+18*4+4*7+1*10+12*1+33*6+26*1+10*2+32*1=426

Для каждой свободной клетки построим цикл и определим его стоимость

Y21 = 15 >0 Y53 = 10 >0

Y31 = 4 >0 Y34 = -2 <0

Y51 = 10 >0 Y44 = -4 <0

Y22 = 8 >0 Y15 = -1 <0

Y52 = 12 >0 Y25 = 2 >0

Y23 = 12 >0 Y43 = 1 >0

Y32 = 1 >0 Y45 = -1 <0

Построим цикл для {1;5}

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	+	⁸
A2		⁸		³		¹⁰	¹		²
A3		⁵		⁴		⁶	⁷		⁹
A4		¹		¹⁰		⁷	⁵		³
A5		⁴		⁸		⁹	²		¹
bi

Стоимость плана = 426-1=425

Построим цикл для {1;5}

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷		¹⁰	⁸
A2		⁸		³		¹⁰		¹	²
A3		⁵		⁴		⁶	+	⁷	⁹
A4		¹		¹⁰		⁷		⁵	³
A5		⁴		⁸		⁹		²	¹
bi

Стоимость плана = 425- 1=424

Построим цикл для {1;5}

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷		¹⁰	⁸
A2		⁸		³		¹⁰		¹	²
A3		⁵		⁴		⁶		⁷	⁹
A4		¹		¹⁰		⁷	+	⁵	³
A5		⁴		⁸		⁹		²	¹
bi

Стоимость плана = 424-1=423

Построим цикл для {4;5}

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰		⁸
A2		⁸		³		¹⁰	¹		²
A3		⁵		⁴		⁶	⁷		⁹
A4		¹		¹⁰		⁷	⁵	+	³
A5		⁴		⁸		⁹	²		¹
bi

Стоимость плана = 424-1=422

	B1	B2	B3	B4	B5	ai
A1		²		⁴		⁷	¹⁰	⁸
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		⁴		⁸		⁹	²	¹
bi

T.к. для всех клеток цены циклов положительны, то дальнейшее улучшение плана невозможно, что означает, что мы нашли оптимальный план.

План оптимален.

	B1	B2	B3	B4	B5	ai
A1		⁴		⁸		⁹	²	¹
A2		⁸		³		¹⁰	¹	²
A3		⁵		⁴		⁶	⁷	⁹
A4		¹		¹⁰		⁷	⁵	³
A5		²		⁴		⁷	¹⁰	⁸
bi

Таблица 5.7 – Оптимальный план

Листинг программы приведен в приложении А, а результаты её выполнения – в приложении Б.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

1 2 3 4 5 6 7

Соучастие в преступлении: понятие и признаки. Виды соучастников и формы соучастия

НЭП: ПРИЧИНЫ, СУЩНОСТЬ И ПРОТИВОРЕЧИЯ

Среднее квадратическое отклонение

Основные теории происхождения государства

Гражданская война в России. Причины, ход, итоги и последствия

ВИДЫ ОРУЖИЯ МАССОВОГО ПОРАЖЕНИЯ И ПОСЛЕДСТВИЯ ЕГО ПРИМЕНЕНИЯ

Самый сильный аргумент, почему эволюция человека не могла быть