Транспортная задача (1 а л.) 1 Определение транспортной модели
жүктеу/скачать 0.49 Mb.
|
|
Глава 3. Транспортная задача (1 а.л.) 3.1 Определение транспортной модели Транспортная модель традиционно используется при разработке планов перевозок одного вида продукции из нескольких пунктов отправления в несколько пунктов назначения. Транспортная модель может рассматриваться, как задача линейного программирования, и может быть решена симплекс методом, но специальная структура транспортной задачи позволяет решить ее более эффективными алгоритмами. Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1, A2…Am, в n пунктов назначения B1,B2… Bn. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. При решении транспорт ной задачи необходимо: обеспечить всех потребителей ресурсами; распределить все произведенные ресурсы; переместить ресурсы от производителей к потребителям с наименьшими затратами. От каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Пусть есть m пунктов производства некоторой продукции с объемом производства ai. Пусть имеется n пунктов потребления, с объемами потребления bj в каждом. Обозначим через cij стоимости перевозок единицы продукции из пункта производства i в пункт потребления j, и через xij объемы перевозок из i в j. Тогда математическая постановка задачи состоит в определении минимального значения функции: (3.1) При ограничениях: (3.2) Первое неравенство системы ограничений (3.2) соответствует условию, что из пункта производства нельзя вывезти больше продукции, чем ее произведено. Второе неравенство соответствует условию, что в пункт потребления должно быть завезено продукции не меньше, чем ее там требуется. Чтобы задача имела допустимые решения необходимо, чтобы объем производства был равен объему потребностей, т.е. (3.3) Здесь общее количество грузов поставщиков равно , а общая потребность в грузе единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах потребления, т.е. если (3.4) то модель такой задачи называется сбалансированной или закрытой. Условие (3.4) является условием разрешимости транспортной задачи. Если указанное условие не выполняется, то модель называется несбалансированной или открытой. Для сбалансированной задачи система ограничений заменяется таким образом, что неравенства превращаются в равенства. (3.5) В реальных условиях не всегда объем производства равен спросу или превосходит его. Однако, транспортную задачу всегда можно сбалансировать. В случае превышения запасов над потребностями, т.е. когда , вводится фиктивный (n+1) пункт назначения с потребностью , причем тарифы считаются равными нулю ,если нет никаких дополнительных условий. Аналогично, в случае превышения объемов потребностей над объемами запасов, т.е. когда , вводится фиктивный (m+1) пункт отправления с запасом груза . Количество продукции, отправляемой из фиктивного пункта производства в пункт назначения, представляет собой объем недостающей продукции в этом пункте. Продукция, поступающая в фиктивный пункт назначения, представляет собой избыток продукции в пункте изготовления данной продукции. При этом соответствующая стоимость перевозки единицы продукции считается равной нулю, так как на самом деле таких пунктов не существует. Однако, эту ситуацию можно рассмотреть и по-другому, считая, что каждая единица недопоставленной в пункт назначения продукции облагается штрафом. В этом случае транспортные расходы на единицу продукции равны штрафу за единицу продукции, недополученную в том или ином пункте назначения. Если рассматривается фиктивный пункт назначения, то имеется избыток производства и можно назначить штраф за хранение излишек продукции на складах, тогда стоимость перевозки одного вида продукции станет равной стоимости его хранения. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|