Прараметрическое программирование

6 5 6 5

4 4 7 7

3 6 8 9

 

Обозначив объем  перевозок с i-го лесоводства на j-ый елочных базар через х_(i), а целевую функцию (общие затраты)— через F, построим математическую модель задачи:

F= 6* x₁₁ + 5* x₁₂ + 6* x₁₃ +5* x₁₄+ 4* x₂₁ + 4* x₂₂ + 7* x₂₃ + 7* x₂₄ + 3* x₃₁ + 6* x₃₂ + 8* x₃₃ + +9* x₃₄    min

 x₁₁ +  x₁₂ +  x₁₃ + x₁₄ ≤ 200,

 x₂₁ +  x₂₂ +  x₂₃ + x₂₄ ≤ 300,

 x₃₁ +  x₃₂ +  x₃₃ + x₃₄ ≤ 400,

 

 x₁₁ +  x₂₁ +  x₃₁ ≥ 300,

 x₁₂ +  x₂₂ +  x₃₂ ≥ 200,

 x₁₃ +  x₂₃ +  x₃₃ ≥ 150,

 x₁₄ +  x₂₄ +  x₃₄ ≥ 250,

x_ij ≥ 0, где i Є [1,3], j Є [1,4].

Знаки ≤ в  ограничениях означают, что со складов можно вывезти не больше груза, чем там имеется, а знаки ≥ — что в каждый магазин нужно доставить груза не меньше, чем требуется. Эти знаки справедливы, когда потребности в сумме не превосходят запасов груза (как в нашей задаче). Если же запасов не хватает для удовлетворения всех потребностей, используются специальные приемы, позволяющие решить задачу в Excel и там знаки неравенств не задаются и поэтому все варианты транспортной задачи вводятся одинаково.

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

2. Решение с помощью  пакета WinQSB

Запуск программы

Чтобы запустить  программу для сетевого моделирования, позволяющую, в частности, решать и транспортную задачу, щелкните кнопку Пуск, найдите программную группу WinQSB и выберите Network Modeling.

Задание параметров задачи

Для ввода  новой задачи выберите команду File, New Problem. Откроется окно: (рис.1.)

Рис. 1. Ввод параметров решения  транспортной задачи.

 

Необходимо  задать следующие параметры:

• Тип задачи — Transportation Problem.

  •   Вариант оптимизации — минимизация (Minimization) или максимизация Maximization).

• Форма задачи — матричная (Spreadsheet Matrix Form) или графическая (Graphic Model Form). Графическая форма — в виде сетевой диаграммы — нагляднее, но более трудоемка для ввода данных, так как требует рисования на экране узлов сети (пунктов отправления и назначения) и соединяющих их дуг (маршрутов перевозок). Поэтому в дальнейшем мы будем использовать матричную форму. Однако после ввода данных можно легко изменить форму задачи, воспользовавшись соответствующей командой меню Format.
• Название задачи — Problem Title.
• Количество пунктов отправления — Number of Sources.
• Количество пунктов назначения — Number of Destinations.

Ввод числовых данных

Если выбрана  матричная форма задачи, откроется  окно с таблицей для ввода данных: затрат на перевозку единицы груза в каждом направлении (тарифов), запасов груза в пунктах отправления и потребностей в пунктах назначения. Вид этого окна после ввода данных показан на рис. 3.2. Строки таблицы соответствуют пунктам отправления (Source), а столбцы — пунктам назначения (Destination). На их пересечении — тарифы соответствующих перевозок. В столбце Supply — запасы грузов в пунктах отправления, а в строке Demand — потребности в пунктах назначения.

Рис. 2. Ввод данных для решения транспортной задачи

 

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

• Перемещаться по таблице — с помощью клавиши Tab или клавиш со стрелками.
• Выбрать ячейку таблицы — щелчком этой ячейки. Если щелкнуть голубое поле над таблицей, то выбранная ячейка выделится цветом и можно редактировать ее содержимое.

С помощью  указанных далее команд меню Edit можно изменить следующие параметры задачи:

• Название задачи — Problem Name.
• Название пунктов отправления и назначения — Node Names.
• Вариант оптимизации целевой функции — Objective Function Criterion (при этом максимизация меняется на минимизацию и наоборот).
• Количество пунктов отправления и назначения — Add a Note или Delete a Note (пункты добавляются или удаляются, соответственно). По умолчанию  добавляются  новые  пункты  отправления.  Для  добавления пункта назначения выберите команду Add a Note а затем снимите флажок Added as a source. Здесь же можно задать также название добавляемого пункта.

