Задачи линейного параметрического программирования

Введение. В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

В настоящее время создано множество программ, предназначенных для использования при выработке управленческих решений.Исключительно большими возможностями обладают пакеты прикладных программ WinQSB. Эти пакеты наиболее крупная коллекция запрограммированных математических методов для решения многих управленческих задач, а именно: • линейное и целочисленное программирование; • сетевое моделирование (транспортная задача, задачи о назначени¬ях, о перевозках с промежуточными пунктами, о кратчайшем пути, о мак¬симальном потоке, о нахождении минимального основного дерева и задача коммивояжера); • сетевое планирование (методы PERT и СРМ); • целевое программирование; • нелинейное программирование; • квадратичное программирование; • анализ очередей (теория массового обслуживания); • имитационное моделирование систем массового обслуживания; • марковские процессы; • анализ решений (теория принятия решений и теория игр); • динамическое программирование; • прогнозирование и линейная регрессия; • агрегатное планирование; • управление запасами; • планировка и размещение оборудования; • планирование потребности в материалах, деталях и узлах; • календарное планирование работ; • выборочный анализ качества; • карты контроля качества. Некоторые модули WinQSB объединяют сразу несколько программ, позволяющих решать родственные задачи (например модуль сетевого моделирования). Кроме того, пакет WinQSB очень удобен для решения задач оптимизации, поскольку предоставляет широкие возможности для послеоптимизационного анализа и параметрического программирования.

В данной курсовой работе детально рассмотрено использование наиболее доступной в настоящее время первой версии пакета WinQSB находящая широкое применение в управлении. 1. Задача линейного программирования. Описание ситуации.

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

На изготовление расходуются трудовые ресурсы, сырье и финансы. Границы выпуска каждого вида продукции, а так же наличие и нормы расхода ресурсов, маржинальная прибыль на единицу продукции приведены в таблице 1: Ресурсы Продукт 1 Продукт 2 Продукт 3 Продукт 4 Наличие Прибыль 150 Труд 35 Сырье 85 Финансы 6 8 10 9 130 нижн. гр. 1 1 2 3 верхн. гр. 6 - 5 Таблица 1. Исходные данные. Необходимо создать производственный план, обеспечивающий наибольшую прибыль, выполнить параметрический анализ при одновременном изменении нескольких а) коэффициентов, б) правых частей ограничений.

Обозначив количество выпускаемой продукции через x1, x2, x3, x4, а целевую функцию (валовую маржинальную прибыль) – через F, построим математическую модель задачи: F = 80x1 + 70x2 + 120x3 + 150x4 max, Три неравенства – ограничения: 2 x1 + 3 x2 + 2 x3 + 3 x4 ≤ 35, 8 x1 + 5 x2 + 6 x3 + 5 x4 ≤ 85, 6 x1 + 8 x2 + 10 x3 + 9 x4 ≤ 130; три неравенства – граничные условия: 1 ≤ x1 ≤ 6, 1 ≤ x2, 2 ≤ x3 ≤ 4, 2 ≤ x4 ≤ 1.2 Решение с помощью пакета WinQSB. Запуск программы Чтобы запустить программу для решения задачи линейного и целочисленного программирования, необходимо в главном меню (Пуск) выбрать программную группу WinQSB и выберите в ней программу Liner and Integer Programming.

Задание параметров задачи Для ввода новой задачи нужно выбрать команду File, затем New Problem.

В открывшемся окне задается: В поле Problem Title – название задачи, в поле Number of Variables – количество переменных, в поле Number of Constrains – количество ограничений, в поле Maximization/Minimization – вариант оптимизации, Data Entry Format – форма задачи матричная (Spreadsheet Matrix Form) или стандартная (Normal Model Form) тип переменных – непрерывные неотрицательные (Nonnegative integer), целые неотрицательные (Nonnegative integer), двоичные (Binary (0,1)) или свободные, то есть произвольного знака (Unsigned/unrestricted). Рис. 1. Ввод параметров решения задачи линейного программирования.

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

Рис. 2.Задание коэффициентов целевой функции и ограничений В строке Variable — установленные по умолчанию имена переменных. В строке Maximize (или Minimize) вводятся коэффициенты целевой функции.

