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

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

Модель транспортной задачи - student2.ru (10)

при условиях

Модель транспортной задачи - student2.ru (11)

Модель транспортной задачи - student2.ru (12)

Модель транспортной задачи - student2.ru (13)

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

1.4Двойственные задачи линейного программирования Каждой задаче линейного программирования можно поставить в соответствие задачу, называемую двойственной к исходной. Предположим, что в производстве используется m различных видов ресурсов, объем которых ограничен величинами b1, b2,.., bm. И производится n различных видов продукции, величина выпуска которых определяется переменными х1, х2,…, хn. Известны нормы затрат каждого ресурса на единицу каждого вида продукции, образующие матрицу Модель транспортной задачи - student2.ru (14) Известна также стоимостная оценка (цена) единицы продукции каждого вида с1, с2,…, сn. Задача сводится к следующему: найти такие значения переменных х1, х2,…, хn, при которых расход ресурсов не превышает заданного их количества, а стоимость всей продукции достигает максимума. В математической форме задача записывается следующим образом: максимизировать L = c1x1+c2x2+…+cnxn (15) при условия Модель транспортной задачи - student2.ru (16) Модель транспортной задачи - student2.ru ³0 (j=1, 2,.., n). На базе тех же исходных данных может быть поставлена еще одна задача, в которой переменными величинами являются оценки у12,…,уm, приписываемые каждому виду ресурсов. Они должны быть такими, чтобы общая оценка всего имеющегося количества ресурсов была минимальной, но при условии, что суммарная оценка ресурсов, расходуемых на единицу любого вида продукции, будет не меньше, чем цена за эту единицу. Математическая задача записывается следующим образом: минимизировать `L = b1y1+b2y2+…+bmym (17)   при условиях Модель транспортной задачи - student2.ru (18)

Наши рекомендации