Изменим названия пунктов отправления и назначения, как показано на рис. 3.

Рис. 3. Изменение пунктов  назначения и отправления

 

С помощью  указанных далее команд меню Format могут быть изменены:

• Форма задачи — Switch to Graphic Model или Switch to Matrix Form (можно перейти в графическую или матричную форму, соответственно).
• Формат чисел— Number.
• Шрифт и цвет — Font.
• Выравнивание—Alignment.
• Высота строк — Row Height.
• Ширина столбцов — Column Width.

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

Рис. 4. Транспортна задача в графической форме.

 

После ввода  данных задачи не забудьте сохранить  ее с помощью команды File > Save Problem As.

Нахождение  решения

Чтобы решить задачу, выберите в меню Solve and Analyze один из следующих вариантов действий:

• Решить задачу — Solve the Problem. Решение находится методом потенциалов. По окончании решения появляется отчет в виде таблицы, в которой указаны только ненулевые перевозки. В дальнейшем можно открыть этот отчет либо посредством меню Window, либо с помощью команды Results, Solution Table, Nonzero Only.
• Решить с показом шагов — Solve and Display Steps — Tableau или Solve and Display Steps — Network. При этом все итерации метода потенциалов показываются в  виде, соответственно, транспортных таблиц или сетевых диаграмм. На каждом шаге указываются перевозки, вводимые в базис и исключаемые из него. С помощью меню Iteration вы можете перейти к следующей итерации (Next Iteration), к концу решения с выводом отчета (Nonstop to Finish) или посмотреть информацию о вводимой и исключаемой перевозке (Show Entering and Leaving Arcs).

• Выбрать метод нахождения первоначального плана — Select Initial Solution Method. Перед началом решения можно выбрать один из восьми предложенных  методов, в частности методы северо-западного угла, минимального элемента, Фогеля и др. Имейте в виду, удачный выбор может ускорить поиск оптимального решения.

Анализ оптимального решения и его чувствительности

Отчет, появляющийся после завершения вычислений, представляет собой таблицу с перечнем только тех направлений, по которым предлагается перевозить груз, то есть выполнять ненулевые перевозки (рис. 5). В отчете содержится следующая информация:

Рис. 5. Отчет о решении задачи с перечнем нулевых перевозок.

В первом столбце  — номера ненулевых перевозок.

• В столбцах From и То — названия соответствующих пунктов от правления и назначения.
• В столбце Shipment— количество груза, которое следует перевозить в каждом направлении. В столбце Unit Cost— затраты на перевозку единицы груза в каждом направлении (тарифы).
• В столбце Total Cost — общие затраты на перевозку груза в каждом направлении (произведение количества груза на соответствующий тариф).
• В столбце Reduced Cost— нормированные стоимости — двойственные оценки, которые могут быть отличны от нуля только для нулевых перевозок. Чтобы увидеть такие перевозки и их нормированные стоимости, воспользуйтесь либо отчетом с перечнем всех перевозок (Solution Table —All), либо отчетом об интервалах оптимальности (Range of Optimality). 
  Как получить такие отчеты — говорится далее в этом разделе. Нормированная стоимость показывает: а) на какую величину нужно снизить тариф нулевой перевозки, чтобы она стала выгодной (положительной); б) насколько увеличатся общие затраты, если ввести в план перевозку единицы груза в неиспользуемом направлении, не меняя тарифов. Нулевая нормированная стоимость у нулевой перевозки — сигнал наличия альтернативных оптимальных решений.
• В последней строке таблицы — оптимальное значение целевой функции — общие затраты при выполнении предлагаемого плана перевозок (Total Objective Function Value = 3350).

После нахождения решения становится доступным меню Results. С помощью этого меню можно узнать, сколько итераций и времени работы процессора потрачено на поиск решения (Show Run Time and Iteration), a также впоследствии снова вызвать рассмотренный отчет, содержащий ненулевые перевозки (Solution Table - Nonzero Only).

Кроме того, с  помощью команд меню Results можно вывести и другие формы отчета:

