Методы северо-западного угла, минимального элемента, Фогеля и двойного предпочтения

Задача 1

Однородный продукт, сосредоточенный на трех  складах фирмы в количествах единиц, необходимо распределить между четырьмя магазинами, которым необходимо соответственно единиц продукта. Стоимость перевозки единицы продукта из  i-го пункта отправления      (i = 1, 2, 3) в  j-й пункт назначения (j = 1, 2, 3, 4) равна     и известна для всех маршрутов.

Вектор запасов продукта на складах 

вектор запросов продукта магазинами 

и матрица транспортных тарифов 

Построить начальный опорный план транспортной задачи методом северо-западного угла.

Решение

Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:

В нашем случае:

Модель транспортной задачи закрытая.

Построим начальный опорный план по правилу северо-западного угла.

Начинаем заполнение с левого верхнего угла и далее двигаемся по диагонали к правому нижнему углу.

Число занятых клеток должно быть .

В нашем случае число занятых клеток равно 6 - опорный план является невырожденным.

Найдем стоимость перевозок опорного плана:

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

Задача 2

На предприятиях  производится однородная продукция в количестве  единиц. Себестоимость производства одной единицы продукции на i-м предприятии равна соответственно  ден.ед. Готовая продукция поставляется потребителям , потребности которых составляют  единиц. Для полного удовлетворения потребностей необходимо увеличить выпуск продукции. Для этого освоить выпуск данной продукции на предприятии  с себестоимостью производства продукции  ден.ед.  Стоимости перевозки одной единицы продукции от каждого предприятия каждому потребителю задаются матрицей .

Требуется построить начальный опорный план транспортной задачи методом минимального элемента.

Решение

Условие баланса:

В нашем случае:

Вводим дополнительного поставщика , у которого имеется  2600-1800=800 единиц груза.

Составим матрицу затрат на производство и транспортировку продукции.

Построим начальный опорный план по правилу минимального элемента.

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту (2,4), поэтому в клетку помещаем . В этом случае 2-я строка в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка (4,3).

Далее, действуя по аналогичной схеме, получаем:

Число занятых клеток должно быть .

В нашем случае число занятых клеток равно 7 - опорный план является невырожденным.

Найдем стоимость перевозок опорного плана:

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

Задача 3

Ниже приведены числовые данные транспортной задачи. Стоимость перевозки единицы продукции записана в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу.

Требуется построить начальный план методом Фогеля.

Решение

Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:

В нашем случае:

Модель транспортной задачи закрытая.

Воспользуемся способом Фогеля для нахождения начального опорного плана транспортной задачи. В каждом ряду и столбце матрицы  найдем минимальный и ближайший к нему элементы и их разность по абсолютной величине записываем в конце соответствующего ряда справа и снизу. Находим максимальную из этих разностей (число 29 заключено в рамку). В ряду (или столбце), соответствующем максимальной разности, находим минимальный элемент . В клетку (3,5) вписываем число

С оставшейся матрицей поступаем аналогично предыдущему. Все вычисления сведены в таблицу.

Получили начальный опорный план транспортной задачи методом Фогеля.

Найдем стоимость перевозок опорного плана:

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

Задача 4

Составить план перевозки зерна из районов  на пять элеваторов  (запасы районов и мощности элеваторов приведены) с минимальными издержками за перевозку. Затраты на перевозку 1 ц заданы.

Начальный план перевозок составить по правилу двойного предпочтения.

Решение

Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:

В нашем случае:

Модель транспортной задачи закрытая.

Заполняем таблицу по правилу двойного предпочтения.

Сначала в каждой строке находим клетку с минимальным тарифом. Если таких клеток несколько (одинаковые значения) то выбираем их все. В выбранных ячейках ставим отметку *.

Затем выполняем те же самые действия, только на тот раз по столбцам. То есть в каждом столбце тоже находим клетку (клетки) с минимальным тарифом и ставим в ней отметку – *.

Начинаем заполнять транспортную таблицу. В первую очередь заполняем ячейки с двумя звездочками (если их несколько, выбираем ту в которой меньший тариф). Далее заполняем клетки с одной звездочкой. Если остались нераспределенные запасы и неудовлетворенные потребности – заполняем оставшиеся клетки без звездочек.

Найдем стоимость перевозок опорного плана:

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