Обозначения С1, С2, СЗ и т. д. — это установленные по умолчанию названия ограничений.В соответствующих строках вводятся коэффициенты этих ограничений, за которыми следуют их знаки (в столбце Direction) и правые части (в столбце R. H. S.). Ниже — две строки для задания граничных условий: LowerBound и UpperBound. В первой из них вводятся нижние границы переменных, а во второй — верхние. По умолчанию все нижние границы равны 0, а все верхние равны бесконечности, которая обозначается большой латинской буквой М. В строке Variable Туре указан заданный вами тип переменных: Continuous (Непрерывная), Integer (Целая), Binary (Двоичная) или Unrestricted (Свободная). Примечание: при вводе чисел, имеющих дробную часть, используйте в качестве разделителя целой и дробной части точку, а не запятую. При вводе данных, набрав число или знак, следует нажать клавишу Enter, чтобы перейти на следующую позицию ввода.

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

При этом выбранная ячейка выделится цветом и можно редактировать ее содержимое. • Изменить знак ограничения — двойным щелчком знака.

Если двойной щелчок выполнить несколько раз, знаки будут меняться циклически (=, =). • Изменить тип переменной — двойным щелчком слова, обозначающего тип этой переменной в строке Variable Type. При нескольких двойных щелчках названия типов будут меняться циклически (Continuous, Integer, Binary, Unrestricted). С помощью указанных далее команд меню Edit можно изменить следующие параметры задачи: • Название задачи — Problem Name. • Имена переменных — Variable Names. • Названия ограничений — Constraint Names. • Вариант оптимизации целевой функции — Objective Function Criterion (максимизация меняется на минимизацию или наоборот). • Количество ограничений — Insert a Constraint или Delete a Constraint (ограничения добавляются или удаляются). • Количество переменных — Insert a Variable или Delete a Variable (переменные добавляются или удаляются). Воспользуемся этими командами, чтобы в нашей задаче ввести русские названия переменных и ограничений (рис. 3). Рис. 3 Изменение названия переменных и ограничений. С помощью перечисленных далее команд меню Format могут быть изменены: • Форма задачи — Switch to Normal Model Form или Switch to Matrix Form (перейти в стандартную или матричную форму). Выбрав любую форму задачи, вы можете построить задачу, двойственную к ней, с помощью команды Switch to Dual Form. • Формат чисел— Number. • Шрифт и цвет — Font. • Выравнивание—Alignment. • Высота строк — Row Height. • Ширина столбцов — Column Width. Чтобы сохранить данные воспользуйтесь командой File, Save Problem As. Нахождение решения Чтобы решить задачу, выберите в меню Solve and Analyze один из следующих вариантов действий: • Решить задачу — Solve the Problem.

При этом задача решается симплексным методом, если все переменные определены вами как непрерывные, или методом ветвей и границ, если хотя бы одна из них определена как целая или двоичная.

По окончании решения появится сообщение о том, что задача решена (The problem is solved.) и либо получено оптимальное решение (Optimal solution is achieved.), либо допустимых решений нет (However, the problem is infeasible!), либо целевая функция не ограничена (However, the problem is unbounded!). Щелкнув кнопку OK в окне с этим сообщением, вы увидите сводный отчет о решении, или анализ недопустимости (если нет допустимых решений), или анализ неограниченности (если не ограничена целевая функция). В дальнейшем можно открывать сводный отчет либо посредством меню Window, либо с помощью команды Results > Combined Report. • Решить с показом шагов — Solve and Display Steps. В этом случае показываются все итерации решения.

Если все переменные определены как непрерывные, задача решается симплексным методом и отображаются симплекс-таблицы с указанием переменных, вводимых в базис и исключаемых из него. С помощью меню Simplex Iteration вы можете сами выбрать переменную, вводимую в базис (Choose Entering Variable), a также перейти к следующей итерации (Next Iteration), к последней итерации (Go to the Last Tableau) или к концу решения с выводом сводного отчета (Nonstop to Finish). В дальнейшем можно открывать таблицу с последней итерацией либо посредством меню Window, либо с помощью команды Results, Final Simplex Tableau.

Решить графическим методом — Graphic Method.

При выборе этой команды откроется окно (рис.4), в котором нужно указать, какая переменная будет отображаться на горизонтальной оси (X), а какая — на вертикальной (У) Если в задаче более двух переменных, вам будет предложено положить остальные переменные равными их значению в оптимальном решении (Set to optimal), или нулю (Set to zero) или тем значениям, которые вы сами зададите (Assign variables) (окно для задания значений откроется после щелчка кнопки ОК). Рис. 4 Задание данных для графического метода решения Анализ оптимального решения и его чувствительности Рис. 5. Сводный отчет о решении задачи линейного программирования. Сводный отчет, появляющийся после завершения вычислений, содержит наиболее полные сведения о найденном оптимальном решении (рис. 5) Кроме того, вы найдете в этом отчете информацию, необходимую для выполнения анализа чувствительности.