• Отчет с перечнем всех перевозках — Solution Table - All. Форма таблицы — та же, что на рис. 3.5, но показаны все перевозки, в том числе и нулевые, для которых нормированные стоимости могут быть положительны.
• Графическое решение — Graphic Solution. Решение выводится в виде сетевой диаграммы.
• Интервалы оптимальности — Range of Optimality. В таблице этого отчета (рис. 6), помимо сведений, присутствующих в обычном отчете, приводится состояние перевозок в столбце Basis Status. Перевозки могут быть либо базисными, то есть положительными (basic), либо небазисными, равными нулю — своей нижней границе (at bound). В столбцах Allowable Min. Cost и Allowable Max. Cost приведены пределы изменения тарифов — границы интервалов оптимальности, внутри которых сохраняется прежнее оптимальное решение (при этом М обозначает ∞). В нашей задаче видно, что у двух небазисных, то есть нулевых, перевозок (из пункта 1 в пункт 4 и из пункта 3 в пункт 2) нормированная стоимость равна нулю. Это говорит о наличии альтернативных оптимальных решений.

Рис. 6. Интервалы оптимальности

 

• Интервалы устойчивости — Range of Feasibility. В этом отчете (рис. 3.7) перечислены узлы, то есть пункты отправления и назначения (Node), запасы грузов (Supply), потребности в них (Demand) и теневые цены (Shadow Price). Теневая цена показывает, насколько сократятся общие затраты на каждую единицу снижения потребностей в одном пункте назначения или увеличения запасов в одном пункте отправления (при неизменности запасов и потребностей в остальных пунктах). Знак минус перед теневыми ценами, соответствующими пунктам отправления, показывает, что при увеличении запасов общие затраты уменьшаются (изменения в противоположных направлениях). С другой стороны, уменьшение потребностей сопровождается уменьшением общих затрат (изменение в одном направлении), поэтому теневые цены, соответствующие пунктам назначения, положительны. Пределы изменения запасов и потребностей, при которых сохраняются прежние теневые цены, — в столбцах Allowable Min. Value и Allowable Max. Value. Это и есть границы интервалов устойчивости.

Рис. 7. Интервалы устойчивости транспортной задачи.

 

Новый отчет  в виде таблицы всегда заменяет предыдущий (старый не сохраняется). Графическое же решение сохраняется и может быть изменено лишь при повторном выборе команды Graphic Solution.

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

Варианты транспортной задачи

При решении  транспортных задач могут встретиться  случаи, отличные от только что рассмотренного:

• Если перевозки груза характеризуются не затратами, а выручкой или прибылью, то транспортная задача решается так же, как в описанном выше примере, но целевая функция максимизируется.
• Если суммарные потребности и запасы груза не совпадают, то программа автоматически вводит фиктивный пункт отправления под именем Unfilled_Demand (Невыполненная заявка) или фиктивный пункт назначения, обозначаемый Unused_Supply (Неизрасходованный запас). При этом затраты на перевозки из фиктивного пункта (или в фиктивный пункт) полагаются равными нулю, а запасы (или потребности) в фиктивном пункте полагаются равными недостающему (или избыточному) количеству груза. Полученная в отчете перевозка из фиктивного пункта отправления (Unfilled_Demand) в реальный пункт назначения трактуется как груз, недопоставленный в этот пункт назначения. А перевозка из реального пункта от правления в фиктивный пункт назначения (Unused_Supply) указывает количество груза, оставшегося невывезенным на этом пункте отправления.

• Если по условию  задачи какая-либо перевозка выполнена  быть не может, то для нее нужно указать неприемлемые затраты на перевозку единицы груза. В качестве таких затрат введите: в задаче на минимум — большое число, значительно превышающее тарифы других перевозок, или латинскую букву М, а в задаче на максимум — наоборот, маленькое число, значительно меньшее остальных (можно даже отрицательное), или латинскую букву М с минусом (-М).

Получение альтернативных решений

Когда получено оптимальное решение, можно получить альтернативные оптимальные решения, с помощью команды Results, Obtain Alternative Solution. Если таких решений нет, эта команда недоступна. Кроме того, сигналом наличия альтернативных решений является нулевая нормированная стоимость у небазисных перевозок (см. рис.6).

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

 

Анализ «Что-если»

После решения  транспортной задачи часто возникает  необходимость выяснить, каким будет решение при других значениях исходных данных: тарифов перевозок, запасов в пунктах отправления или потребностей в пунктах назначения. Можно, конечно, вернуться в окно с исходными данными, изменить их и повторить решение. Но в этом случае пропадают первоначальные данные, а это не всегда желательно. Поэтому лучше воспользоваться анализом «Что-если». Это, фактически, многократное решение задачи с разными наборами данных, но при сохранении исходной задачи.