Домашнее задание;pdf

Лабораторная работа №1
по дисциплине
«Методы оптимальных решений»
Экономический факультет, II курс, 2013–2014 уч. год, летняя сессия
Работа посвящена изучению утилиты Excel «Поиск решения» (Solver) на примере
решения учебных задач линейной оптимизации.
Утилита Excel «Поиск решения»
Утилита доступна в среде Excel во вкладке «Данные». Если её там нет, следует
обратиться к инженеру класса или преподавателю с просьбой подключить соответствующую надстройку. В разных версиях Excel это делается по-разному. Дальнейшее изложение методических рекомендаций будет выполнено на примере Excel–2010.
Предполагается, что «Поиск решения» уже подключен.
Рассмотрим, например, следующую задачу линейного программирования
2x1 − x2 + 4x3 →
4x1 − 2x2 + x3 >
3x1 + 4x2 − 8x3 >
−x1
+ 3x3 6
x1 , x2 , x3 > 0.
min
10
20
30
Создадим новый документ Excel и запишем на пустом листе задачу так, как указано
на рис. 1.
Рисунок 1 — Первоначальная запись задачи
На рис. 1 для удобства отображения выделены две серые области. Горизонтальная область B1:D1 будет соответствовать переменным x1 , x2 и x3 . Изначально область пустая. Вертикальная область A2:A5 содержит формулы, растянутые из ячейки A2. Растягиваемая формула A2=СУММПРОИЗВ($B$1:$D$1;B2:D2) указана
1
на рис. 1. Обратите внимание на знаки «$» при указании диапазона $B$1:$D$1: они
необходимы для того, чтобы при копировании формулы в нижние ячейки данный
диапазон не изменялся.
Указанная в ячейке A2 формула означает, что берётся сумма произведений
2 · x1 + (−1) · x2 + 4 · x3 ,
что и составляет нашу целевую функцию. Будучи скопированной в последующие
ячейки, формула даёт левые части ограничений задачи. На рис. 1 левые части равны
нулю, так как ячейки B1:D1, соответствующие переменным, сейчас пустые (то есть
равны нулю).
Запустите «Поиск решения» и введите информацию о задаче так, как указано на
рис. 2.
Рисунок 2 — Окно «Параметры поиска решения»
В окне «Параметров. . . » следует обратить внимание на 6 элементов.
1. «Оптимизировать целевую функцию» — здесь следует выбрать целевую функцию, записанную в ячейке A2 (здесь и далее не важно, будем мы указывать
знаки «$» или нет).
2. «До» — выбрать тип задачи, то есть min или max. Также утилита предоставляет возможность вместо минимума и максимума найти заданное пользователем
значение целевой функции (ответить на вопрос, может ли целевая функция
достигнуть заданного значения). В нашей задаче следует выбрать «Минимум».
2
3. «Изменяя ячейки переменных» — здесь следует указать переменные задачи, в
нашем случае им соответствуют ячейки B1:D1.
4. «В соответствии с ограничениями» — указываются ограничения задачи. В нашей задаче два ограничения имеют тип «>» и одно «6». С помощью кнопки
«Добавить» укажем, что левые части первых двух ограничений должны быть
больше, либо равны правым (A3:A4>=F3:F4) и левая часть оставшегося ограничения меньше, либо равна правой (A5<=F5)
5. «Сделать переменные без ограничений неотрицательными» — установите эту
галочку для того, чтобы выполнялось условие x1 , x2 , x3 > 0. Без этого условия
переменные не ограничены по знаку.
6. «Выберите метод решения» — следует выбрать симплекс-метод, так как именно
его мы будем изучать для решения задач линейного программирования.
После выполнения всех указанных выше манипуляций, нажмите кнопку «Найти
решение». Если задача имеет конечное оптимальное решение, оно будет найдено, а
на экране появится окно как на рис. 3.
Рисунок 3 — Сообщение о том, что решение найдено
Нажмите «ОК», тогда решение задачи появится на листе Excel (рис. 4).
Рисунок 4 — Найденное решение появилось на листе
3
Итак, решением нашей задачи стало значение переменных
x1 ≈ 3,64, x2 ≈ 2,27, x3 = 0.
При этом минимальное значение целевой функции равно 5 (будем указывать это как
z = 5).
Помимо указанного случая, когда существует конечное оптимальное решение,
возможны ещё два: решения нет и целевая функция неограничена. В этих случаях
вместо «Решение найдено» Excel выведет соответствующие сообщения.
Задачи для самостоятельной работы
Задача 1
−3x1
7x1
−x1
x1
3x1
+
−
+
+
2x2
3x2
2x2
5x2
2x2
− x2
x1 ,
− 2x4 → max
+ 3x4 > 5
6 54
+ 4x4 > 42
+ x4 6 98
+ 3x4 = 50
x2 , x3 , x4 > 0.
+
+
+
+
+
3x3
4x3
3x3
3x3
2x3
Ответ: x1 = 0, x2 = 0, x3 = 18, x4 ≈ 16,67, z ≈ 20,67.
У данной задачи может быть и другой ответ: x1 ≈ 16,67, x2 = 0, x3 ≈ 23,56, x4 =
0, z ≈ 20,67. Задача ЛП может иметь несколько решений, однако значения целевых
функций для всех этих решений должны совпадать.
Задача 2
x1 + 3x2 + 5x3
x1 + 3x2 + 4x3
x1 + 5x2 + 2x3
x1 , x 2 , x 3 ,
+ 4x4 → max
+ x4 > 40
+ x4 6 0
x4 > 0.
Ответ: нет допустимого решения.
Задача 3
x1 + 3x2 + 5x3
x1 + 3x2 + 4x3
x1 + 5x2 + 2x3
x1 , x 2 , x 3 ,
4
+ 4x4 → max
+ x4 > 40
+ x4 > 20
x4 > 0.
Ответ: нет оптимального решения (целевая функция неограниченно растёт).
Задача 4
−2x1 + x2
x1 + 4x2
2x1 − x2
5x1 + 2x2
x1 > 0, x2
− 2x3 → max
+
x3 > 4
6 20
+ 12x3 = 10
6 0, x3 ∈ R.
Ответ: x1 ≈ 5,43, x2 = 0, x3 ≈ −1,43, z = −8.
Задача 5
x1 + 3x2 − 2x3
3x2 + x3
3x1 + 2x2 − 3x3
−x1 + 2x2 + 2x3
4x1 + 5x2 + x3
x1 , x 2 , x 3 , x 4
+ 4x4 → max
+ 3x4 > 2
+ 2x4 6 4
+ 5x4 6 6
+ 4x4 = 10
∈ [0, 1].
Ответ: x1 ≈ 0,41, x2 = 1, x3 ≈ 0,26, x4 ≈ 0,78, z = 6.
5