Вычитание минимального элемента по строкам и выявление минимальных элементов во столбцам

15	11	8	0	8	14
7	3	5	0	2	4
10	7	5	0	20	18
13	11	6	8	0	17
8	0	2	3	1	0
7	9	3	2	0	4
7	0	2	0	0	0

Минимальный элемент вычитается из всех элементов соответствующего столбца.

Таблица 2.41.

Вычитание минимального элемента по столбцам

8	11	6	0	8	14
0	3	3	0	2	4
3	7	3	0	20	18
6	11	4	8	0	17
1	0	0	3	1	0
0	9	1	2	0	4

Дальнейший поиск оптимального решения осуществляется в соответствии с обычным алгоритмом (см. пример 2.9).

Недопустимые назначения

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

НЕСООТВЕТСТВИЕ ЧИСЛА ПУНКТОВ ПРОИЗВОДСТВА И НАЗНАЧЕНИЯ

Если исходная таблица не является квадратной, в нее следует включить дополнительные фиктивные строки и столбцы, необходимые для приведения ее к квадратной форме. Значения стоимости, соответствующие фиктивным клеткам, как правило, равны нулю.

Назначения, размещаемые в клетках фиктивных строк, фактически не существуют. Назначения, соответствующие фиктивным столбцам, на деле представляют собой те единицы, которые не подлежат распределению.

РЕЗЮМЕ

Транспортная модель — это частный случай модели линейного программирования. Стандартная задача включает в себя некоторое множество пунктов производства, например, несколько торговых складов, которые осуществляют поставки в некоторое множество пунктов назначения, например, в несколько магазинов. Цель состоит в минимизации общей стоимости транспортировки в рамках ограничений на спрос и предложение. Решение этой задачи может быть найдено с помощью традиционных методов линейного программирования. Относительно простая структура задачи позволяет, однако, разработать специальные алгоритмы, применение которых оказывается более трудоемким, чем применение обычных методов решения задач линейного программирования с множеством переменных.

Первый шаг алгоритма состоит в построении транспортной таблицы, в которой содержится информация об издержках транспортировки. Строкам этой таблицы соответствуют пункты производства, а столбцам — пункты назначения.

Второй шаг алгоритма — это поиск начального распределения перевозок. Нами было описано два метода реализации данной процедуры. В методе минимальной стоимости перевозки распределяются в первую очередь по наиболее дешевым маршрутам. Метод Вогеля предполагает расчет значений штрафной стоимости и такое распределение перевозок, которое позволяет избежать получения высоких штрафов. Однако ни один из методов не гарантирует, что полученное начальное распределение перевозок окажется оптимальным.

Третий шаг состоит в проверке начального распределения перевозок на оптимальность. Мы изложили два метода проверки решения на оптимальность. Оба они основаны на вычислении значений теневых цен для незаполненных клеток. Если эти значения положительны или равны нулю для всех пустых клеток, то полученное распределение перевозок является оптимальным.

В методе ступенек в пустую клетку помещается одна единица продукции. Затем определяются натуральные и стоимостные изменения, происшедшие под воздействием такого размещения. Метод МОДИ в большей степени основан на математической теории. Используя значения стоимости перевозки в каждой заполненной клетке, мы получаем стоимость, соответствующую строке или столбцу:

с_ij= u_i + v_j.

Используя значения компонент u и v, полученных для строк и столбцов соответственно, рассчитывают значения теневых цен, соответствующие всем пустым клеткам. Их расчет производится по формуле:

s_ij = c_jj - (u_i + v_j).

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

Транспортная задача может иметь некоторые специфические особенности. Если предложение и спрос несбалансированны, то необходимо ввести в задачу фиктивные пункты производства или назначения. Оптимальное решение должно находиться в крайней точке допустимого множества, иными словами, должно быть базисным. Базисным называется решение, число переменных в котором равно числу строк в таблице плюс число столбцов минус единица. Если число переменных оказывается меньше указанной величины, то решение является вырожденным, и в этом случае следует использовать пустые клетки, размещая в них псевдоперевозки, объем которых равен нулю.

Недопустимые маршруты могут быть блокированы введением в соответствующие клетки таблицы достаточно больших значений стоимости транспортировки. Целевую функцию задачи можно не только минимизировать, но и максимизировать.

Еще более специфической задачей, для которой разработаны особые методы решения, является задача о назначениях. Число пунктов производства в этой задаче совпадает с числом пунктов назначения, причем каждой строке и каждому столбцу должно соответствовать только одно назначение. Для решения этой модифицированной транспортной задачи был разработан Венгерский метод.