От: 1

Фиктивный

источник

поставок

Спрос

В Предложение

Следующая наименьшая стоимость ячейки - $6 в ячейке 1-В. В эту ячейку {на этот маршрут) надо распределить как можно больше единиц. Оставшийся спрос для столбца В - 15, и общее количество строки -- 75. Мы назначаем меньшую из этих величин, т. е. 15, ячейке 1 -В, таким образом исчерпывая столбец и уменьшая поставки в строке до 60. Затем мы перечеркиваем затраты ячеек столбца В.

Фиктивный

источник

поставок

Спрос

Предложение

Если по-прежнему игнорировать фиктивную строку, то следующая самая низкая стоимость ячейки - $9 в ячейке 1-А, где поставка 60 и спрос 80 единиц. Мы назначаем меньшее из этих значений, т. е. 60 единиц ячейке 1-А, поэтому значения затрат в строке 1 должны быть вычеркнуты. Также, пересмотрев столбец А, получаем его общее количество, равное 20.

Фиктивный

источник

поставок

Спрос

Теперь остается только фиктивная строка. Фиктивная ячейка А имеет поставку и спрос, равные 20; распределение данного количества в ячейку исчерпывает как поставку, так и спрос, заканчивая начальное распределение.

чДо:

От: 1

Фиктивный

источник

поставок

Спрос

В Предложение

, Следующий шаг -проверка полученного решения на оптимальность. Сначала мы должны проверить полноценность: R + С - 1 = 3 (строки) + 2 (столбца) -1=4, необходимое количество заполненных ячеек. Поскольку в нашем решении имеются четыре заполненных ячейки, решение не является неполноценным. Для оценки может использоваться или метод перехода по камням или MODI. Предположим, что будем использовать MODI. Мы всегда начинаем с размещения ноля слева в строке 1. Это индекс строки 1. Мы можем использовать его, чтобы найти индекс столбца для любой заполненной ячейки в строке 1. Поскольку и ячейка 1 -А, и ячейка 1 -В являются заполненными, мы можем получать для обеих значение индекса столбца. Для заполненных ячеек, сумма индексов строки и столбца должна равняться значению ячейки. Для ячейки 1-А: О -ь индекс столбца = 9, следовательно индекс столбца А должен равняться 9. Аналогично, для ячейки 1-В, О -ь индекс столбца = 6, следовательно, индекс столбца должен равняться 6. Затем эти индексы используются, чтобы найти значения индекса строки для законченных ячеек в соответствующих им столбцах. Таким образом, для ячейки 2-В, 6 -ь индекс строки = 3, поэтому индекс строки должен равняться -3. Для фиктивной ячейки А, 9 -ь индекс строки = О, поэтому индекс строки должен быть -9.

От: О 1

-3 2

Фиктивный

источник

поставок

Спрос

А 9 В 6 Предложение

Затем мы используем эти индексы для оценки пустых ячеек. Оценка ячейки определяется, вычитая из значения ячейки суммы индексов строки и столбца. Таким образом, для ячейки 2-А мы имеем 5 - (-3 -ь 9) = -1, и для фиктивной ячейки В мы имеем О - (-9 -ь 6) = 3.

От: О 1

-3 2

фиктивный

источник

поставок

Спрос

А 9 В 6 Предложение

Появление отрицательной оценки ячейки говорит о том, что решение может быть улучшено. Когда появляются отрицательные значения, мы выбираем ячейку с наибольшим из них, и концентрируем на ней наши усилия, чтобы улучшить решение. Так как имеется только одна такая ячейка, мы ее и выбираем, г. Значение -1 в ячейке 2-А говорит нам, что каждая единица, которую мы распределим в эту ячейку, уменьшает общую стоимость решения на $1. Разумеется, желательно поместить в эту ячейку как можно больше единиц, но мы ограничены общими количествами строки и столбца (строка 2 и столбец А). Мы также ограничены необходимостью сохранить общие количества для всех строк и столбцов. Чтобы помещать единицы в ячейку 2-А, мы должны брать их из некоторой другой ячейки, которая будет находиться в другой строке или другом столбце. К счастью, эту проблему несложно решить: определите путь перехода для ячейки 2-А (методом перехода по камешкам ) и используйте его для руководства перераспределением. Этот путь проиллюстрирован в следующей таблице:

От: 1

Фиктивный

источник

поставок

Спрос

.До: А

В Предложение

Количество, которое может быть перемещено в ячейку 2-А, - это наименьщая величина, которая появляется в отрицательной позиции пути. Имеются две таких величины, 60 и 75. Поскольку 60 меньшая из них, она перемещается по всему пути (т.е. прибавляется там, где имеется знак + и вычитается там, где имеется знак -). Результат - наше пересмотренное решение:

ЧДоА От:-

Фиктивный

источник

поставок

Спрос

В Предложение

. Это улучшенное решение может быть оптимальным, или может требовать дальнейшего изменения. Чтобы выяснить это, мы должны его оценить. Сначала мы проверяем его полноценность: R + C-1=3-l-2-l=4. У нас имеются 4 заполненные ячейки, значит, решение полноценно.

Затем мы разрабатываем индексы MODI, используя заполненные ячейки. Мы всегда начинаем, назначая индекс О первой строке. Тогда для любой заполненной ячейки в первой строке номер индекса столбца-такой же, как стоимость ячейки. Поскольку ячейка 1 -В имеет стоимость ячейки 6, то индекс столбца В также равен 6. Используя это значение и стоимость заполненной ячейки 2-В, получаем индекс для строки 2: стоимость ячейки - индекс столбца = индекс строки. Таким образом, 3 - 6 = -3. Индекс этой строки 2 можно использовать вместе со стоимостью законченной ячейки 2-А, чтобы найти ицдекс столбца А, 5 - (-3) = 8, а индекс 8 можно использовать со стоимостью фиктивной ячейки А, для получения индекса фиктивной строки: 0-8 =-8 Эти индексы показаны в следующей таблице:

-3 2 -8

Фиктивный

источник

поставок

Спрос

4/*°- А 8 В 6 Предложение

Теперь можно определить оценки для пустых ячеек. Ячейка 1-А: 9 - (О-I-8) = 1

Ячейка фиктивная В: О - (-8 + 6) = 2

Поскольку отрицательные оценки отсутствуют, полученное решение оптимально: Отправьте 75 единиц от 1 к В, 60 единиц от 2 к А, и 15 единиц от 2 к В. 20 единиц