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

Содержание Содержание 1 Введе ние. 2 1. Задач а линейного программирования. 3 Описа ние ситуации. 3 1.2 Реше ние с помощью пакета WinQSB. 4 Запус к программы 4 Задан ие параметров задачи 4 Ввод ч исловых данных 4 Нахож дение решения 6 Анали з оптимального решения и его чувствительности 7 Получ ение альтернативных решений 9 Парам етрический анализ 9 Решающая функция 11 2. Транс портная задача 13 Приме р 13 2. Решен ие с помощью пакета WinQSB 13 Запус к программы 13 Задан ие параметров задачи 14 Ввод ч исловых данных 14 Нахож дение решения 16 Анали з оптимального решения и его чувствительности 16 Вариа нты транспортной задачи 18 Получ ение альтернативных решений 19 Анали з «Что-если» 19 Парам етрический анализ 20 Решаю щая функция 23 Литер атура: 23 Введение. В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная деятел ьность, заключающаяся в получении наилучших результатов при соответст вующих условиях . Поиски оптимальных решений привели к созданию специальных математичес ких методов и уже в 18 веке были заложены математические основы оптимизац ии (вариационное исчисление, численные методы и др). Однако до второй поло вины 20 века методы оптимизации во многих областях науки и техники примен ялись очень редко, поскольку практическое использование математически х методов оптимизации требовало огромной вычислительной работы, котор ую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно. В настоящее время создано множество программ, предназначе нных для использования при выработке управленческих решений. Исключительно большими в озможностями обладают пакеты прикладных программ WinQSB . Эти пакеты наиболее крупная коллекция запр ограммированных математических методов для решения многих управленче ских задач, а именно: · линейное и целочисленное про граммирование; · сетевое моделирование (тран спортная задача, задачи о назначени ях, о перевозках с промежуточными пу нктами, о кратчайшем пути, о мак симальном потоке, о на хождении минимального основного дерева и задача коммивояжера); · сетевое планирование (метод ы PERT и СРМ); · целевое програ ммирование; · нелинейное про граммирование; · квадратичное п рограммирование; · анализ очереде й (теория массового обслуживания); · имитационное м оделирование систем массового обслуживания; · марковские про цессы; · анализ решений (теория принятия решений и теория игр); · динамическое п рограммирование; · прогнозирован ие и линейная регрессия; · агрегатное пла нирование; · управление зап асами; · планировка и размещение обо рудования; · планирование потребности в материалах, деталях и узлах; · календарное планирование р абот; · выборочный ана лиз качества; · карты контроля качества. Некоторые модули WinQSB объединяют сразу несколько программ , позволяющих решать родственные задачи (например мо дуль сетевого моделирования). Кроме того, пакет WinQSB очень у добен для решения задач оптимизации, поскольку предоставляет широкие в озможности для послеоптимизационного анализа и параметрического прог раммирования. В данной кур совой работе детально рассмотрено использование наиболее доступной в настоящее время первой версии пакета WinQSB находя щая широкое применение в управлении. 1. Задача линейного программиро вания. Описание ситу ации. Требуется определить план выпуска 4 видов мороженного: рожок, брикет , в стаканчике и на пало чке з авод а по производ ству полуфабрикатов глубокой заморозки. На изготовление р асходуются трудовые ресурсы, сырье и финансы. Границы выпуска каждого вида продукции, а так же наличие и нормы рас хода ресурсов, маржинальная прибыль на единицу продукции приведены в та блице 1 : Ресурсы Продукт 1 Продук т 2 Продукт 3 Продукт 4 Наличие Прибыль 80 70 120 150 Труд 2 3 2 3 35 Сырье 8 5 6 5 85 Финансы 6 8 10 9 130 нижн. гр. 1 1 2 3 верхн. гр. 6 - 4 5 Таблица 1. Исходные данные. Необходимо создать производственный план, обеспечив ающий наибольшую прибыль , выполнить параметрический анал из при одновременном изменении нескольких а) коэффициентов, б) правых ча стей ограничений. Обозначив количес тво выпускаемой продукции через x 1 , x 2 , x 3 , x 4 , а целевую функцию (валовую маржинальную прибыль ) – через F , постро им ма тематическую модель задачи: F = 80 x 1 + 70 x 2 + 120 x 3 + 150 x 4 max , Три неравенства – ограничения: 2 x 1 + 3 x 2 + 2 x 3 + 3 x 4 ≤ 35 , 8 x 1 + 5 x 2 + 6 x 3 + 5 x 4 ≤ 85, 6 x 1 + 8 x 2 + 10 x 3 + 9 x 4 ≤ 1 3 0 ; три неравенства – граничные условия: 1 ≤ x 1 ≤ 6 , 1 ≤ x 2 , 2 ≤ x 3 ≤ 4 , 2 ≤ x 4 ≤ 5. 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 ), целые не отрицательные ( Non n egative integer) , двоичные ( Binary ( 0 ,1)) или свободные , то есть произвольного знака (Unsigned/unrestricted). вод числовых дан ных Если выбрана матричная ф орма задачи, откроется окно с таблицей для ввода данных: коэффициентов ц елевой функции и ограничений, правых частей ограничений, а так же выбора их знаков. В строке 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 Cri terion (максимизация меняется на минимизаци ю или наоборот). • Количество ограничений — Insert a Constraint или Delete a Con straint (ограничения добавляются или удаляются). • Количество переменных — Insert a Variable или Delete a Variable (переменные добавляются и ли удаляются). В оспользуемся этими командами, чтобы в нашей задаче ввести рус ские названия переменных и ограничений (рис. 3). С помощью перечисленных далее команд меню Format могут быть и зменены: • Форма задачи — Switch to Normal Model Form или Switch to Ma trix 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 ) (окно д ля задания зна чений откроется после щелчка кнопки ОК ) . Анализ оптимального решения и его чувствительности Сводный отчет, появляющийся после завершения вычислений, со держит наиболее полные сведения о найденном оптимальном реше нии (рис. 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 M in . c ( j ) и Allowable Max . c ( j ) — границы интервалов оптимальности, то есть пределы изменения коэффиц иентов це левой функции, при которых сохраняется прежнее о птимальное решение (М обозначает ∞ ). В нашем пример е такими интервалами будут: для 1-го вида продукции — [ 4 6 .6, 112 ] , для 2-го — [ 5 0, 1 2 0], для 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, то значение целевой функции может измени ться. Предупреждение об этом появится после щелчка кноп ки ОК. Параметрический анализ Параметрический анализ позволяет вы яснить, как изменяется оптимальное значение целевой функции при измене нии ее коэффициентов или правых частей ограничений. При этом предполагают, что изменяемые ве личины зави сят от некоторого параметра (например, времени), и находят, как от этого же параметра зависит оптимальное значение целевой функ ции. Параметрический анализ можно выполнить с помощью команды Per form Parametric Analysis только после нахождения оптимального решения. Она находится в меню Solve and Analyze , когда на экране открыто ок но с исходными данными задачи, или в меню Results , когда на экране - отчет, сводны й или частный, о результатах решения. Эта команда от кр ывает окно для выбора варианта пар аметрического ана лиза . По умолчанию в этом окне выбран параметр Objective Function , предполагающий анализ изменений коэффициентов целевой функции. Ес ли вы хотите проанализировать измен ение одного коэффициента, выбери те в списке справа переменную, к которой он относится. Посл е щелчка кнопки ОК появится таблица с результата ми параметрического анализа. Если же одновременно изменяются несколько коэффициентов, то нужно сделать следу ющее: в списке выбрать пункт Perturbation Vector , щелкнуть кнопку ОК и в открыв шемся окне задать вектор изменения, по казывающий, как изменяется кажды й коэффициент целевой функции. Пусть, например, целевая функция нашей задачи изменяется следую щим образом: F = (8 0+м) x 1 + 7 0 x 2 + (120+2 м ) x 3 + (15 0+3 м ) x 4 , где м — изме няющийся парамет р. Вектор изменения в этом случае — (1,0, 1 , 2 ). Он со стоит из коэффициентов параметра м и задается в окне, показанном на рис. 8 . После щелчка в этом окне кнопки ОК появится таблица с резуль татами параметри ческого анализа. Если изменяются правые части ограничений, нужно выбрать параметр Right Hand Side . Если вас интересует изменение одного огра ничения, выберите в списке с права его название и щелкните кнопку ОК. Если одновременно изменяются не сколько ограничений, то в этом же списке выберите Perturbation Vector и щелкните ОК. В открывшемся ок не з адайте вектор изменения, показывающий, как изменяется правая часть каждого ограничения (в том числе и ограничений сверх у в граничных ус ловиях задачи). В первых трех столбцах полученной таблицы ( Р ис. 9. ) — номера и грани цы интервалов изменения параметра м . (Если бы рассматривалось изменение только одного коэффициента целевой функции или одной правой части ог р аничения, то это были бы интервалы изменения этого коэффициента или этой правой части, а не параметра м .) Интервалы расположены в следую щей последовательности. Сначала перечислены интерва лы с м = 0 до +∞, затем — с м = 0 до -∞ (в таблице бесконечнос ть обозначается словом Infini ty ). В столбцах 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. График решающей функции при изменении правых частей ограничений. Есл и выбран графический метод решения, то построен ное г рафическое изображение можно использовать для анализа чувствительности модели. Чтобы выполнить анализ чувствительности, выберите команду Sensi tivity , Objective Function and Constraints . Появится окно, в котором можно внес ти изменения в любые параметры задачи. 2. Транспортная зад ача Пример На трех лесоводствах в преддверии нового года имею тся елки в количестве 200, 300, 400 ед., который необходимо доста вить на четыре елочных базара в количестве, соответственно 300, 200, 1 50, 2 50 ед. Нужно составить так ой план перевозок, при котором общие затраты минимал ьны. Затраты на перевозку одну елку заданы матрицей, в кот орой номер строки соответствует номеру лесоводства, а номер столбца – н омеру магазина. 6 5 6 5 4 4 7 7 3 6 8 9 Обозначив объем перевозок с i -го лесоводства на j - ый елочных базар через х ( i ) , а це левую функцию (общие затра ты)— через F , построим математическую модель задачи: F = 6* x 11 + 5* x 12 + 6* x 13 +5* x 14 + 4* x 21 + 4* x 22 + 7* x 23 + 7* x 24 + 3* x 31 + 6* x 32 + 8* x 33 + +9* x 34 min x 11 + x 12 + x 13 + x 14 ≤ 200, x 21 + x 22 + x 23 + x 24 ≤ 300, x 31 + x 32 + x 33 + x 34 ≤ 400, x 11 + x 21 + x 31 ≥ 300, x 12 + x 22 + x 32 ≥ 200, x 13 + x 23 + x 33 ≥ 1 50, x 14 + x 24 + x 34 ≥ 2 50, x ij ≥ 0, где i Є [1,3], j Є [1,4]. З наки ≤ в ограничениях означают, что со складов можно вывезти не больше груза, чем там имеется, а знаки ≥ — что в каждый маг азин нужно доставить груза не меньше, чем требуется. Эти знаки справедли вы, когда потребности в сумме не превосходят запасов груза (как в нашей задаче). Если же запасов не хватает д ля удовлетворения всех потребностей, ис пользуются специ альные приемы, позволяющие решить задачу в Excel и там знаки неравенств не задаются и поэтому все варианты транс портной задачи вводятся одинаково. Условие целочисленности переменных в транспортной задаче задавать не нужно. Из-за особенностей алгоритма, решени е автома тически получается целым, если запасы груза в пунктах отправле ния и по требности в пунктах назначения выражаются ц елыми числами. 2. Решение с помощью пакета WinQSB Запуск программы Чтобы запустить программу для сетево го моделирования, позволяю щую, в частности, решать и транспортную задач у, щелкните кнопку Пуск, найдите программную группу WinQSB и выберите Network Modeling . Задание параметров задачи Для ввода новой задачи выберите кома нду File , New Problem . От кроется окно : (рис.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 — потребности в пунктах назначен ия. При ввод е данных, набрав число или знак, следует нажимать клавишу Enter , чтобы п ерейти на следующую позицию ввода. Кроме того, можно в ыполнять следующие действия: · Перемещаться по таб лице — с помощью клавиши Tab или кла в иш со стрелками. • Выбрать ячейку таблицы — щелчком этой ячейки. Если щелкнуть голубое поле над та блицей, то выбранная ячейка выделится цветом и мож но редактировать ее содержимое. С помощью указанных далее команд меню Edit можно из менить сле дующие параметры задачи: • Название задачи — Problem Name. • Название пунктов отправления и назначен ия — Node Names . • Вариант оптимизации целевой функции — Objective Function Cri terion (при этом максимизация меняется на минимизацию и наоборот). • Количество пунктов отправл ения и назначения — Add a Note или Delete a Note (пункт ы добавляются или удаляются, соответственно). По умолчани ю добавляются новые пункты отправления. Для добавления пункта назначения выберите команду Add a Note а затем снимите флажок Added as a source . Здесь же можно задать также название добавляемого пункта. Изменим названия пунктов отправления и назначения, С помощью указанных далее команд меню Format могут быть изме нены: • Форма задачи — Switch to Graphic Model или Switch to Matrix Form (можно перейти в графическую или матр ичную форму, соответст венно). • Формат чисел — Number. • Шрифт и цвет — Font. • Выравнивание — Alignment. • Высота строк — Row Height. • Ширина столбцов — Column Width. Так, например, та же задача в графической форме будет выглядет ь следующим образом После ввода данных задачи не забудьте сохранить ее с помощью команды 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 . Перед н ачалом решения можно выбрать один из восьми предлож енных методов, в частности методы северо-западного угла, минимального элемента, Фогеля и др. Имейте в виду, удачный выбо р мо жет ускорить поиск оптимального решения. Анализ оптимального решения и ег о чувствительности Отчет, появляющийся после завершения вычислений, представляет собой таблицу с перечнем т олько тех направлений, по которым предлага ется пере возить груз, то есть выпол нять ненулевые перевозки (р ис. 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) нормированная стоимость рав на нулю. Это говорит о наличии альтернативных оптимальных решений. • Интервалы устойчивости — Range of Feasibility. В этом отчете (рис. 3.7) перечислены узлы, то есть пункты отправления и назначен ия ( Node ), запасы грузов ( Supply ), потребности в них ( Demand ) и тенев ые цены ( Shadow Price ). Теневая цена показывает, насколько сократятся об щие затраты на к аждую единицу снижения потребностей в одном пункте назначения или увеличения запасов в одном пункте отправления (при не из менности запасов и потребностей в остальных пунктах). Знак минус пе ред теневыми ценами, соответствующими пунктам отправле ния, показыва ет, что при увеличении запасов общие за траты уменьшаются (изменения в противоположных направлениях). С другой с тороны, уменьшение потреб ностей сопровождается уме ньшением общих затрат (изменение в одном направлени и), поэтому теневые цены, соответствующие пунктам назначе ния, положительны. Пределы изменения запасов и потребностей, при ко торых сохраняются прежние теневые цены, — в с толбцах Allowable Min . Value и Allowable Max . Value . Это и е сть границы интервалов устойчиво сти. Новый отчет в виде таблицы всегда заменяет предыдущий (старый не сохраняется). Графическое же решение сохраняетс я и может быть изменено лишь при повторном выборе команды Graphic Solution . Просмотрев отчеты, вы можете с помощью меню Window вернут ься в окно с исходными данными. Данные можно изменить и решение повто рить, получив при этом новый табличны й отчет. Варианты транспортной задачи При решении транспортных задач могу т встретиться случаи, отлич ные от только что рассмот ренного: • Если перевозки груза характериз уются не затратами, а выручкой или прибылью, то трансп ортная задача решается так же, как в описанном выше пр имере, но целевая функция максимизируется. • Если суммарные потребности и запасы груза не совпадают, то про грамма автоматичес ки вводит фиктивный пункт отправления под именем Unfilled _ Demand (Невыполненная заявка) или фиктивный пункт наз наче ния, обозначаемый Unused _ Supply (Неизрасходован ный запас). При этом затраты на перевозки из фиктивного пункта (или в фикти вный пункт) по лагаются равными нулю, а запасы (или пот ребности) в фиктивном пункте полагаются равными нед остающему (или избыточному) количеству груза. Получе нная в отчете перевозка из фиктивного пункта отправления ( Un filled _ Demand ) в реальный пункт назначения трактуе тся как груз, недопо ставленный в этот пункт назначения. А перевозка из ре ального пункта от правления в фиктивный пункт назначения ( Unused _ Supply ) указывает ко личество груза, оставшегося невывезенным на этом пункте отправления. • Если п о условию задачи какая-либо перевозка выполнена быть не может, то для нее нужно указать неприемлемые затраты на перев озку еди ницы груза. В качестве таких затрат введите: в задаче на минимум — боль шое число, значительно превышающее тарифы др угих перевозок, или ла тинскую букву М, а в задаче на ма ксимум — наоборот, маленькое число, значительно мен ьшее остальных (можно даже отрицательное), или латин скую букву М с минусом (-М). Получение альтернативных ре шений Когда получено оптимальное решение, можно получить альтернатив ные оптимальные решения , с помощью команды Results , Obtain Alterna tive Solution . Если та ких решений нет, эта команда недоступна. Кроме то го, с игналом наличия альтернативных решений является нулевая нормиро ванная стоимость у небазисных перевозок (см. рис.6). При каждо м выборе этой команды появляется табличный отчет с но вым альтернативны м оптимальным решением. Решения меняются цикли ческ и: после их полного просмотра цикл повторяется. Вид отчета (с нуле выми пе ревозками или без них) зависит от того, какой отчет открывался последним, перед обращением к данной команде. Анализ «Что-если» После решения транспортной задачи ча сто возникает необходимость выяснить, каким будет решение при других зн ачениях исходных данных: тарифов перевозок, запасов в пунктах отправления или потребностей в пунктах наз начения. Можно, конечно, вернуться в окно с исходными дан ными, изменить и х и повторить решение. Но в этом случае пропадают пер воначальные данные, а это не всегда желательно. Поэтому лучше восполь зов аться анализом «Что-если». Это, фактически, многократное решение задачи с разными наборами данных, но при сохранении исходной задачи. Анализ «Ч то-если» можно выполнить с помощью команды Perform What If Analysis то лько после нахождения оптимального решения. Эту кома нду выберите либо в меню Solve and Analyze , либ о в меню Results . Откроется окно для задания исходных данных анализа (рис. 8). Рис. 8. Анализ что-ес ли. По умолча нию в поле Analysis on выбра н параметр Link ( Arc ) Coeffi cient ( Cost / Distance ), предполагающий анал из изменений тарифов пере возок. Если вы хотите проан ализировать изменение одного тарифа, выбе рите в списке справа соответствующее направление перевозки и затем вве дите новый тариф в поле Link Cost / Distance . После щ елчка кнопки ОК появится таблица отчета о решении за дачи с новым значением введенного параметра. Вид отчет а (с нулевыми перевозками или без них) зависит от того, ка кой отчет открыв ался последним, перед выполнением анализа «Что-если». Если нужн о проанализировать одновременное изменение неско льких тарифов, то щелкните кнопку Vector (в право м нижнем углу) и в появив шемся окне задайте новое значение каждого тариф а. После щелч ка в этом и предыдущем окнах кнопки ОК появится таб лица с отчетом о новом решении. Если нужно проанализировать изменение запасов или потребностей в одном из пункто в отправления или назначения, то проделайте следующее. В поле Analysis on в ыберите параметр Node Value ( Supply / Demand ) (см. рис. 8), после этого в списк е справа выберите название пункта, а за тем в поле Link Cost / Distance введит е новое значение изменяемого пара метра. После щелчка кно пки ОК появится отчет о новом решении. Од новременное изменение запасов или потребностей в нескольких пунктах в рассматриваемой версии программы исследовать не уд ается. Параметрический анализ Параметрический анализ позволяет вы яснить, как изменяется опти мальное значение целевой функции (общие зат раты) при изменении тари фов перевозок или запасов и п отребностей в пунктах отправления и назна чения. При этом предполагают, что изменяемые величины линейно зависят от некоторо го изменяемого параметра (например времени), и находят, как от этого же пар аметра зависят общие затраты. Параметрически й анализ можно выполнить с помощью команды Perform Parametric Analysis только после нахождения оптимального ре шения. Эта команду можно выбрать либо в меню Solve and Analyze , либо в меню Results . Она открывает окн о для выбора варианта параметриче ского анализа (рис . 9). По умолчан ию в этом окне выбран параметр Link ( Arc ) Coefficient ( Cost / Distance ), предпо лагающий анализ изменений тарифов. Если вы хо тите пр оанализировать изменение тарифа одной перевозки (например из пункта 1 в пункт 4) выбер ите в списке справа направление этой перевозки. Зате м укажите, в каких пределах изменяется выбранный тариф. Рис. 9. Выбор вари анта параметрического анализа. Например, в нашей задаче исходное значение тарифа ра вно 6. Пусть нас интересует его изменение в пределах от 3 до 10 с шагом 2. Представим изменяемое значение тарифа в вид е 6 + и, где и — изменяющийся пара метр. Тогда начальное значение эт ого параметра будет -3, конечное равно 4, а шаг равен 2. Именно их и нужно задат ь, соответственно, в полях Star ing u , Ending u и Step of u (см. рис. ЗЛО). После щелчка кноп ки ОК поя вится таблица с результатами параметричес кого анализа (рис.10). Рис. 10. Результаты параметрического анализа при изменении т арифа одной перевозки. В этой табл ице с заданным шагом представлены значения тарифа в указанном интервал е и соответствующие общие затраты — оптимальные значени я целевой функции ( OBJ Value ). Точно так же выполняется параметрический анализ изменения запа сов или потребностей в одном пункте отправления или назначения. В этом случ ае выбирают параметр Node Value ( Supply / Demand ) (см. рис. 9) и в списке справа — название пункта. Затем для параме тра и вводят началь ное и конечн ое значения, а также шаг изменения. (Значения этого изме няющегося параметра добавляются к исходной величине запасов или по требностей.) И наконец, после щелчка кнопки ОК, м ожно увидеть резуль таты параметрического анализа. Если одно временно изменяются тарифы нескольких перевозок или за пасы и потребности в неско льких пунктах, то после выбора варианта пара метрического анализа (тарифы или запасы/потребности) нужн о щелкнуть кнопку Vector . После чего в открывшемся окне за дать вектор изменения, показывающий, как изменяются все тарифы или все запасы и потребности. Пусть, напр имер, в нашей задаче запасы и потребности следующим о бразом зависят от изменяющегося параметра и. Начальный запас (потребно сть) Изменяемый запас (потребн ость) Пункт отправления (назначения) П. отпр. 1 100 100 + 3 и П.отпр.З 400 400 - 2 и П.назн.4 250 250 + и Положим, нас интересует измен ение этого параметра в интервале от 15 до 35 с шагом 5. Вект ор изменения запасов (потребностей) в данном случае б удет содержать три ненулевых компонента: 3, -2 и 1 (коэффици енты параметра и). Для выпол нения параметрического анализа сначала выберем параметр Node Value ( Supply / Demand ) и зададим пределы и шаг изменения пара метра и (рис.11). Рис. 11.Выбор варианта парам етрического анализа (изменение запасов и потребностей). Затем щел кнем кнопку Vector и введем ненулевые компоненты векто ра изменения запасов и потребностей (рис.12). Рис . 12. Задание вектора изменения запасов и потребностей. После щелч ков в этом и предыдущем окнах кнопки ОК появится таб лица с результатами параметрического анализа, в которой для каждого знач ения параметра и указаны общие з атраты — оптимальное значение це левой функции ( OBJ Value ) В дальнейш ем можно вернуться к таблице с результатами параметри че ского анализа. Для этого выберите команду Results , Show Parametric Analysis , Table . Решающая функция Результаты предварительно выполнен ного параметрического анализа можно представить в г рафической форме, воспользовавшись командой Results > Show Parametric Analysis - Graphic . При этом выводится гра фик решающей функции, п оказывающий зависимость целевой функции (общих затрат) от параметра и . Результаты параметрическ ого анализа представлены графически на рис. 13. Литература: 1. А.Л. Кутузов - Учебное пособие «Математические методы и модели исследова ния операций» Изд-во СПбГПУ 2005г.