2015-08-21
1224
Воспользуемся той же программой Linear and Integer Programming, которую использовали в разделе 1.2 для решения задачи линейного программирования. Для ввода новой задачи следует выбрать команду File > New Problem и действовать далее, как было описано в разделе 1.2. Однако теперь при задании парамегров (см. рис. 1.1) следует выбрать общий для всех переменных тип — целые неотрицательные (Nonnegative integer):
Если ранее, решая задачу линейного программирования, вы сохранили ее на диске, то теперь можете просто загрузить. Понадобится лишь двойным щелчком изменить тип каждой переменной в строке Variable Туре (см. рис. 1.3). В результате непрерывный тип (Continuous) заменится целочисленным (Integer). Таким же образом можно задавать условия и частичной це- лочисленности, когда целыми должны быть не все, а только часть переменных.
После выбора команды Solve and Analyze ► Solve the Problem появится сводный отчет (рис. 2.1) с целочисленным оптимальным решением.
| л Combined Report for Производственный план | I | X | ||||||
| 21:02:33 | Friday | August | ||||||
| Decision | Solution | Unit Cost or | Total | Reduced | Basis | |||
| Variable | Value | Profit c(j) | Contribution | Cost | Status | |||
| Г | Прод1 | 5,0000 | 70,0000 | 350,0000 | basic | |||
| ¥ | Прод2 | 1,0000 | 60,0000 | 60,0000 | 60,0000 | at bound | ||
| ПродЗ | 3,0000 | 110,0000 | 330,0000 | basic | ||||
| Прод4 | 4,0000 | 140,0000 | 560,0000 | basic | ||||
| Objective | Function | (Max.) = | 1 300,0000 | |||||
| Left Hand | Right Hand | Slack | Shadow | |||||
| Constraint | Side | Direction | Side | or Surplus | Price | |||
| Т | Труд | 18,0000 | <= | 19,0000 | 1,0000 | |||
| Сырье | 70,0000 | <= | 80,0000 | 10,0000 | ||||
| Финансы | 91,0000 | <= | 100,0000 | 9,0000 | ||||
Рис. 2.1. Сводный отчет о целочисленном решении задачи линейного программирования
Этот отчет отличается от отчета обычной задачи линейного программирования лишь отсутствием последних двух столбцов, предназначенных для показа допустимых изменении коэффициентов целевой функции и правых частей ограничений.
Как и в обычной задаче линейного программирования, кроме сводного отчета, можно с помощью команд меню Results получить еще и частные отчеты: по решению (Solution Summary) и по ограничениям (Constraint Summary). Также можно решить задачу с показом шагов, выбрав команду Solve and Analyze ► Solve and Display Steps. При этом показываются все итерации, получаемые методом ветвей и границ. Просматривая их, вы можете с помощью меню Brand-And-Bound Iteration перейти к следующей итерации (Next Iteration), к концу решения с выводом сводного отчета (Nonstop to Finish) или посмотреть текущую информацию (Show Node Information). Эта информация — о количестве активных узлов, текущем значении целевой функции и нижней или верхней границе, обозначаемых, соответственно, ZL и ZU.
Поскольку нахождение целочисленного решения зачастую является довольно длительной процедурой, в WinQSB предусмотрена возможность ее ускорения. Для этого используются команды, позволяющие изменить следующие параметры:
1.94. Допустимая погрешность в определении оптимальных значений переменных — Change Integer Tolerance. Для ускорения можно увеличить принятое по умолчанию значение 0,01.
1.95. Допустимое отклонение полученного значения целевой функции от оптимального — Specify Solution Quality. Для ускорения можно увеличить принятое по умолчанию значение 0%.
1.96. Приоритеты выбора переменных для ветвления — Specify Variable Branching Priorities. Для ускорения можно менять приоритеты, которые по умолчанию одинаковы и равны 0.
Указанные параметры можно изменить либо перед началом решения (выбрав соответствующие команды в меню Solve and Analyze), либо в ходе решения с показом шагов (выбрав те же команды в меню Brand-And-Bound Iteration).