Этот анализ позволяет выяснить, как изменения коэффициентов целевой функции и правых частей ограничений могут повлиять на найденное оптимальное решение.

При этом, однако, предполагается, что изменяется только один коэффициент целевой функции или правая часть только одного ограничения.

Сведений о том, что произойдет при одновременном изменении нескольких входных данных задачи, сводный отчет не дает. Сводный отчет состоит из двух таблиц.

В первой таблице выводится следующая информация, касающаяся переменных: • В первых двух столбцах — номера и имена переменных. • В столбце Solution Value — найденное решение (в нашем случае 3,4; 1,7; 4, 5) — оптимальный план выпуска продукции. • В столбце Unit Cost or Profit c(j) — удельные затраты или удельная маржинальная прибыль, являющиеся коэффициентами целевой функции. • В столбце Total Contribution — итоговый вклад в оптимальное значение целевой функции, определяемый каждой переменной (произведение коэффициента целевой функции на оптимальное значение этой переменной). В нашем примере — это маржинальная прибыль от продажи каждого продукта. В столбце Reduced Cost— нормированные стоимости — двойственные оценки (в нашем случае — 0, 0, 0, 0). Такая оценка может быть отлична от нуля только для переменной, имеющей в оптимальном плане нулевое значение, и показывает, на какую величину следует изменить коэффициент этой переменной в целевой функции, чтобы ее значение стало положительным (например, насколько увеличить цену изделия, чтобы его производить стало выгодно). Кроме того, эта оценка показывает, на какую величину ухудшится значение целевой функции, если уйти от оптимального плана (нулевого значения переменной), добавив в него единицу соответствующей продукции. • В столбце Basis Status — состояние переменных в последней симплекс-таблице: они могут быть либо базисными (basic), либо небазисными и равными своей нижней границе (at bound). (Нижняя граница переменных задана в строке LowerBound матричной формы задачи.) • В столбцах Allowable Min. c(j) и Allowable Max. c(j) — границы интервалов оптимальности, то есть пределы изменения коэффициентов целевой функции, при которых сохраняется прежнее оптимальное решение (М обозначает ∞). В нашем примере такими интервалами будут: для 1-го вида продукции — [46.6, 112], для 2-го — [50, 120], для 3-го — [65,7, +∞) и для 4-го — [70, +∞). • В последней строке таблицы — оптимальное значение целевой функции (в нашей задаче — Objective Function (Max.) = 1 624.2860). Вторая таблица сводного отчета содержит следующие сведения об ограничениях задачи: • В первых двух столбцах — номера и названия ограничений. • В столбце Left Hand Side — левые части ограничений, вычисленные при оптимальных значениях переменных.

В нашей задаче — это количество ресурсов, которое будет израсходовано при оптимальном выпуске продукции. • В столбце Direction — знаки ограничений. • В столбце Right Hand Side — правые части ограничений. • В столбце Slack or Surplus — остатки или избытки, вычисленные по правилу: «правая часть минус левая» для ограничений типа =. Они могут показывать, например, величину неиспользованного ресурса (для лимитирующих ограничений, то есть ограничений сверху) или превышение требуемого уровня (для ограничений-требований, то есть ограничений снизу). Если остаток или избыток равен нулю, то соответствующее ограничение является связанным (активным), а соответствующий ресурс — дефицитным (используемым полностью). В противном случае ограничение несвязанное, а ресурс недефицитен.

В нашей задаче связанным является первое ограничение, а дефицитны трудовые ресурсы. • В столбце Shadow Price — теневые цены — двойственные оценки, показывающие, на какую величину изменится оптимальное значение целевой функции при увеличении на единицу правой части соответствующего ограничения, тогда как остальные данные неизменны (например при добавлении единицы соответствующего ресурса). Кроме того, теневая цена — это максимальная цена, которую стоит платить за дополнительное количество дефицитного ресурса, чтобы приобретение было выгодным, или минимальная цена его продажи.

Теневая цена отлична от нуля только для связанных ограничений. • В столбцах Allowable Min. RHS и Allowable Max. RHS — границы интервалов устойчивости, то есть пределы изменения правых частей ограничений (запасов ресурсов), при которых неизменны соответствующие теневые цены и в оптимальном решении сохраняется прежний набор ненулевых переменных (ассортимент продукции). В нашем примере интервалами устойчивости будут: для трудовых ресурсов— [33.7, 39.4], для сырья — [73.6, +∞) и для финансов — [120.2, +∞). После нахождения решения становится доступным меню Results.

