Зенкевич Н.А. Практикум по исследованию операций
Подождите немного. Документ загружается.
5.7. ЗАДАЧА О ДВУХ СТАНКАХ 131
i a
i
b
i
1 a
1
b
1
2
a
2
b
2
...
... ...
i a
k
b
k
...
... ...
N a
N
b
N
Шаг 2. Найти среди значений a
i
и b
i
– наименьшие.
Шаг 3. Если таковым значением окажется одно из a
i
, то поставить соответствующую
деталь первой.
Шаг 4. Если это одно из b
i
, то поставить соответствующую деталь последней.
Шаг 5. Вычеркнуть оба значения a
i
и b
i
из таблицы.
Шаг 6. Повторить этот процесс с 2n − 2 оставшимися величинами.
Шаг 7. В случае нескольких минимальных элементов для определенности выбрать с
меньшим номером. В случае, когда a
i
= b
i
упорядочить детали по значению a
i
.
5.7.2 Пример
Задана таблица, в которой указано время обработки деталей на двух станках.
i a
i
b
i
1 4 5
2 4 1
3 30 4
4 6 30
5
2 3
На первом
шаге получаем
i a
i
b
i
1 4 5
3 30 4
4 6 30
5 2 3
2 6 4 6 1
на втором
шаге
i a
i
b
i
5 6 2 6 3
1 4 5
3 30 4
4 6 30
2 6 4 6 1
на третьем
шаге
i a
i
b
i
5 6 2 6 3
1 6 4 6 5
4 6 30
3 30 4
2 6 4 6 1
Оптимальной перестановкой является (5,1,4,3,2).
132 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
5.8 Задачи для самостоятельного решения
5.8.1 Найдите оптимальное решение задачи о загрузке фургона при условии, что макси-
мальная грузоподьемность w = 3.
5.8.2 Найдите оптимальное решение задачи о загрузке фургон а при условии, что
максимальная грузоподьемность w = 4.
Примечание: вес и стоимость каждого предмета берутся из примера раздела 5.4.
5.8.3 Найдите оптимальное решение задачи о загрузке фургон а при условии, что
максимальная грузоподьемность w = 5.
Вес и стоимость каждого предмета приведены в таблице:
i ω
1
v
i
1 2 30
2 3 60
3 1 90
5.8.4 Найдите оптимальное решение задачи о загрузке фургон а при условии, что
максимальная грузоподьемность w = 6.
Вес и стоимость каждого предмета приведены в таблице:
i ω
1
v
i
1 2 70
2 3 80
3 1 50
Решить задачу о капиталовложениях.
5.8.5 5.8.6
A h
1
(x
1
) h
2
(x
2
) h
3
(x
3
) h
4
(x
4
)
0 0 0 0 0
1 1 2 1,5 2,5
2 2 2,5 2 3
3 2,5 5 3 4
4 6 6,5 4 5
5 7 8 5 7
A h
1
(x
1
) h
2
(x
2
) h
3
(x
3
) h
4
(x
4
)
0 0 0 0 0
1 10 12 11 13
2 12 13 14 15
3 13 14 15 16
4 15 17 16 19
5 20 18 19 21
5.8. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 133
5.8.7 5.8.8
A h
1
(x
1
) h
2
(x
2
) h
3
(x
3
) h
4
(x
4
)
0 0 0 0 0
1 5 4 3 6
2 7 6 5 8
3 9 8 7 10
4 11 10 9 12
5 13 12 11 14
A h
1
(x
1
) h
2
(x
2
) h
3
(x
3
) h
4
(x
4
)
0 0 0 0 0
1 0,3 0,28 0,15 0,25
2 0,45 0,43 0,25 0,3
3 0,65 0,6 0,42 0,43
4 0,8 0,65 0,5 0,55
5 0,9 0,7 0,65 0,55
5.8.9
A h
1
(x
1
) h
2
(x
2
) h
3
(x
3
) h
4
(x
4
)
0 0 0 0 0
1 10,5 0,25 0,15 0,4
2 0,45 0,4 0,25 0,35
3 0,65 0,55 0,4 0,45
4 0,7 0,65 0,5 0,55
5 0,9 0,8 0,6 0,65
5.8.10 Рассматривается задача календарного планирования трудовых ресурсов.
а) Пусть минимальные потребности в рабочей силе b
j
равны 6,5,3,6 и 8 для j =
1, 2, 3, 4, 5.
b) Найдите оптимальное решение задачи при условии, что y
0
= 3.
Примечание: данные, которыми располагает управляющий фермерским хозяйством
следует брать из примера раздела 5.5.
Решить задачу о кратчайшем пути:
134 Глава 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
5.8.11 5.8.12
2
3
4
4
2
2
1
5
6
1
3
5
6
7
2
3
4
4
4
2
1
5
1
3
5
6
7
7
3
9
2
6
8
Начальная вершина 1, конечная 6. Начальная вершина 1, конечная 7.
5.8.13
2
3
4
7
1
5
1
6
8
3
10
2
9
5
2
Начальная вершина 1, конечная 6.
Решить задачи о двух станках:
5.8.14 5.8.15 5.8.16
i a
i
b
i
1 4 6
2 8 10
3 1 7
4 5 2
5 4 9
i a
i
b
i
1 30 2
2
4 10
3 3 2
4 8 15
5 9 6
6 7 12
i a
i
b
i
1 3 4
2
9 1
3 2 8
4 40 10
5 5 15
6 15 6
Глава 6
Использование пакетов прикладных
программ
В данной главе рассматривается возможности использования различных прикладных
пакетов для решения типовых задач, в рамках курса теории управления. Нами были
выбраны пакеты Excel, LINGO, Maple. Пакеты Excel и Maple часто используются при
решении различных математических задач. Пакет LINGO специально разработан для
решения задач линейного программирования.
6.1 Решение оптимизационных задач средствами Excel
6.1.1 Задача линейного программирования
Постановка задачи.
Небольшая фирма изготовляет два вида красок: для внутренних и наружных работ.
Продукция обоих видов поступает в оптовую продажу. для производства красок исполь-
зуются два исходных продукта – A и B. Максимально возможные суточные запасы этих
продуктов составляют 6 и 8 т. соответственно. В таблице даны расходы A и B на 1т.
соответствующих красок.
Исходный Расход исходных продуктов Максимально возможный
продукт на тонну краски суточный запас, т
производства Тип 1 Тип 2
A 1 2 6
B 2 1 8
135
136 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ
Суточный спрос на краску первого типа никогда не превышает спроса на краску
второго типа более чем на 1т. Кроме того, спрос на краску первого типа никогда не
превышает 2т. в сутки. Оптовые цены одной тонны красок заданы: 3 тыс. для красок
второго типа, 2 тыс. для краски первого типа. Какое количество краски каждого вида
должна производить фирма, чтобы доход от реализации продукции был максимальным?
В процессе формализации получили следующую математическую модель:
max z = max(x
1
+ x
2
);
x
1
+ 2x
2
≤ 6; (6.1.1)
2x
1
+ x
2
≤ 8; (6.1.2)
−x
1
+ x
2
≤ 1; (6.1.3)
x
2
≤ 2; (6.1.4)
x
1
≥ 0; (6.1.5)
x
2
≥ 0; (6.1.6)
где x
1
– суточный объем производства краски типа 1, x
2
– суточный объем производ-
ства краски типа 2.
6.1.2 Реализация математической модели в табличной форме
Исходные данные. Оформим исходные данные задачи в виде таблицы, это повысит
удобство работы с моделью (см. рис.6.1.1).
Изменяемые ячейки. Отведем в таблице место для переменных x
1
, x
2
. (ячейки C21,
D21). Выделим область переменных рамкой – здесь мы получим оптимальный производ-
ственный план выпуска красок каждого типа.
Целевая ячейка. В ячейке J4 введем целевую функцию z = 3x
1
+ 2x
2
с помощью
формулы:
= СУММПРОИЗВ(F 6 : G6; $C$21 : $D$21).
6.1. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ EXCEL 137
Рис.6.1.1. Математическая модель в табличной форме
Ограничения. При вводе исходных данных рекомендуется помещать значки ≥, ≤, =,
между левыми и правыми частями ограничений, что в дальнейшем упростит прочтение
задачи.
Для вычисления расхода ресурса на производство красок первого и второго типа
введем в ячейку E13 формулу:
= СУММПРОИЗВ(C13 : D13; $C$21 : $D$21).
Для ресурса в ячейку E14 введем формулу:
= СУММПРОИЗВ(C14 : D14; $C$21 : $D$21).
Аналогично для ограничений на спрос 1 и спрос 2 в ячейки E15, E16 вводим формулы:
= СУММПРОИЗВ(C14 : D14; $C$21 : $D$21)
= СУММПРОИЗВ(C14 : D14; $C$21 : $D$21).
В меню Сервис находим пункт Поиск решения. (Этот пункт меню не входит в
стандартную установку Excel, если он не установлен, необходимо его установить допол-
нительно с компакт-диска MS Office.)
Рассмотрим элементы диалогового окна Поиск решения (см. Рис. 6.1.2.)
138 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ
Рис.6.1.2. Диалоговое окно Поиск решения
В поле Установить целевую ячейку дается ссылка на ячейку с целевой функцией,
для которой будет находиться максимум, минимум или заданное значений. В нашем слу-
чае целевой ячейкой является J4. Тип взаимосвязи (максимум, минимум или заданное
значение) между решением и целевой ячейкой задается путем установки переключателя
в группе Равной. В нашей задаче установим переключатель в положение Максималь-
ному значению, т.к. планируется производство, обеспечивающее максимальный доход
от реализации продукции.
В поле Изменяя ячейки указываются номера ячеек, которые должны изменяться
в процессе поиска решения задачи, т.е. ячейки, отведенные под переменные задачи. В
нашем случае введем в поле Изменяя ячейки диапазон $C$21:$D$21.
Ограничения, налагаемые на переменные задачи, отображаются в поле Ограниче-
ния. Средство поиска решений допускает ограничения в виде равенств, неравенств, а
также позволяет ввести требование целочисленности переменных. Ограничения добав-
ляются по одному. Для ввода ограничений нажмите кнопку Добавить в диалоговом
окне Поиск решения и в открывшемся диалоговом окне Добавление ограничения
(рис. 6.1.3) заполните поля.
Рис.6.1.3. Диалоговое окно Добавление ограничения
В рассматриваемом примере имеется две группы ограничений:
• ограничения на ресурсы и спрос – (6.1.1), (6.1.2), (6.1.3), (6.1.4).
6.1. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ EXCEL 139
• ограничения, накладываемые на знак переменных – (6.1.5), (6.1.6).
В поле Ссылка на ячейку введите левую часть ограничения $E$15, а в поле Огра-
ничение - правую часть, в нашем примере $H$15. С помощью раскрывающегося списка
вводится тип соотношения между левой и правой частями ограничения. В нашем приме-
ре это ≤. Нажмите кнопку Добавить в диалоговом окне Добавление ограничения и
введите оставшиеся ограничения. В результате должны быть введены следующие огра-
ничения:
$E$13 ≤ $H$13,
$E$14 ≤ $H$14,
$E$15 ≤ $H$15,
$E$16 ≤ $H$16;
Примечание: В случае, когда все ограничения одного знака, то их можно вводить
при помощи массива ячеек:
$E$13 : $E$16 ≤ $H$13 : $H$16.
Теперь нажмите кнопку Параметры в диалоговом окне Поиск решения для того
чтобы проверить, какие параметры заданы для поиска решений. В открывшемся диало-
говом окне Параметры поиска решения (рис. 6.1.4) можно изменять условия и вариан-
ты поиска решения исследуемой задачи, а также загружать и сохранять оптимизируемые
модели. Значения и состояния элементов управления, используемые по умолчанию, под-
ходят для решения большинства задач. Тем не менее, рассмотрим подробнее элементы
этого диалога:
Рис.6.1.4. Диалоговое окно Параметры поиска решений
Поле Максимальное время служит для ограничения времени, отпускаемого на
поиск решения задачи.
140 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ
Поле Предельное число итераций служит для ограничения числа промежуточ-
ных вычислений.
Поля Относительная погрешность и Допустимое отклонение служат для зада-
ния точности, с которой ищется решение. Рекомендуется после нахождения решения с ве-
личинами этих параметров, заданными по умолчанию, повторить вычисления с большей
точностью и меньшим допустимым отклонением и сравнить с первоначальным решени-
ем. Использование подобной проверки особенно рекомендуется для задач с требованием
целочисленности переменных.
Флажок Линейная модель служит для поиска решения линейной задачи оптимиза-
ции или линейной аппроксимации нелинейной задачи. В случае нелинейной задачи этот
флажок должен быть сброшен, в случае линейной задачи - установлен, т.к. в противном
случае возможно получение неверного результата.
Флажок Показывать результаты итераций служит для приостановки поиска ре-
шения и просмотра результатов отдельных итераций.
Флажок Автоматическое масштабирование служит для включения автоматиче-
ской нормализации входных и выходных значений, качественно различающихся по ве-
личине, например, при максимизации прибыли в процентах по отношению к вложениям,
исчисляемым в рублях.
Группа Оценка служит для выбора метода экстраполяции. Группа Производные
служит для выбора метода численного дифференцирования. Группа Метод служит для
выбора алгоритма оптимизации.
Вернитесь в диалог Поиск решения нажатием кнопки ОК. Нажатие кнопки Вы-
полнить открывает окно Результаты поиска решения, которое сообщает, что реше-
ние найдено (рис. 6.1.5). Для того, чтобы вывести отчет о результатах решения зада-
чи выберите в диалоговом окне требуемый тип отчета: Результаты, Устойчивость,
Пределы. Можно выбрать одновременно все типы отчетов, выделив их при нажатой
клавише Ctrl.
Рис.6.1.5. Диалоговое окно Результаты поиска решений