Применение алгоритма «Поиск решения»

Цель работы: построить целевую функцию ЗЛП и с помощью алгоритма «Поиск решения» найти точку оптимального плана.

Теоретическое обоснование

Приравняем целевую функцию к постоянной величине а: . Меняя значение а, получим семейство параллельных пря­мых, каждая из которых называется линией уровня. Линия уровня - геометри­ческое место точек, в которых целевая функция принимает одно и то же значе­ние, равное а. Целевая функция не зафиксирована в определенном положении относительно начала координат (а может принимать различные значения). Ее можно перемешать параллельным переносом, как в направлении возрастания, так и по направлению убывания. Целевая функция перпендикулярна градиен­ту. На графике ее можно отобразить двумя способами:

а) построить градиент и провести к нему перпендикуляр;

б) приравнять целевую функцию к какому - либо числу затем рас­считать координаты точек пересечения с осями ОХ и ОУ.

Градиент - вектор, который показывает направление наискорейшего воз­растания целевой функции. Градиент строится из начала координат. Координа­ты градиента - это частные производные целевой функции Действительно, Получаем градиент С(60;50).

Чтобы найти точку оптимального плана, среди точек многоугольника области допустимых решений ABCDE (рис. 1) необходимо найти такую, в ко­торой функция принимает максимальное значение. Для этого целевую функцию переносят параллельным переносом по направлению гради­ента до крайней точки пересечения с ОДР. Точка С будет точкой оптимально­го плана, так как в этой точке целевая функция будет достигать своего мак­симального значения.

Ход выполнения

1. Для построения градиента внесите в ячейки поля EXCEL коэффициен­ты , при переменных XI и целевой функции и соответствую­щие подписи так, как это показано в табл. 6.

Добавьте строку для расчета координат градиента. С помощью ссылок на коэффициенты целевой функции запишите расчет координат градиента в ячей­ки Е10 и G10 (табл.6).

Градиент строится в диаграмме «Точечная» аналогично процедуре по­строения прямых ОДР (п. 3, абзац 2 лабораторной работы 1).

 

Таблица 6

 

	А	В	С	D	Е	F	G	Н
					Координаты на оси ОХ1	Координаты на оси ОХ2
		Юбки ()	Брюки ()	Запас ресур­сов	=0
	Ткань	1,5				=D3/B3	=D3/C3
	Трудоем­кость
	Наклад­ные рас­ходы
	Спрос					=D6/B6	любое
		I
	Целевая функция			а
	Градиент				=В9		=С9

2. Построение целевой функции проводится по точкам пересечения с осями координат.

В поле расчета координат точек пересечения прямых ОДР с осями ОХ1 и ОХ2 скопируйте формулы из строки 3 в строку 9 (табл. 6). В ячейку D9 запи­шите любое положительное числовое значение

В «Исходные данные» диаграммы EXCEL добавьте ограничение «Целе­вая функция» согласно второму шагу построения (п. 3, второй абзац лабораторной работы 1). Построенная целевая функция может располагаться как на пере­сечении с ОДР, так и за пределами ОДР в зависимости от значения

3. Чтобы обеспечить передвижение целевой функции по графику EXCEL до точки оптимума, необходимы дополнительные построения.

Добавьте после строки «Целевая функция» в табл. 6 строку «Допустимый план», в ячейках В11 и С11 которой будут содержаться допустимые значения и плана ЗЛП. Выделите эти ячейки с помощью заливки.

Вставьте справа от расширенной матрицы ЗЛП еще один столбец, в со­ответствующих строках которого будут записываться формулы левых частей ограничений и целевой функции (см. табл. 7) Запишите в ячейку ЕЗ табл. 7 формулу =ВЗ*В11 + СЗ*С11. Скопируйте эту формулу в остальные ячейки столбца Е табл. 7.

Вместо любого значения а>0 в ячейке D9 установите ссылку на ячейку Е9 (см. табл. 7).

Для передвижения целевой функции по диаграмме достаточно «привя­зать» целевую функцию к координатам точки допустимого плана (точки опти­мума).

Постройте на диаграмме точку допустимого плана. В меню «Исходные данные» графического редактора выберите опцию «добавить ряд». В окно «Значения X» с помощью ссылки вставьте адрес ячейки со значением допустимого плана В окно «Значение У» с помощью ссылки вставьте адрес ячейки со значением допустимого плана . Для точки допустимого плана установите крупный значок маркера.

Теперь введите в ячейки допустимого плана любые допустимые значения и . На поле диаграммы появится целевая функция, и маркером на ней бу­дет обозначена точка допустимого плана.

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

Таблица 7

 

	А	В	С	D	Е	F	G	Н
						Координаты на оси ОХ 1	Координаты на оси ОХ2
		Юбки	Брюки	Запас ресурсов	Значения при
	Ткань	1,5					=D3/B3	=D3/C3
	Трудоемкость
	Накладные расходы
	Спрос						=D6/B6	любое
	Целевая функция
	Градиент
	Допустимый план

4. Для нахождения оптимального плана воспользуйтесь встроенной в EXCEL процедурой «Поиск решения».

Основные этапы выполнения процедуры «Поиск решения»:

1. В опции «Сервис» выберите «Поиск решения».

2. В диалоговом окне «Целевая ячейка» сделайте ссылку на ячейку, содержащую значение целевой функции.

3. В окне «Ограничения» нажмите кнопку «Добавить». Появится новое диалоговое окно, в котором необходимо записать левую и правую части огра­ничений в виде ссылок на соответствующие ячейки:

=ЕЗ

=D3

 

Рис.2

Необходимо добавить таким способом все ограничения, в том числе и ус­ловия неотрицательности переменных и .

4. В окне «Изменяя ячейки» сделайте ссылки на ячейки, содержащие зна­чение допустимого плана и .

5. После записи всех ограничений в диалоговое окно «Ограничения» на­жмите кнопку «Выполнить».

6. После окончания алгоритма загорится диалоговое окно. Выберите «Сохранить найденное решение». Необходимо с помощью мышки и клавиши Shift выделить все три типа отчета и нажать ОК.

Контрольные вопросы

1. Что является графическим отображением области допустимых реше­ний ЗЛИ?

2. На каких участках области допустимых решений может находиться оп­тимальное решение ЗЛП?

3. Что является множеством решений неравенства?

4. Какие существенные недостатки не позволяют широко применять гра­фический метод для решения задач линейного программирования?

5. Что такое расширенная матрица?

Задание: докажите с помощью построенной диаграммы основное свой­ство линии уровня.

 

 

Лабораторная работа 3

Самостоятельное решение одного из предложенных вариантов ЗЛП

Решите предложенный вариант производственной системы, выполните следующие задания:

1. Обозначьте на графике допустимые базисные решения.

2. Обозначьте недопустимые базисные решения.

3. Установите в главном окне процедуры «Поиск решения» соответствующий флажок и проведите поэтапный алгоритм решения ЗЛП.

4. Установите соответствие между вершинами многоугольника ОДР и этапами процедуры «Поиск решения».