С его помощью можно узнать, сколько итераций и времени работы процессора потрачено на поиск решения (Show Run Time and Iteration), а также впоследствии снова вызвать сводный отчет (Combined Report). Хотя сводный отчет полностью содержит все сведения о результатах решения и их чувствительности, можно получить и несколько более мелких, частных отчетов, которые выводятся с помощью команд меню Results: • Отчет по результатам — Solution Summary.

Показывает оптимальные значения переменных и их итоговый вклад в оптимальное значение целевой функции, нормированные стоимости, а также состояние переменных: входят они в окончательный базис или нет. • Отчет по ограничениям — Constraint Summary.

Отображает левые и правые части ограничений, остатки или избытки, а также теневые цены. • Анализ чувствительности при изменении коэффициентов целевой функции — Sensitivity Analysis for OBJ. Показывает нормированные стоимости, а также пределы изменения коэффициентов целевой функции, определяющее интервалы оптимальности, внутри которых сохраняется прежнее оптимальное решение. • Анализ чувствительности при изменении правых частей ограничений — Sensitivity Analysis for RHS. Отображает теневые цены, а также пределы изменения правых частей ограничений, определяющие интервалы устойчивости, внутри которых сохраняется прежний базис решения и прежние теневые цены. Новый выбранный отчет всегда заменяет предыдущий (старый не сохраняется). Просмотрев сводный или частные отчеты, вы можете с помощью меню Window вернуться в окно с исходными данными.

Данные можно изменить и решение повторить, получив при этом новый отчет.

Получение альтернативных решений Когда получено оптимальное решение задачи и на экране — окно с ее исходными данными, можно получить альтернативные решения с помощью команды Solve and Analyze, Alternative Solution.

Она открывает окно, содержащее два списка: в левом — текущий базис, а в правом — небазисные переменные вместе с двойственными оценками Cj-Zj, указанными в скобках.

В правом списке нужно выбрать переменную, которую следует ввести в базис.

После щелчка кнопки ОК программа автоматически выберет переменную, исключаемую из базиса, и найдет новое решение.

Если вы выбрали небазисную переменную с Cj-Zj = 0, то значение целевой функции не изменится, то есть будет найдено альтернативное оптимальное решение.

Если же вы выбрали переменную с Cj-Zj ≠ 0, то значение целевой функции может измениться. Предупреждение об этом появится после щелчка кнопки ОК. Рис. 6 Получение альтернативных решений.

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

Параметрический анализ можно выполнить с помощью команды Perform Parametric Analysis только после нахождения оптимального решения. Она находится в меню Solve and Analyze, когда на экране открыто окно с исходными данными задачи, или в меню Results, когда на экране - отчет, сводный или частный, о результатах решения.Эта команда открывает окно для выбора варианта параметрического анализа. Рис. 7. Выбор варианта параметрического анализа.

По умолчанию в этом окне выбран параметр Objective Function, предполагающий анализ изменений коэффициентов целевой функции. Ес¬ли вы хотите проанализировать изменение одного коэффициента, выбери¬те в списке справа переменную, к которой он относится. После щелчка кнопки ОК появится таблица с результатами параметрического анализа.Если же одновременно изменяются несколько коэффициентов, то нужно сделать следующее: в списке выбрать пункт Perturbation Vector, щелкнуть кнопку ОК и в открывшемся окне задать вектор изменения, по¬казывающий, как изменяется каждый коэффициент целевой функции.

Рис. 8. Задание вектора изменения правых частей ограничений Пусть, например, целевая функция нашей задачи изменяется следую¬щим образом: F = (80+μ)x1 + 70x2 + (120+2μ)x3 + (150+3μ)x4, где μ — изме¬няющийся параметр. Вектор изменения в этом случае — (1,0, 1, 2). Он со¬стоит из коэффициентов параметра μ и задается в окне, показанном на рис. 8. После щелчка в этом окне кнопки ОК появится таблица с резуль¬татами параметрического анализа.

