Инструкция по использованию microsoft Excel для решения задач цзлп

ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Excel

ПРИМЕР РЕШЕНИЕ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО

Задача Найти при ограничениях ,

Задачу без условия целочисленности переменных назовем задачей №1.

Решаем задачу №1 с помощью надстройки Excel - Поиск решения

1) оптимальные значения переменных помещаем в ячейки А2:В2, оптимальное значение целевой функции – в ячейку С3.

2) Введем исходные данные

	A	B	C	D	E
	X1	X2

3) В ячейку С3 ввести формулу «=СУММПРОИЗВ(А2:В2;А3:В3)». Замечание: массив 1 - А2:В2, массив 2 - А3:В3.

4) В ячейку С4 ввести формулу «=СУММПРОИЗВ(А2:В2;А4:В4)». В ячейку С5 ввести формулу «=СУММПРОИЗВ(А2:В2;А5:В5)».

5) Запустить Поиск решения

6) В поле «установить целевую ячейку» вводим адрес $C$3, ввести тип целевой функции (максимальное или минимальное значение), в поле «Изменяя ячейки» ввести адреса искомых переменных A$2:B$2

7) Нажимаем кнопку «Добавить», появляется диалоговое окно «Добавление ограничения». В поле «Ссылка на ячейку» ввести адрес $C$4 и знак ограничения, в поле «ограничение» ввести адрес $D$4. Для того, чтобы ввести остальные ограничения вновь нажимаем кнопку «Добавить». После введения последнего ограничения кнопка «ОК».

8) В диалогом окне Поиска решения нажимаем кнопку «Параметры», появляется диалоговое окно «Параметры поиска решения». Установить флажок в окнах «Линейная модель», «Неотрицательные значения». Вновь «ОК». Возвращаемся в диалоговое окно Поиска решения. Нажимаем кнопку «Выполнить».

Получим решение

	A	B	C	D
	x1	x2
		7,5
			29,5

Итак, . Так как значения неизвестной не удовлетворяет условию целочисленности, то проведем разбиение множества G допустимых решений задачи №1 на два подмножества . по неизвестной . ОДР (область допустимых решений) одной задачи будет содержать множество точек, у которых ≤7, а вторая – у которых ≥8. В результате получим две новые задачи линейной оптимизации: №2 и №3.

Задача №2 Задача №3

Решаем задачи №2 и №3 с помощью надстройки Excel - Поиск решения. Решение задачи №2:

x1	x2
1,2
		29,4
		37,6

Оптимальное решение без учета целочисленности

Решение задачи №3:

x1	x2
0,75
		29,25
		19,75

Условие целочисленности не выполняется, процедуру разбиения повторяем. Множество с большей оценкой разбиваем . Разобьем ОДР задачи №2 на два подмножества по переменной :≤1, ≥2. В результате получим две новые задачи №4 и №5:

Задача №4 Задача №5

Решаем задачи №4 и №5 с помощью надстройки Excel - Поиск решения. Решение задачи №4:

x1	x2

Решение задачи №5:

x1	x2

Оценка множества G_1,2 равна 29,25, что больше 29. Необходимо произвести ветвление множества G_1,2. Получаем две новых задачи №6 и №7. По сравнению с задачей №3 в задаче №6 добавим ограничение , а в задаче №7 ограничение .

Задача №6 Задача №7

Решаем задачи №6 и №7 с помощью надстройки Excel - Поиск решения. Решение задачи №6:

x1	x2
	9,5
		28,5
		9,5

Решение задачи №7:

x1	x2
	7,5
		29,5
		7,5

Программа Поиск решения сообщила, что не может найти правильного решения. Действительно, ограничение ≥8 не выполняется. Задача не имеет решения. Ответ:Ǿ.

Решение задачи схематично можно представить в виде графа

G

≤7 ≥8

≤1 ≥2 =0 ≥1

несовместна

Подзадачу №6 отбрасываем, т.к. значение функции меньше, чем , определяющее целочисленное решение задачи.

Проверка. При решении задачи с помощью надстройки Excel - Поиск решения: выбираем кнопку «Добавить», в окне «Ссылка на ячейку» вводим $А$2:$В$2, выбираем ограничение – цел.

x1	x2

Дата добавления: 2014-01-15