Лекция№04-тпр (1) 2.10.14

Лекция №4.

Открытая модель КТЗ.

Модель закрытой КТЗ имеет вид:

(1)

(2)

(3)

(4)

Если в КТЗ условие баланса не выполняется, т.е. , а именно так чаще всего и случается на практике, то такую модель КТЗ называют открытой. При этом возможны два случая: суммарный объем производимой продукции превышает суммарный объем потребления (перепроизводство) и суммарный объем производимой продукции меньше суммарного объема потребления (дефицит).

1.Рассмотрим первый случай: . В этом случае не обязательно вывозить всю продукцию из всех пунктов производства. Тогда в модели (1)-(4) вместо ограничения (2) будет стоять следующее:

(5).

Для решения открытой КТЗ (1),(5),(3), (4) необходимо свести ее к закрытой КТЗ. Для этого добавляется фиктивный пункт потребления с номером с потреблением . Чтобы объемы фиктивных перевозок не меняли значение целевой функции, стоимость перевозки в фиктивный пункт полагают равной нулю:

Тогда ограничение (5) пр6вращается в ограничение вида:

(6)

Таким образом, получаем закрытую модель КТЗ. Пусть задача (1), (6), (3), (4) решена и найдены оптимальные значения перевозок .Эти значения позволяют принять и дополнительное решение: в каких пунктах и насколько сократить объем производства. Если , то в i–том пункте производства нужно сократить выпуск продукции на величину . Однако такое сокращение будет оптимальным только с точки зрения транспортных расходов. При принятии решения о сокращении производства необходимо еще учитывать себестоимость производства продукции. Если затраты на производство единицы продукции в i–том пункте обозначить и включить их в состав транспортных затрат , то получится задача о сокращении производства.

2.Теперь рассмотрим случай дефицита производства, когда . В этом случае невозможно удовлетворить запросы всех пунктов потребления, поэтому в модели (1)-(4) ограничение (3) примет вид:

(7).

Эта задача также сводится к закрытой КТЗ путем введения фиктивного пункта производства с номером с объемом производства . Тогда ограничение (7) превращается в ограничение вида (8):

(8).

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

Теорема о целочисленности решения КТЗ.

Если в КТЗ (1)-(4) значения целые, то и оптимальный план КТЗ будет целочисленным.

Доказательство. Пусть - целые числа и КТЗ решена методом потенциалов. Начальный опорный план такой задачи будет целочисленным, так как при его построении в каждой клетке назначалась целочисленная переменная . При переходе к лучшему опорному плану вычислялась добавка Q=min{}, поэтому Q также будет целым. Это целое число либо прибавляется к компонентам опорного плана, либо вычитается из них. Т.о. все рассматриваемые в ходе решения задачи опорные планы будут целочисленными. Следовательно, и оптимальный план будет целочисленным. 

Задача о назначениях.

(Задача выбора)

Постановка задачи. Пусть имеется n заказов с номерами и имеются n исполнителей с номерами , т.е. число заказов равно числу исполнителей. Любой заказ м.б. выполнен любым исполнителем., при этом стоимость выполнения i–того заказа j-тым исполнителем равна . Необходимо закрепить заказы за исполнителями так, чтобы все заказы были выполнены, у всех исполнителей был заказ, а суммарная стоимость выполнения заказов была бы минимальной.

Построим ММ задачи.

Пусть

Тогда модель задачи о назначениях запишется в виде:

(1)

(2)

(3)

(4)

Здесь целевая функция (1) выражает суммарную стоимость выполнения заказов, ограничения (2) требуют, чтобы у каждого заказа был исполнитель, а ограничения (3) – чтобы у каждого исполнителя был заказ.

Модель (1)-(4) относится к классу задач линейного целочисленного, а именно булевского, программирования. Решение такого класса задач является очень трудоемким и за приемлемое время можно получить решение лишь для задач небольшой размерности. Однако задача (1)-(4) имеет особенности, которые позволяют свести ее к КТЗ. Для этого условие (4) записывается условно как:

(5).

Тогда задача (1)-(3), (5) является частным случаем КТЗ при m=n, . Пусть эта задача решена методом потенциалов и получено решение . Будет ли это решение являться и решением исходной задачи (1)-(4)? ДА! На основании теоремы о целочисленности решения КТЗ значения целые. Они удовлетворяют ограничениям (2), (3). Но сумма неотрицательных целых чисел очевидно будет равна 1 только тогда, когда слагаемые равны 0 и 1, т.е. . Таким образом выполняется условие (4).

Если число заказов больше или меньше числа исполнителей, то вводят либо фиктивных исполнителей, либо фиктивные заказы.

Примечание. Таким образом, задачу о назначениях можно решить как КТЗ. Однако существуют специальные более эффективные методы. Один из таких алгоритмов известен под названием «Венгерский метод» (см. Таха Х. «Введение в ТПР»).

Транспортная задача в сетевой постановке

(с промежуточными пунктами).

В КТЗ продукция перевозится непосредственно из любого пункта производства в любой пункт потребления. Однако в реальных задачах перевозка грузов производится по различным коммуникациям. Из данного пункта производства в данный пункт потребления можно попасть различными путями, побывав в других промежуточных пунктах. Например: Заводы- Оптовые базы- Потребители.

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

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

В настоящее время для решения таких задач существуют достаточно эффективные алгоритмы, основанные на модификации метода последовательного улучшения плана ЗЛП.

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

Метод отыскания путей минимальной стоимости.

Построение ММ. Узлы транспортной сети классифицируем следующим образом:

1. - множество узлов с излишками продукции, назовем их пунктами производства.

2. - множество узлов с нехваткой продукции, назовем их пунктами потребления.

На сети можно выделить совокупность путей, позволяющих перейти из пункта в пункт :

i j

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

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

Пусть - объем перевозок из пункта i в пункт j по кратчайшему пути. Тогда оптимальные объемы перевозок по путям минимальной стоимости определяются из решения следующей КТЗ:

(1)

(2)

(3)

(4)

Т.О. в результате решения серии задач поиска кратчайшего пути для исходной транспортной сети, модель ТЗ в сетевой постановке сводится к КТЗ (1)-(4). Здесь в качестве производителей выступают узлы с излишками продукции, а в качестве потребителей – узлы с недостатком продукции.