Порядок решения зада ЛП с помощью QSB рассмотрим на примере П.2.1. Подготовьте ЭММ задачи для решения на ЭВМ:
В нашей задаче: ЦФ на максимум, 4 переменных и 7 ограничений. Условия неотрицательности переменных (т.е., х2 ³ 0) заданы по умолчанию.
Выберите опцию Линейное программирование в главном меню системы. На экране появится функциональное меню:
Добро пожаловать в линейное программирование!
Варианты работы с LP:
Если вы работаете с системой впервые, то выберите опцию 1.
Опция
Функция
Помощь по LP
Ввод новой задачи
Чтение задачи с диска
Просмотр/Печать исходных данных
Решение задачи
Запись задачи на диск
Изменение задачи
Просмотр/Печать итогового решения
Возврат в главное меню
Выход из QSB
В функциональном меню выберите опцию 2 – Ввод новой задачи. В верхней сроке экрана появится запрос о названии задачи:
Введите название задачи (до 6 символов)? prim1
Наберите имя задачи, длиной не более 6 символов, например, prim1 ,и нажмите Enter . При нажатии Enter автоматически происходит возврат в функциональное меню.
Вверху экрана появятся требования, которые необходимо соблюдать при вводе исходных данных (способы представления чисел, знаки отношения в неравенствах, клавиши перемещения курсора и др.); а внизу – вопросы о задаче:
Критерий на максимум (1) или минимум (2)? (Введите 1 или 2) <1>
Сколько переменных в вашей задаче? (введите число <=40) <4>
Сколько ограничений в вашей задаче? (введите число <=40) <7>
Хотите использовать заданные имена переменных (Х1, Х2,...,Хn) (Y/N)? <y>
Ответьте на вопросы. Варианты ответов показаны выше (ЦФ на максимум, 4 переменных и 7 ограничений, будем использовать заданные имена переменных – Х1, Х2,...,Хn). Переход от предыдущей строки к последующей осуществляется нажатием Enter , обратный переход – клавишей Backspace .
Если при вводе не было ошибок, то по окончании нажмите клавишу
Spacebar для корректировки введённой информации – любую другую клавишу.
На экране появится шаблон ЭММ (ЦФ и ограничения) со свободными позициями для ввода коэффициентов. Заполните шаблон, при необходимости поменяйте знаки (<=, >=, =):
Max 60______ X1 70______X2 120_______X3 130______X4
Ограничен.
1) 1_____Х1 2_____Х2 3_____Х3 4_____Х4 £ 40_____
2) 6_____Х1 5_____Х2 4_____Х3 3_____Х4 £ 110____
3) 4_____Х1 6_____Х2 8_____Х3 12____Х4 £ 100____
4) 1_____Х1 ______Х2 ______Х3 ______Х4 >=1_____
5) 1_____Х1 ______Х2 ______Х3 ______Х4 £ 12_____
6) ______Х1 ______Х2 1_____Х3 ______Х4 >=2_____
7) ______Х1 ______Х2 ______Х3 1_____Х4 = 3______
После нажатия клавиши Spacebar на экране появится функциональное меню. В функциональном меню выберите опцию 6 – Запись задачи на диск. В верхней части экрана появится запрос об имени файла, в котором будут храниться исходные данные задачи.
Наберите имя файла (например, такое же как и имя задачи, т.е. prim1 ) и нажмите Enter . Для просмотра существующих файлов введите имя диска и нажмите Enter . При нажатии Enter без ввода имени файла осуществляется автоматический возврат в функциональное меню.
Если файла нет на диске, то выводится сообщение «Задача записана. Для продолжения любая клавиша.». Если файл с таким именем существует, то требуется подтверждение о замене его содержимого (Y) или отмене записи задачи (N): «Этот файл уже существует. Заменить его (Y/N)?» Введите Y или N и нажмите Enter . На экране появится функциональное меню.
В функциональном меню выберите опцию 3 – Чтение задачи с диска. В верхней части экрана появится запрос об имени файла, в котором хранятся исходные данные задачи.
Выберите имя файла prim1 и нажмите Enter . Для просмотра существующих файлов введите имя диска и нажмите Enter . При нажатии Enter без ввода имени файла осуществляется автоматический возврат в функциональное меню.
Если файла нет на диске, то выводится сообщение: «Нет такого файла. Повторите ввод». Если файл с таким именем существует, но в нём хранятся данные не задачи ЛП, то выводится сообщение «В этом файле нет задачи линейного программирования». И в том, и в другом случае необходимо повторить ввод имени файла. Если задача прочитана успешно, то выводится сообщение «Задача прочитана. Для продолжения любая клавиша». После нажатия любой клавиши на экране появится функциональное меню.
В функциональном меню выберите опцию 4 – Просмотр/Печать исходных данных. Если задача не была ведена или прочитана с диска, то будет выдано сообщение: «Задача не введена. Для продолжения любая клавиша», и после нажатия любой клавиши на экране появится функциональное меню; в противном случае – в верхней строке экрана появится запрос о необходимости вывода данных на принтер.
Убедитесь, что принтер готов к работе, введите символ Y (если распечатка не требуется, то – символ n ) и нажмите Enter . На экран (и принтер, если задано) будет выведено описание исходных данных задачи.
В задаче большой размерности исходные данные могут занимать несколько экранных страниц. Перемещение к следующей странице осуществляется нажатием клавиши / , к предыдущей странице – Esc . Для выхода в функциональное меню нажмите клавишу Spacebar после окончания просмотра.
В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:
Меню опции <Решение>
пункт
1---- Решение и просмотр начальной таблицы
2---- Решение и просмотр итоговой таблицы
3---- Решение и просмотр начальной и итоговой таблиц
4---- Решение и просмотр всех таблиц
5---- Решение без просмотра таблиц
6---- Возврат в функциональное меню
Выбор опции 6 обеспечивает возврат в функциональное меню без решения задачи. При выборе остальных опций задача будет решена. При этом для задач небольшой размерности доступны все режимы, а для больших задач – только опции 4-5. С целью усвоения алгоритма симплекс-метода начинающему пользователю рекомендуется выбирать опцию 4, обеспечивающую просмотр процесса решения по шагам.
Выберите опцию 4---- Решение и просмотр всех таблиц. На экране появится информация по каждой итерации, причём для больших задач (наш пример) выдаётся только номер итерации, текущее значение ЦФ, вводимые и выводимые из базиса вектора:
итерация: 1 Новая цф(Мах.)=390+(–3BigM)
Вводим: Х4 значение = 3 Выводим: А7 Стр 7
Для небольших задач информация оформлена в виде симплекс-таблицы:
Базис
С( j)
X1
X2
S1
A1
S2
B( j)
B(j)
A(i j)
2.000
3.000
–M
A1
S2
–M
2.000
1.000
1.000
5.000
–1.00
1.000
1.000
5.000
20.00
2.500
20.00
C( j)–Z( j)*BigM
2.000
2.000
3.000
1.000
–1.00
–5.00
Текущее значение целевой функции (Мах.)=0+(–5BigM)
<подсвеченные переменные вводим или выводи из базиса>
Вводим: Х1 Выводим: А1
В первой колонке указываются имена базисных переменных (естественные переменные обозначаются Х1, Х2,..., или как Вы их обозначили; дополнительные – S1, S2,...; искусственные – А1, А2,...).
Во второй колонке находятся коэффициенты ЦФ, соответствующие базисным переменным.
В заголовках следующих пяти колонок указаны имена переменных и коэффициенты ЦФ (строкой ниже). В колонках 3 и 4 находятся коэффициенты матрицы ограничений модели, а в колонках 5-7 – базисные вектора, образованные путём введения в систему дополнительных и искусственных переменных.
В 8 колонке – столбец свободных членов.
В 9 колонку (кроме начальной таблицы, в которой в 9 колонке помещены нули) заносятся отношения правых частей ограничений к соответствующим координатам вектора, вводимого в базис. Эти отношения необходимы для определения вектора, выводимого из базиса. Из базиса выводится вектор, имеющий наименьшее отношение. Деление на ноль в последней колонке обозначается символом Inf.
В двух последних строках таблицы рассчитываются относительные оценки (колонки 3-7) и в 8 колонке помещается значение ЦФ при данном базисном плане, причём в последней строке считаются оценки и значение ЦФ исходной задачи, а в последней строке – расширенной задачи, полученной путём введения искусственных переменных.
ЦФ расширенной задачи определяется следующим образом: maxL = =–, где M(BigM) – достаточно большое положительное число.
Оценки считаются по формуле , где s - множество индексов базисных векторов, s = {1,2,...,m}; C( j) – коэффициенты ЦФ; x(i,j) – коэффициенты разложения векторов матрицы ограничений по единичному базису (i = 1...m; j = 1...n+m). Признаком оптимальности базисного допустимого плана служит наличие неположительных двойственных оценок.
По последней строке определяется вектор, подлежащий включению в базис. Этот вектор имеет наибольшую относительную оценку. Итерационный процесс на основе анализа оценок последней строки проводится с целью исключения из базиса всех искусственных векторов, затем, если существует хотя бы одно допустимое решение, процесс отыскания оптимального плана исходной задачи продолжается с использованием предпоследней строки.
Ниже таблицы выдаётся текущее значение ЦФ для данной итерации и указываются имена вводимой в базис и выводимой из базиса переменных. В таблице эти переменные выделены цветом. Под последней симплекс таблицей показано значение ЦФ, вычисленное на оптимальном плане.
Переход от одной итерации к другой осуществляется нажатием любой клавиши, кроме G , при нажатии которой вычислительный процесс пойдёт без остановки до конца.
В результате решения задачи возможна выдача таких сообщений: «Нет допустимого решения», «Целевая функция не ограничена». В этих случаях осуществляется выход в функциональное меню.
Если найден оптимальный план, то после просмотра процесса решения, согласно выбранному режиму (1-4) или без просмотра итераций (5) система выдаст сообщение «Найдено оптимальное решение. Для продолжения лбая клавиша» и после нажатия любой клавиши выведет меню способов представления полученного решения задачи:
Меню опции <Просмотр/Печать итогового решения> prim1
Варианты работы для просмотра/печати итогового решения
Для печати итогового решения подготовьте принтер
пункт
1---- Просмотр итогового решения
2---- просмотр решения и анализ чувствительности
3---- просмотр/печать решения
4---- просмотр/печать решения и анализ чувствительности
5---- Возврат в функциональное меню
Опция 5 позволяет вернуться в функциональное меню без просмотра результатов. Опции 1-4 обеспечивают вывод на экран (а 3-4 – и на принтер) итогового решения и результатов анализа чувствительности коэффициентов ЦФ и коэффициентов правой части ограничений. Аналогичные функции предлагаются в пункте 8 функционального меню.
Выберите опцию 2 – просмотр решения и анализ чувствительности. На экране появится таблица с результатами решения задачи:
итоговые результаты prim1 Стр.: 1
перемен. No. имена
Решение
Дв. оц.
перемен. No. имена
Решение
Дв. оц.
1 Х1
2 Х2
3 Х3
4 Х4
5 S1
6 S2
7 S3
8 S4
1.0000
0.0000
7.5000
3.0000
4.5000
65.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
15.0000
0.0000
9 A4
10 S5
11 S6
12 A6
13 S7
14 A7
15 A8
0.0000
11.0000
0.0000
0.0000
5.5000
0.0000
0.0000
0.0000
0.0000
20.0000
–20.0000
0.0000
0.0000
–50.0000
Maximum значение ц.ф.= 1350 (из множества реш.) итерац. = 5
После 5 итераций получен оптимальный план задачи Х*=(1; 0; 7,5; 3). Прибыль от реализации продукции составит 1350 д.е. Пользуясь этой таблицей, можно начать послеоптимизационный анализ задачи, основанный на двойственных оценках (колонки 3 и 6), а именно определить степень дефицитности ресурсов, установить, как изменится значение ЦФ при изменении запасов ресурсов на единицу. Финансы оказались лимитирующим ресурсом (S3=0, двойственная оценка положительна), остальные ресурсы – избыточные. Увеличение финансов приведёт к увеличению прибыли, а рост материальных и трудовых ресурсов – нет. Более подробный анализ решения производится автоматически в двух последующих таблицах.
После нажатия любой клавиши на экране появится таблица, содержащая анализ чувствительности коэффициентов ЦФ к изменению исходных данных:
Анализ чувствительности коэффициентов ц.ф. Стр.: 1
С(j)
MinС(j)
исходное
Max С(j)
C(j)
Min С(j)
исходное
Max С(j)
C(1)
C(2)
–бескон
–бескон
60.0000
70.0000
60.0000
90.0000
С(3)
С(4)
120.0000
–бескон
120.0000
130.0000
+бескон
+бескон
Здесь для каждого коэффициента ЦФ указано его исходное значение, а также нижняя и верхняя граница возможного его изменения с сохранением оптимального плана (т.е., цена П2 может изменяться в интервале [–¥, 90] без изменения оптимального плана).
После нажатия любой клавиши на экране появится таблица, содержащая анализ чувствительности для ресурсов (правой части ограничений) к изменению исходных данных.
Анализ чувствительности правой части Стр.: 1
B(j)
MinB(i)
исходное
MaxB(i)
B(j)
MinB(i)
исходное
MaxB(i)
В(1)
В(2)
В(3)
В(4)
35.5000
45.0000
56.0000
0.0000
40.0000
110.0000
100.0000
1.0000
+бескон
+бескон
112.0000
12.0000
В(5)
В(6)
В(7)
В(8)
1.0000
0.0000
–бескон
0.0000
12.0000
0.0000
2.0000
3.0000
+бескон
7.3333
7.5000
6.6667
Здесь для каждого вида ресурса указано его исходное значение, а также нижняя и верхняя граница возможного изменения запасов ресурсов с сохранением структуры оптимального плана (т.е., при изменении запаса третьего ресурса в пределах [56; 112] набор базисных переменных останется неизменным). Проверим данное утверждение, максимально изменив величину запаса третьего ресурса со 100 до 112.
Нажмите любую клавишу. На экране появится функциональное меню. Выберите опцию 7 – Изменение задачи. На экране появится меню для корректировки исходных данных задачи:
Меню опции <Изменение > prim1
пункт
1---- изменение коэффициентов задачи
2---- изменение ограничения
3---- плюс 1 ограничен.
4---- минус 1 ограничение
5---- плюс переменная
6---- минус переменная
7---- Просмотр/Печать исходных данных
8---- Возврат в функциональное меню
Работа с опциями 1-2 аналогична вводу данных новой задачи. В первом случае предоставляется возможность корректировки коэффициентов задачи, начиная с первого ограничения, а во втором – с заданного пользователем. Опции 3 и 4предназначены для добавления и удаления одного ограничения. Опции 5 и 6 – для добавления и удаления одной переменной. Добавление переменной предполагает ввод её имени и значений коэффициентов ЦФ и ограничений.
Выберите опцию 2 – изменение ограничения. На экране появится запрос (который выдаётся каждый раз при выборе опций 1 –6) на ввод названия задачи.
Нажмите Enter , таким образом, все изменения будут производиться в текущей задаче. Далее появится запрос на ввод номера ограничения.
Наберите на клавиатуре номер ограничения ( 3 ) и нажмите Enter . На экране появится ЭММ задачи (с третьего ограничения).
Переместите курсов к цифре 100 и введите 112 . Для быстрого окончания корректировки нажмите дважды клавишу / .
В появившемся меню выберите опцию 8 – Возврат в функциональное меню.
Решите задачу. Ответ: Х*=(1; 0; 9; 3), L = 1530. Структура оптимального плана не изменилась.
Для окончания работы в функциональном меню выберите опцию 0 – Выход из QSB.