П.2.3. Решение задач целочисленного программирования

Порядок решения задач ЦП с помощью QSB рассмотрим на примере.
Подготовьте ЭММ задачи для решения на ЭВМ, исключив условия неотрицательности переменных:

В нашей задаче: ЦФ на максимум, 10 переменных и 9 ограничений.
Выберите опцию 2 – Целочисленное программирование в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.
В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim2 ), ответьте на вопросы о задаче. Варианты ответов: ЦФ на максимум, 10 переменных и 9 ограничений, будем переименовывать переменные, т.е. при ответе на последний вопрос введите символ N . По окончании нажмите клавишу Spacebar . На экране появится шаблон для ввода новых имён переменных (вместо заданных Х1, Х2,...,Хп).
Переименуйте переменные, как показано ниже:
1: <x1> 2:<x2> 3:<x3> 4:<d21> 5:<d22>
6:<d23> 7:<d24> 8:<d31> 9:<d32> 10:<d33>
Переход к следующей позиции осуществляется нажатием Enter , обратный переход – клавишей Backspace . Если при вводе не было ошибок, то по окончании нажмите клавишу Spacebar ; для корректировки введённой информации – любую другую клавишу.
На экране появится ряд дополнительных вопросов о задаче, на которые нужно ответить ( Y - да, или N - нет):
Все переменные целые (Y/N)? y
значения всех переменных 0-1 (Y/N)? n
Вы будете задавать граничные условия (Y/N)? у
Заполните появившийся шаблон для ввода целочисленных переменных и границ их изменения:

Номер










Имя
x1
x2
x3
d21
d22
d23
d24
d31
d32
d33
Целочислен. (I/C)
<I>
<I>
<I>
<I>
<I>
<I>
<I>
<I>
<I>
<I>
Нижн. гран.
<0 >
<0 >
<0 >
<0 >
<0 >
<0 >
<0 >
<0 >
<0 >
<0 >
Верхн. гран.
<10 >
<8 >
<12 >
<32000 >
<32000 >
<32000 >
<32000 >
<32000 >
<32000 >
<32000 >

По умолчанию нижняя граница принимается равной 0, а верхняя – 32000. В третьей колонке показан статус переменной: I – целочисленная; С – нецелочисленная, который можно изменять. После ввода верхней границы переменной Х3 (т.е. 12 ) можно нажать клавишу / для быстрого окончания корректировки. После нажатия клавиши Spacebar на экране появится шаблон ЭММ (ЦФ и ограничения) со свободными позициями для ввода коэффициентов.
Введите коэффициенты модели, при необходимости поменяйте знаки (<=, >=, =). Заполненный шаблон выглядит следующим образом:
Mах 20____х1 6_____х2 8_____х3 _______d21 _______d22
____d23 _____d24 ______d31 _______d32 _______d33
Ограничен.
(1) 10____х1 5_____х2 4_____х3 _______d21 _______d22
____d23 _____d24 _____d31 _______d32 _______d33£ 206____
(2) 2 ____х1 7_____х2 4_____х3 _______d21 _______d22
____d23 _____d24 _____d31 _______d32 _______d33£ 100____
(3) ____х1 1_____х2 4_____х3 –2_____d21 –4_____d22
–6__d23 –8___d24 _____d31 _______d32 _______d33=0_______
(4) ____х1 _____х2 1_____х3 _______d21 _______d22
____d23 _____d24 –4____d31 –8_____d32 –12____d33=0_______
(5) ____х1 5_____х2 ______х3 1______d21 1______d22
1___d23 1____d24 _____d31 _______d32 _______d33=1_______
(6) ____х1 5_____х2 ______х3 _______d21 _______d22
____d23 _____d24 1____d31 1______d32 1______d33=1_______
После нажатия Spacebar на экране появится функциональное меню.
В функциональном меню выберите опцию 5-Решениет задачи. На экране появится меню опции <Решение>:

Меню опции <Решение>
пункт
1---- Решение и просмотр первой итерации
2---- Решение и просмотр всех итераций
3---- Решение без просмотра итераций
4---- Изменение толеранса (по умолчанию – 0.01)
5---- Возврат в функциональное меню
Опция 1 обеспечивает вывод в виде таблицы результатов только первой итерации, а опция 2 – всех итераций. При выборе опции 3 задача будет решена без просмотра итераций. 4 опция предназначена для изменения толеранса (допустимой погрешности целого при вычислениях, по умолчанию толеранс равен 0.01). Выбор опции 5 обеспечивает возврат в функциональное меню без решения задачи.
Выберите опцию 2-Решение и просмотр всех итераций. Результаты решения на каждой итерации представлены одинаковыми по форме таблицами, причём решение на первой итерации совпадает с решением, получаемым при решении задачи программой «Линейное программирование»:
Текущее решение итерация: 1 Стр.: 1
Нижн. гран.
перемен.
Верхн. гран.
Нижн. гран.
перемен.
Верхн. гран.
0 £
0 £
0 £
0 £
0 £
0 £
0 £
0 £
0 £
0 £
0 £
x1
x2
x3
d21
d22
d23
d24
d31
d32
d33
£ 10
£ 8
£ 12
£ бесконеч
£ бесконеч
£ бесконеч
£ бесконеч
£ бесконеч
£ бесконеч
£ бесконеч
£ бесконеч
x1
x2
x3
d21
d22
d23
d24
d31
d32
d33
10.000
4.571
12.000
0.571
0.000
0.000
0.429
0.000
0.000
1.000
20.000
6.000
8.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
Нецелоцисленное решение, цф (Max) = 332.4286 ZL=–1E+20

В первой и третьей колонках указываются нижняя и верхняя граница изменения переменных, в пятой – полученные значения переменных, в шестой – коэффициенты ЦФ. В последней строке выдаётся: либо текущее нецелочисленное значение ЦФ и нижняя граница ЦФ (ZL), либо сообщение «ветвь не имеет допустимого решения».
Переход от одной итерации к другой осуществляется нажатием любой клавиши, кроме G , при нажатии которой вычислительный процесс пойдёт без остановки до конца.
В результате решения задачи возможна выдача таких сообщений: «Нет допустимого решения», «Целевая функция не ограничена». В этих случаях осуществляется выход в функциональное меню. Если найден оптимальный план, то система выдаст сообщение «Найдено оптимальное решение. Для продолжения любая клавиша».
После нажатия любой клавиши выведет меню способов представления полученного решения задачи:
Меню опции <Просмотр/Печать итогового решения> prim2

пункт
1---- Просмотр итогового решения
2---- просмотр и печать итогового решения
3---- Возврат в функциональное меню
Опция 2 отличается от опции 1 только тем, что одновременно с выводом окончательного решения на дисплей осуществляется его печать на принтер. Аналогичные функции предлагаются в пункте 8 функционального меню.
Выберите опцию 1 – просмотр итогового решения. На экране появится таблица с результатами решения задачи:
итоговые результаты prim2 Стр.: 1
перемен. No. имена
Решение
коэффициент цел. функции
перемен. No. имена
Решение
коэффициент цел. функции
1 х1
2 х2
3 х3
4 d21
5 d22
10.000
4.000
12.000
0.000
1.000
0.0000
0.0000
0.0000
0.0000
0.0000
6 d23
7 d24
8 d31
9 d32
10 d33
0.0000
0.0000
0.0000
0.0000
1.0000
0.0000
0.0000
0.0000
0.0000
0/000
Maximum значение ц.ф.= 320 итоговая итерац. = 79

После 79 итераций получен оптимальный план задачи Х*=(10; 4; 12; 0; 1; 0; 0; 0; 0; 1). Прибыль от реализации продукции составит 320 д.е.