Программа графического решения и исследования задач линейного программирования

В лабораторной работе графическое решение и исследование чувствительности задач линейного программирования к изменению исходных параметров проводятся с помощью программы lp.exe.

При запуске программы на выполнение на экране появляется основное меню

перемещаться по которому можно с помощью клавиш управления курсором (­ и ¯). Выбор пункта меню осуществляется нажатием <Enter>. Для получения более подробной информации о программе используется <F1>. Выход из режима ознакомления – по нажатию любой клавиши.

1. При выборе пункта “Выполнение по заданному варианту” внизу экрана появляется запрос на ввод номера варианта. Необходимо ввести одну из цифр от 0 до 9 и нажать <Enter>. После этого на экране будет выведено графическое решение задачи (если оно существует) или выдано сообщение:

ОДР не ограничена или не существует.

В последнем случае нужно нажать любую клавишу для возврата в главное меню.

В режиме “Выполнение по заданному варианту” программа использует уже имеющиеся начальные условия, записанные в файлы v0.txt – v9.txt.

На представленном программой графике целевая функция и оптимальная вершина выделены красным цветом. Одна из границ ОДР подсвечена зеленым цветом. Это означает, что все манипуляции при исследовании чувствительности решения будут производиться над этой прямой, т. е. она является активной. В правой части экрана также отображаются:

1. исходная система ограничений, выражение для целевой функции и цель оптимизации (maximum или minimum), взятые из соответствующего файла;

2. оптимальное значение функционала (начальное) и значения переменных, при которых оно достигается;

3. шаг изменения коэффициентов правых частей ограничений;

4. угол наклона активизированной прямой относительно оси абсцисс;

5. значения коэффициентов выбранной прямой;

6. информация об изменении значения функционала.

Если анализ чувствительности решения к изменению исходных параметров проводить не требуется, то пользователю будет необходима информация, относящаяся только к первым двум подпунктам. На этом работа программы может быть завершена. Для возврата из графического режима в главное меню нужно нажать <Esc>.

2. При выборе пункта “Выполнение с вводом данных” ввод начальных условий осуществляется по подсказке системы. Программа запрашивает количество уравнений в системе ограничений (вводится число не более 7), направление оптимизации функционала (1 – максимизация, 0 – минимизация). Далее пользователю предлагается поочередно ввести значения коэффициентов системы и целевой функции, а также знаки неравенств в системе. Коэффициенты должны содержать не более 12 символов, включая точку (не запятую!) в случае дробных чисел. Знак неравенства: ³ – вводится ²0²; £ – вводится ²1². Для ввода каждого значения в программу необходимо нажимать <Enter>. Вся вводимая информация записывается в файл данных v0.txt, поэтому в дальнейшем пользователю не нужно повторно осуществлять процедуру ввода, а можно воспользоваться режимом “Выполнение по заданному варианту” (вариант 0).

Если данные введены неверно, а клавиша <Enter> не нажата, то можно ²стереть² их с помощью клавиши <Back Space> и ввести заново. Иначе нужно либо повторить процедуру ввода сначала, либо выйти из программы и скорректировать файл данных v0.txt, который должен строго соответствовать шаблону, приведенному в комментариях к программе (клавиша <F1>).

По окончании ввода на экране будет выведено графическое решение задачи (если оно существует) или выдано сообщение:

ОДР не ограничена или не существует.

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

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

Исследование чувствительности графического решения к изменению исходных параметров (если оно необходимо) можно провести в любом из режимов “Выполнение по заданному варианту” или “Выполнение с вводом данных”.

Для анализа чувствительности к изменению коэффициентов правых частей ограничений или матрицы системы выбирается одна из границ ОДР, не примыкающая к оптимальной вершине, с помощью клавиш управления курсором “влево” или “вправо”. Выбранная прямая становится активной.

Увеличение (уменьшение) значения коэффициента b_i активизированной прямой осуществляется клавишами управления курсором “вверх” (“вниз”), при этом граница перемещается параллельно самой себе, а на экране отображается новое значение коэффициента b_i. Приращение коэффициента определяется шагом (по умолчанию равным 0.25), который можно менять с помощью клавиш <+>, <–> в правой части клавиатуры в интервале от 0 до 1 с дискретизацией 0.05.