Если изменяются правые части ограничений, нужно выбрать параметр Right Hand Side. Если вас интересует изменение одного огра¬ничения, выберите в списке справа его название и щелкните кнопку ОК. Если одновременно изменяются несколько ограничений, то в этом же списке выберите Perturbation Vector и щелкните ОК. В открывшемся ок¬не задайте вектор изменения, показывающий, как изменяется правая часть каждого ограничения (в том числе и ограничений сверху в граничных ус¬ловиях задачи). Рис. 9. Результаты параметрического анализа при изменении правых частей ограничений В первых трех столбцах полученной таблицы (Рис. 9.)— номера и границы интервалов изменения параметра μ. (Если бы рассматривалось изменение только одного коэффициента целевой функции или одной правой части ог¬раничения, то это были бы интервалы изменения этого коэффициента или этой правой части, а не параметра μ.) Интервалы расположены в следую¬щей последовательности.

Сначала перечислены интервалы с μ = 0 до +∞, затем — с μ = 0 до -∞ (в таблице бесконечность обозначается словом Infinity). В столбцах From OBJ Value и То OBJ Value — значения целевой функции на границах интервалов изменения параметра μ. В столбце Slope — угловой коэффициент целевой функции.

Наконец, в последних столбцах Leaving Variable и Entering Variable — имена переменных, которые ис¬ключаются из базиса и вводятся в него при переходе к следующему по по¬рядку интервалу изменения параметра μ. В последних двух столбцах используются следующие обозначения. Буквы UB, добавляемые к именам переменных, обозначают ограничения сверху значений этих переменных, а слова Slack или Surplus перед назва¬ниями ограничений — дополнительные переменные, остаточные или из¬быточные, используемые в симплексном методе для превращения ограни¬чений-неравенств в равенства.

Если в столбце Leaving Variable указана переменная, а в столбце En¬tering Variable — нет, данный интервал изменения параметра μ является последним, в котором имеется решение, а в следующем — решение отсут¬ствует.

Интервалы без допустимых решений обозначаются в столбце From OBJ Value словом Infeasible.К результатам параметрического анализа можно возвращаться из дру¬гих окон WinQSB посредством меню Window или с помощью команды Results, Show Parametric Analysis меню. Решающая функция Результаты предварительно выполненного параметрического анализа можно представить в графической форме. Для этого воспользуйтесь ко¬мандой Results, Graphic Parametric Analysis.

При этом выводится гра¬фик решающей функции, показывающий зависимость целевой функции от параметра μ (Если изменяется только один коэффициент целевой функции или одна правая часть ограничения, то показывается зависимость именно от этого коэффициента или этой правой части). Рассмотренные ранее результаты параметрического анализа представлены графически: Рис. 10. График решающей функции при изменении правых частей ограничений.

Графический анализ чувствительности Рис. 10. График решающей функции при изменении правых частей ограничений. Если выбран графический метод решения, то построен¬ное графическое изображение можно использовать для анализа чувствительности модели. Чтобы выполнить анализ чувствительности, выберите команду Sensi¬tivity, Objective Function and Constraints.Появится окно, в котором можно внести изменения в любые параметры задачи.

Рис. 11. Графическое решение. 2. Транспортная задача Пример На трех лесоводствах в преддверии нового года имеются елки в количестве 200, 300, 400 ед который необходимо доставить на четыре елочных базара в количестве, соответственно 300, 200, 150, 250 ед. Нужно составить такой план перевозок, при котором общие затраты минимальны.Затраты на перевозку одну елку заданы матрицей, в которой номер строки соответствует номеру лесоводства, а номер столбца – номеру магазина. 6 5 6 5 4 4 7 7 3 6 8 9 Обозначив объем перевозок с i-го лесоводства на j-ый елочных базар через х(i), а це¬левую функцию (общие затраты)— через F, построим математическую модель задачи: F= 6* x11 + 5* x12 + 6* x13 +5* x14+ 4* x21 + 4* x22 + 7* x23 + 7* x24 + 3* x31 + 6* x32 + 8* x33 + +9* x34 min x11 + x12 + x13 + x14 ≤ 200, x21 + x22 + x23 + x24 ≤ 300, x31 + x32 + x33 + x34 ≤ 400, x11 + x21 + x31 ≥ 300, x12 + x22 + x32 ≥ 200, x13 + x23 + x33 ≥ 150, x14 + x24 + x34 ≥ 250, xij ≥ 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 Cri¬terion (при этом максимизация меняется на минимизацию и наоборот). • Количество пунктов отправления и назначения — 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 Ini¬tial Solution Method.

Перед началом решения можно выбрать один из восьми предложенных методов, в частности методы северо-западного угла, минимального элемента, Фогеля и др.