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

Порядок решения задач ЦП с помощью QSB рассмотрим на примере.

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

В нашей задаче: ЦФ на максимум, 10 переменных и 9 ограничений.

Выберите опцию 2 – Целочисленное программирование в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.

В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim2 ), ответьте на вопросы о задаче. Варианты ответов: ЦФ на максимум, 10 переменных и 9 ограничений, будем переименовывать переменные, т.е. при ответе на последний вопрос введите символ N . По окончании нажмите клавишу Spacebar . На экране появится шаблон для ввода новых имён переменных (вместо заданных Х₁, Х₂,...,Х_п).

Переименуйте переменные, как показано ниже:

Переход к следующей позиции осуществляется нажатием Enter , обратный переход – клавишей Backspace . Если при вводе не было ошибок, то по окончании нажмите клавишу Spacebar ; для корректировки введённой информации – любую другую клавишу.

На экране появится ряд дополнительных вопросов о задаче, на которые нужно ответить ( Y - да, или N - нет):

Заполните появившийся шаблон для ввода целочисленных переменных и границ их изменения:

По умолчанию нижняя граница принимается равной 0, а верхняя – 32000. В третьей колонке показан статус переменной: I – целочисленная; С – нецелочисленная, который можно изменять. После ввода верхней границы переменной Х₃ (т.е. 12 ) можно нажать клавишу / для быстрого окончания корректировки. После нажатия клавиши Spacebar на экране появится шаблон ЭММ (ЦФ и ограничения) со свободными позициями для ввода коэффициентов.

Введите коэффициенты модели, при необходимости поменяйте знаки (<=, >=, =). Заполненный шаблон выглядит следующим образом:

После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5-Решениет задачи. На экране появится меню опции <Решение>:

Опция 1 обеспечивает вывод в виде таблицы результатов только первой итерации, а опция 2 – всех итераций. При выборе опции 3 задача будет решена без просмотра итераций. 4 опция предназначена для изменения толеранса (допустимой погрешности целого при вычислениях, по умолчанию толеранс равен 0.01). Выбор опции 5 обеспечивает возврат в функциональное меню без решения задачи.

Выберите опцию 2-Решение и просмотр всех итераций. Результаты решения на каждой итерации представлены одинаковыми по форме таблицами, причём решение на первой итерации совпадает с решением, получаемым при решении задачи программой «Линейное программирование»:

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

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

В результате решения задачи возможна выдача таких сообщений: «Нет допустимого решения», «Целевая функция не ограничена». В этих случаях осуществляется выход в функциональное меню. Если найден оптимальный план, то система выдаст сообщение «Найдено оптимальное решение. Для продолжения любая клавиша».

После нажатия любой клавиши выведет меню способов представления полученного решения задачи:

Опция 2 отличается от опции 1 только тем, что одновременно с выводом окончательного решения на дисплей осуществляется его печать на принтер. Аналогичные функции предлагаются в пункте 8 функционального меню.

Выберите опцию 1 – просмотр итогового решения. На экране появится таблица с результатами решения задачи:

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