П.2.2. Решение задач линейного программирования

Порядок решения зада ЛП с помощью QSB рассмотрим на примере П.2.1. Подготовьте ЭММ задачи для решения на ЭВМ:

В нашей задаче: ЦФ на максимум, 4 переменных и 7 ограничений. Условия неотрицательности переменных (т.е., х ₂ ³ 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

В первой колонке указываются имена базисных переменных (естественные переменные обозначаются Х₁, Х₂,..., или как Вы их обозначили; дополнительные – S₁, S₂,...; искусственные – А₁, А₂,...).

Во второй колонке находятся коэффициенты ЦФ, соответствующие базисным переменным.

В заголовках следующих пяти колонок указаны имена переменных и коэффициенты ЦФ (строкой ниже). В колонках 3 и 4 находятся коэффициенты матрицы ограничений модели, а в колонках 5-7 – базисные вектора, образованные путём введения в систему дополнительных и искусственных переменных.

В 8 колонке – столбец свободных членов.

В 9 колонку (кроме начальной таблицы, в которой в 9 колонке помещены нули) заносятся отношения правых частей ограничений к соответствующим координатам вектора, вводимого в базис. Эти отношения необходимы для определения вектора, выводимого из базиса. Из базиса выводится вектор, имеющий наименьшее отношение. Деление на ноль в последней колонке обозначается символом Inf.

В двух последних строках таблицы рассчитываются относительные оценки (колонки 3-7) и в 8 колонке помещается значение ЦФ при данном базисном плане, причём в последней строке считаются оценки и значение ЦФ исходной задачи, а в последней строке – расширенной задачи, полученной путём введения искусственных переменных.

ЦФ расширенной задачи определяется следующим образом: max L = = – , где 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	+бескон +бескон

Здесь для каждого коэффициента ЦФ указано его исходное значение, а также нижняя и верхняя граница возможного его изменения с сохранением оптимального плана (т.е., цена П₂ может изменяться в интервале [–¥, 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.