Метод указания к лаб работам ИСО, страница 4

Минимизировать .

при ограничениях:

{1..m}

{1..n}.

В исследовании операций полностью целочисленную транспортную задачу обычно называют классической транспортной задачей.

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

Транспортная задача всегда может быть задана таблицей издержек, связанных с перевозками грузов из данных источников в данные пункты назначения. В ячейку с координатами (i,j) таблицы издержек записывают стоимость перевозки единицы груза из истока i в сток j. Кроме значений стоимости перевозок в данную таблицу в соответствующих строках помещают величины запасов в пунтках-истоках, а в соответствующих столбцах – величины заявок пунктов-стоков. Ниже приведен пример заполненной таким образом таблицы издержек.

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

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

И
так, каждая переменная соответствует потоку вдоль ориентированной дуги из истока I в сток j. Тогда соответствующая ему величина выражает затраты в расчете на единицу потока, а сама задача заключается в распределении мощностей истоков по дугам таким образом, чтобы при минимальных затратах удовлетворить потребности стоков.

Прежде чем переходить к рассмотрению конкретных при­меров, рассмотрим несколько особенностей постановки классической транспортной задачи.

Прежде всего, следует отметить, что затраты, связанные с производством еди­ницы товара, как правило, не одинаковы для различных пунк­тов производства. При формулировке транспортной задачи мы предполагали единую себестоимость производства и хранения единицы товара в каждом из истоков. В случае необходимости учета разности этих затрат при постановке транспортных задач следует включить эти величины в коэффициенты .

В реальных задачах транспортного типа нетрудно предположить возможность возникновения ситуации, в которой некоторому истоку будет доступен не каждый из имеющихся стоков. В формулировке классической транспортной задачи данная возможность нами учтена не была. Для того, чтобы все-таки учесть подобную ситуацию, договоримся о том, что если в силу каких-либо причин i-й пункт производства не доступен для j-го пункта потребления, то либо исключим из рассмотрения переменную модели , либо примем соответствующую ей величину сколь угодно большой.

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

В ряде случаев возникает необходимость учета ограничений, связанных с пропускной способностью той или иной ориентированной дуги сети, при постановке транспорт­ной задачи. Задачу транспортную задачу исследования операций при наличии ограничений пропускных способностей дуг называют транспортной задачей с ограничениями по пропуск­ной способности.

Как правило, введение ограничений на пропускные способности дуг в математическую модель классической транспортной задачи приводит лишь к незначительному увеличению объема вычи­слений при поиске оптимального решения. Однако иногда эти ограничения оказываются настолько жесткими, что множество допустимых решений рассматриваемой задачи оказывается пу­стым.

При постановке классической транспорт­ной задачи предполагают идентичность ассортимента, то есть считается, что все пункты производства выпус­кают одну и ту же продукцию. Однако на практике подобная ситуация встречается крайне редко. Обычно, каждое пред­приятие выпускает несколько наименований или, хотя бы, разновидностей товаров, а при разработке плана их перевозок необходимо учитывать всю номенклатуру. Как можно легко себе представить, требуется немалая изобретательность, чтобы подогнать реальную распределительную задачу к условиям клас­сической транспортной модели. К сожалению, здесь нет возможности перечислить все приемы, позволившие успешно справиться с такой подгонкой на практике. Для пояснения основных понятий, которыми при этом пользуются, ниже приводится краткое описание одного из подходов к решению этой проблемы.

Пусть спрос на различные виды продукции в каждом пункте потребления (стоке) j в течение планируемого периода известен. Примем в качестве единицы измерения общего количества требуемой продук­ции всех видов какую-либо удобную общепринятую меру, напри­мер тонну. Аналогично будем измерять поставки в тех же едини­цах. При вычислении величин стоимостей перевозок предположим, что если некоторое предприя­тие i отправляет тонну продукции потребителю j, то эта тонна вклю­чает все виды продуктов, необходимых в пункте j в заданных про­порциях.

Здесь сразу же возникает вопрос, насколько практически реализуемым и точным будет полученное числовое решение задачи. Чтобы разумно отве­тить на этот вопрос, нужно иметь в виду два обстоятельства. Прежде всего, решение, в сущности, представляет собой некоторый план распределения продуктов в течение заданного интервала времени. Иными словами, модель обеспечивает прикрепление предприятий к пунктам назначения или поставщиков к потребителям. Числовые значения величин перевозок по самой своей природе являются приближенными, поскольку в большинстве реальных случаев значения запросов в пунктах потребления представ­ляют собой лишь прогнозы потребностей на планируемый период. В связи с этим значения , полученные в процессе решения, не являются фактическими значениями количества перевозимых продуктов, а слу­жат только оценками величины будущих поставок. Рассуждая дальше, относи­тельные достоинства полученного плана необходимо сравнить с любы­ми практически реализуемыми вариантами, которые может исполь­зовать фирма, в том числе, разумеется, с принятым планом перево­зок. Учитывая эти соображения, многие фирмы могут существенно повы­сить свои доходы, приняв план перевозок, основанный на решении классической транспортной задачи.

Вернемся теперь непосредственно к рассмотрению методов решения транспортной задачи. Пусть задана некоторая классическая транспортная задача.

Предположим, что имеется n пунктов потребления (например, промышленных предприятий или типографий) П_j, j {1..n}, требующих снабжения некоторым определенным видом сырья. Потребности в сырье каждого предприятия П_j равны соответственно b_j условных единиц j {1..n}. Кроме того, имеется m складов С_i, i {1..m}, на которых хранится требуемое предприятиям сырье. На каждом складе С_i имеется в наличии запас товара в количестве a_i соответственно, i {1..m}. Склады удалены от предприятий на некоторые расстояния и связаны с ними некоторыми путями сообщений с различными тарифами на перевозку грузов (в нашем случае сырья). Будем считать, что каждый склад связан с каждым пунктом потребления некоторым единственным маршрутом с неограниченной пропускной способностью. Единица сырья, получаемая предприятием П_j со склада C_i с учетом известных тарифов на перевозки, обходится в c_ij рублей. Для простоты предположим, что все заявки выполнимы и обеспечивают отсутствие излишек на складах, т.е. сумма всех заявок в точности равна сумме всех имеющихся запасов:

.