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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(10)

при условиях

(11)

(12)

(13)

Поскольку переменные удовлетворяют системам линейных уравнений (11) и (12) и условию неотрицательности (13), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

1.4Двойственные задачи линейного программирования Каждой задаче линейного программирования можно поставить в соответствие задачу, называемую двойственной к исходной. Предположим, что в производстве используется m различных видов ресурсов, объем которых ограничен величинами b 1, b 2,.., b m. И производится n различных видов продукции, величина выпуска которых определяется переменными х 1, х 2,…, х n. Известны нормы затрат каждого ресурса на единицу каждого вида продукции, образующие матрицу (14) Известна также стоимостная оценка (цена) единицы продукции каждого вида с 1, с 2,…, с n. Задача сводится к следующему: найти такие значения переменных х 1, х 2,…, х n, при которых расход ресурсов не превышает заданного их количества, а стоимость всей продукции достигает максимума. В математической форме задача записывается следующим образом: максимизировать L = c 1 x 1+ c 2 x 2+…+ c n x n (15) при условия (16) ³0 (j =1, 2,.., n). На базе тех же исходных данных может быть поставлена еще одна задача, в которой переменными величинами являются оценки у 1, у 2,…, у m, приписываемые каждому виду ресурсов. Они должны быть такими, чтобы общая оценка всего имеющегося количества ресурсов была минимальной, но при условии, что суммарная оценка ресурсов, расходуемых на единицу любого вида продукции, будет не меньше, чем цена за эту единицу. Математическая задача записывается следующим образом: минимизировать `L = b 1 y 1+ b 2 y 2+…+ b m y m (17)   при условиях (18)