Второй этап

Строим цепочку из выделенных штрихом или звездочкой нулей, начиная с 0’, расположенного в строке с ненулевой невязкой и идем далее по столбцу, строке, столбцу, чередуя 0* с 0’ до тех пор, пока это возможно. В данном случае цепочка состоит из 3 элементов и имеет вид:

Далее ищем минимум среди четных элементов цепочки матрицы Х, невязки строки, где началась цепочка и невязки столбца, где она закончилась, т.е.

Переходим к новой матрице Х путем прибавления к нечетным элементам цепочки и вычитания из четных элементов. Элементы, не входящие в цепочку, остаются без изменений. Получим

Х₁=

. Переходим ко второй итерации.

Итерация 2

Первый этап

Т.к. все нули оказались выделены, и во всех просматриваемых строках невязки равны нулю, то переходим к третьему этапу.

Третий этап

Среди невыделенных элементов матрицы С₁ ищем минимальный, в данном случае h=1. Далее вычитаем этот элемент из всех невыделенных строк, а затем прибавляем его ко всем выделенным столбцам. В результате получим новую матрицу и снова переходим к первому этапу.

Первый этап

Для очередного невыделенного нуля, расположенного в 4 строке 5 столбца, невязка строки больше 0, поэтому отмечаем данный нуль штрихом и переходим ко второму этапу.

Второй этап

Строим цепочку из выделенных штрихом или звездочкой нулей, начиная с 0’, расположенного в строке с ненулевой невязкой и идем далее по столбцу, строке, столбцу, чередуя 0* с 0’ до тех пор, пока это возможно. В данном случае цепочка состоит из 1 элемента и имеет вид:

Далее ищем минимум среди невязки строки, где началась цепочка и невязки столбца, где она закончилась, т.е.

Переходим к новой матрице Х путем прибавления к нечетным элементам цепочки и вычитания из четных элементов. Элементы, не входящие в цепочку, остаются без изменений. Получим

Х₂=

. Переходим к третьей итерации.

Итерация 3

Первый этап

Т.к. все нули оказались выделены, и во всех просматриваемых строках невязки равны нулю, то переходим к третьему этапу.

Третий этап

Среди невыделенных элементов матрицы С₁ ищем минимальный, в данном случае h=1. Далее вычитаем этот элемент из всех невыделенных строк, а затем прибавляем его ко всем выделенным столбцам. В результате получим новую матрицу и снова переходим к первому этапу.

Первый этап

Для очередного невыделенного нуля, расположенного в 4 строке 3 столбца, невязка строки больше 0, поэтому отмечаем данный нуль штрихом и переходим ко второму этапу.

Второй этап

Строим цепочку из выделенных штрихом или звездочкой нулей, начиная с 0’, расположенного в строке с ненулевой невязкой и идем далее по столбцу, строке, столбцу, чередуя 0* с 0’ до тех пор, пока это возможно. В данном случае цепочка состоит из 1 элемента и имеет вид:

Далее ищем минимум среди невязки строки, где началась цепочка и невязки столбца, где она закончилась, т.е.

Переходим к новой матрице Х путем прибавления к нечетным элементам цепочки и вычитания из четных элементов. Элементы, не входящие в цепочку, остаются без изменений. Получим

Х₃=

. Переходим к четвертой итерации.

Итерация 4

Первый этап

Т.к. все нули оказались выделены, и во всех просматриваемых строках невязки равны нулю, то переходим к третьему этапу.

Третий этап

Среди невыделенных элементов матрицы С₁ ищем минимальный, в данном случае h=1. Далее вычитаем этот элемент из всех невыделенных строк, а затем прибавляем его ко всем выделенным столбцам. В результате получим новую матрицу и снова переходим к первому этапу.

Первый этап

Для очередного невыделенного нуля, расположенного в 4 строке 3 столбца, невязка строки больше 0, поэтому отмечаем данный нуль штрихом и переходим ко второму этапу.

Второй этап

Строим цепочку из выделенных штрихом или звездочкой нулей, начиная с 0’, расположенного в строке с ненулевой невязкой и идем далее по столбцу, строке, столбцу, чередуя 0* с 0’ до тех пор, пока это возможно. В данном случае цепочка состоит из 3 элементов и имеет вид:

Далее ищем минимум среди четных элементов цепочки в матрице Х, невязки строки, где началась цепочка и невязки столбца, где она закончилась, т.е.

Переходим к новой матрице Х путем прибавления к нечетным элементам цепочки и вычитания из четных элементов. Элементы, не входящие в цепочку, остаются без изменений. Получим

Х₄=

. Переходим к пятой итерации.

Итерация 5

Первый этап

Т.к. все нули оказались выделены, и во всех просматриваемых строках невязки равны нулю, то переходим к третьему этапу.

Третий этап

Среди невыделенных элементов матрицы С₁ ищем минимальный, в данном случае h=1. Далее вычитаем этот элемент из всех невыделенных строк, а затем прибавляем его ко всем выделенным столбцам. В результате получим новую матрицу и снова переходим к первому этапу.

Первый этап

Для очередного невыделенного нуля, расположенного в 4 строке 5 столбца, невязка строки больше 0, поэтому отмечаем данный нуль штрихом и переходим ко второму этапу.

Второй этап

Строим цепочку из выделенных штрихом или звездочкой нулей, начиная с 0’, расположенного в строке с ненулевой невязкой и идем далее по столбцу, строке, столбцу, чередуя 0* с 0’ до тех пор, пока это возможно. В данном случае цепочка состоит из 5 элементов и имеет вид:

Далее ищем минимум среди четных элементов цепочки в матрице Х, невязки строки, где началась цепочка и невязки столбца, где она закончилась, т.е.

Переходим к новой матрице Х путем прибавления к нечетным элементам цепочки и вычитания из четных элементов. Элементы, не входящие в цепочку, остаются без изменений. Получим

Х₄=

. Оптимальное решение найдено. Транспортные расходы = 2952.