Пример математической модели дискретного программирования (транспортная задача )

Имеется пунктов поставщиков и пунктов назначения (потребителей) .

— количество груза в тоннах, сосредоточенное в пункте ;

— количество груза, ожидаемое в пункте .

Принимаем условие

(6.16)

означающее, что суммарный запас груза равен суммарной потребности в нем.

— стоимость перевозки одной тонны груза из пункта в пункт .

— количество тон груза, перевезенное из пункта в пункт .

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

Неизвестными в нашей задаче являются неотрицательных чисел . Сведем их в таблицу 6.1, назовем ее матрицей перевозок.

Таблица 6.1. Матрица перевозок
			...
			...
			...
...	...	...	...	...	...
			...
			...

Запишем соотношение для пунктов поставщиков и пунктов потребителей .

Будем называть уравнение 0I горизонтальными уравнениями, а 0II – вертикальными. Перевозка из и стоит , общая стоимость всех перевозок будет

(II)

где суммирование производится по всем и всем . Таким образом, мы пришли к следующей задаче линейного программирования:

Дана система уравнений I и линейная функция II. Требуется среди неотрицательных решений системы найти такое, которое минимизирует функцию II.