Для анализа пределов изменения коэффициента правой части другого ограничения необходимо вернуться к исходным условиям, нажав <Enter>. При одновременном изменении нескольких коэффициентов полученные результаты могут быть некорректными.

Для исследования коэффициентов матрицы системы поочередно осуществляется поворот выбранной границы ОДР с помощью следующих клавиш:

‘1’ – поворот прямой против часовой стрелки относительно вершины ОДР, расположенной правее или выше;

‘2’ – поворот прямой по часовой стрелке относительно вершины ОДР, расположенной правее или выше;

‘3’ – поворот прямой против часовой стрелки относительно вершины ОДР, расположенной левее или ниже;

‘4’ – поворот прямой по часовой стрелке относительно вершины ОДР, расположенной левее или ниже.

Т.е. сделав предельно возможный поворот в одном направлении, нужно зафиксировать полученные значения коэффициентов, а потом вернуться к начальным условиям (<Enter>). А затем аналогично произвести повороты в других направлениях. При каждом нажатии соответствующей клавиши на экране отображаются новое положение прямой и значения коэффициентов a_ij. Исследование чувствительности к изменению коэффициентов матрицы системы также необходимо проводить для каждого ограничения в отдельности.

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

Границы ОДР, совпадающие с осями координат, не участвуют в исследовании на чувствительность, поскольку они определяются не ограничениями исходной системы, а условием неотрицательности значений переменных.

Возможные пределы изменения коэффициентов целевой функции определяются коэффициентами при неизвестных в ограничениях ОДР, соответствующих прямым, примыкающим к оптимальной вершине. В этом можно убедиться, если в режиме ввода данных для конкретной системы ограничений ввести сначала новые значения c_j, совпадающие с коэффициентами соответствующего ограничения, а потом (при повторном вводе) незначительно изменить в ту или иную сторону один из коэффициентов. Во втором случае при определенном соотношении коэффициентов оптимальное решение переместится в соседнюю вершину.

Основной информацией для пользователя во всех трех случаях являются начальные условия и предельные значения исследуемых коэффициентов при неизменном значении целевой функции.

При необходимости определения, какие из коэффициентов системы ограничений целесообразно изменять для увеличения (уменьшения при минимизации) оптимального значения функционала, выбирается одна из границ ОДР, примыкающая к оптимальной вершине, с помощью клавиш управления курсором “влево” или “вправо”. Далее исследование проводится фактически аналогично описанному выше за исключением некоторых моментов:

7. при анализе поведения функционала целесообразно исследовать только те направления изменения коэффициентов, которые приводят к изменению функционала в желаемую сторону (увеличение при максимизации, уменьшение при минимизации);

8. помимо начальных условий и полученного исходного решения пользователю здесь необходимо зафиксировать пределы изменения рассматриваемых коэффициентов и соответствующие им значения целевой функции.

Из графического режима можно в любой момент вернуться в главное меню, нажав <Esc>.

3. По окончании работы с программой нужно выбрать в основном меню пункт “Выход” для возврата в операционную систему.

ОГЛАВЛЕНИЕ

1. Решение задач линейного программирования графическим методом…………1

2. Исследование графического решения задач линейного программирования….3

2.1. Исследование чувствительности решения к изменениям коэффициентов правых частей ограничений………………………………………………………..4

2.2. Исследование чувствительности решения к изменениям коэффициентов матрицы системы ограничений……………………………………………………6

2.3. Исследование чувствительности решения к изменениям коэффициентов целевой функции……………………………………………………………………9

3. Программа графического решения и исследование задач линейного программирования………………………………………………………………………………12

Д о н д и к Евгений Михайлович

Графическое решение и исследование задач

линейного программирования

(с программным обеспечением)

Редактор И.П.Перехрест

Корректор М.Е.Цветкова

Лицензия № 020446 от 14.03.97.

Подписано в печать Формат бумаги 60 х 84 1/16.

Бумага газетная. Печать офсетная. Усл.печ.л. 1,0.

Уч.-изд.л.1,0. Тираж 30 экз. Заказ

Рязанская государственная радиотехническая академия.

391000, Рязань, ул.Гагарина, 59/1.

Редакционно-издательский центр РГРТА.

Министерство образования российской федерации

Рязанская государственная радиотехническая академия