2190
.pdfхранять каждый сценарий и вводить его имя, соответствующее текущему значению сырья.
Рис. 32
Для представления результатов решения вызывается пункт меню Сервис, Сценарии и в появившемся диалоговом окне Диспетчер сценариев (рис. 33) выбирается пункт Отчет.
Рис. 33
100
При выборе в диалоговом окне Отчет по сценарию (рис. 34) типа отчета Структура создается итоговый сценарий (рис. 35), который размещается на отдельном листе с названием “Структура сценария”.
Рис. 34
Рис. 35
Для удобства дальнейшей работы полученный сценарий можно отредактировать и представить следующем виде:
Рис. 36
101
Для наглядного представления результатов параметрического анализа построим гистограммы:
Оптимальное решение
160 |
|
|
|
|
|
|
|
|
140 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
140 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
120 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
110 |
|
|
110 |
|
|
Прод1 |
||||||||||||
|
|
100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Прод2 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
80 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Прод3 |
80 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
60 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Прод4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
0 |
|
|
сырье=100 |
сырье=150 |
сырье=200 сырье=250 |
сырье=300 |
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
Значение прибыли |
|
|
|
|
|
|
||||||||
|
|
Прибыль |
|
|
|
|
|
|
|
|||||||||
1400 |
|
|
|
|
|
|
|
|
|
|
|
1320 |
1320 |
|
|
|||
|
|
|
|
|
|
|
|
|
1240 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
1200 |
|
|
|
|
|
|
|
1040 |
|
|
|
|
|
|
|
|
|
|
1000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
800 |
|
|
|
|
700 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
600 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
400 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
200 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
сырье=100 сырье=150 сырье=200 сырье=250 сырье=300 |
||||||||||||||||
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 37
Решения по заказу
При решении по заказу пользователь задает значения тех величин, которые он хотел бы видеть в оптимальном решении. Такие задачи могут быть трех видов:
назначение величины целевой функции; назначение величин искомых переменных; назначение величин используемых ресурсов.
102
Рассмотрим возможные варианты на примере решаемой задачи производственного планирования.
Впервом случае для получения результата необходимо
вячейку, соответствующую целевой функции (F6), ввести требуемую величину, а затем, вызвав программу Поиск решения, решить задачу по рассмотренной выше схеме.
Во втором случае в ячейки B4:D4, соответствующие нижним границам значений переменных задачи, вводятся требуемые значения переменных. Далее вызывается программа Поиск решения, в появившемся диалоговом окне осуществляется переход к окну Ограничения, курсор устанавливается на ограничение $B$3>=$B$4, вызывается команда Изменить и вместо знака >= вводится знак =. Аналогичные изменения производятся и с ограничениями $C$3>=$C$4, $D$3>=$D$4, $E$3>=$E$4, после чего осуществляется решение задачи.
Втретьем случае в таблицу с исходными данными вводятся требуемые значения используемых ресурсов (при этом необходимое значение для трудовых ресурсов заносится в ячейку F9, для сырья - в ячейку F10, для финансов - в ячейку F11) и задача решается обычным образом.
Решение при условных исходных данных
Некоторые задачи оптимизации можно решать с помощью логических функций, используя условие ЕСЛИ . Такие задачи будем называть задачами оптимизации при условных
исходных данных. Решение этих задач |
начинается с опти- |
мизации условной целевой функции . |
Основной логической |
функцией, применяемой при такой оптимизации , является логическая функция ЕСЛИ , имеющая формат записи: =ЕСЛИ (A;C3;C4), где А - логическое условие или адрес ячейки с условием; С3 - адрес ячейки , где записана целевая функция, по которой производится оптимизация при выполнении условия А; С4 - адрес ячейки , где записана целевая функция, которая оптимизируется при невыполнении условия А.
Данная функция может быть введена с помощью Мастера функций. Пример рассматриваемой задачи производ-
103
ственного планирования с условной целевой функцией приведен на рис. 38. На рис. 39 представлено решение данной задачи.
Рис. 38
Рис. 39
В общем случае условные целевые функции могут быть составными и для записи условий включать , кроме логической функции ЕСЛИ, логические функции И и ИЛИ, которые вводятся в формате И(A;B) , ИЛИ(A;B) , где А , В - назначаемые условия .
Формат записи условных вычислений при этом будет иметь вид :
=ЕСЛИ (И(A;B); адрес ЦФ1; адрес ЦФ2), =ЕСЛИ (ИЛИ(A;B); адрес ЦФ1; адрес ЦФ2).
104
При решении практических задач довольно часто могут возникать логические цепочки. EXCEL допускает применение функции ЕСЛИ в цепочке до 7 раз.
Аналогично можно вводить условные ограничения. Условные исходные данные для левых частей (ЛЧ) ограничений вводятся в формате :
=ЕСЛИ (условие; адрес ЛЧ1; адрес ЛЧ2), для правых частей (ПЧ) ограничений формат ввода
аналогичен предыдущему, только вместо ЛЧ1 и ЛЧ2 записываются ПЧ1и ПЧ2.
В одной и той же задаче условия для целевой функции, левых и правых частей ограничений могут вводиться одновременно.
ЛЕКЦИЯ 10 ПРИКЛАДНЫЕ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО
ПРОГРАММИРОВАНИЯ
Задачей целочисленного линейного программирования
(ЗЦЛП) называется задача линейного программирования, в которой на переменные наложено требование целочисленности. При этом если все переменные задачи должны принимать целочисленные значения, задача называется полностью целочис-
ленной, иначе – частично целочисленной. Если множество до-
пустимых решений задачи является конечным, то задача называется комбинаторной. В-частности, к классу комбинаторных относятся задачи булевой оптимизации, в которых переменные могут принимать только два значения: 0 или 1.
Задача о раскрое.
Для изготовления заготовок D1,…,Dm имеется n способов раскроя материала A1,…,An. aij -количество заготовок i-го
типа, получаемых из единицы материала при способе Aj. Имеется D единиц материала. При раскрое единицы материала по способу Aj имеются отходы площадью Cj . Надо произвести не
105
менее bi заготовок i-го типа и выполнить план с минимизаци-
ей отходов.
|
|
|
|
|
|
|
|
Таблица 12 |
||
Виды |
Способы раскроя |
|
|
|
|
План |
|
|||
заготовок |
A1 |
|
A2 |
|
… |
An |
|
|
произ |
|
|
|
|
|
|
|
|
|
|
водства |
|
D1 |
а11 |
a21 |
a12 |
a22 |
... ... |
a1n |
a2 n |
|
b1 |
|
D2 |
... |
am1 |
... |
am2 |
... ... |
... |
amn |
|
b2 |
|
… |
|
|
|
|
|
|
|
|
... |
|
Dm |
|
|
|
|
|
|
|
|
bm |
|
Отходы |
C1 |
|
c2 |
|
… |
cn |
|
|
|
|
Пустьxj - количество единиц материала, раскраиваемого
по j-му способу.
Математическая модель задачи запишется следующим образом:
n |
|
|
|
|
Cj xj |
min; |
|
|
|
j 1 |
|
|
|
|
n |
|
|
|
|
aij xj |
bi; |
i |
1,m |
; |
j 1 |
|
|
|
|
n |
|
|
|
|
xj D;
j1
xj 0, j 1,n,xj целые.
Задача о ранце. Имеются предметы n видов, для каждого предмета j-го вида (j=1,n) известны его объем a j 0 и сто-
имость cj 0. Необходимо определить такой набор предме-
тов, суммарный объем которых не превышал бы заданного числа b, а суммарная ценность была бы максимальной. Эта задача интерпретируется как задача загрузки ранца объема b и
называется одномерной задачей о ранце.
Введем целочисленные переменные x j(j 1,n), зна-
чения которых характеризует количество предметов j-го вида,
106
помещенных в ранец. Тогда математическая модель данной задачи имеет вид:
n
C jx j max ;
j 1
n
a jx j b;
j 1
x j 0, x j - целое .
Если ограничениями могут быть не только объем ранца, но и другие его характеристики bi , то получим многомерную задачу о ранце.
n
C j xj max ;
j1 n
aij xj bi ,i 1,m;
j 1
xj 0, xj - целое.
В случае, если количество предметов j-го вида ограничено и равно dj, к задаче добавляется ограничение x j dj.
Если dj=1, то получим задачу о ранце с булевыми перемен-
ными. Тогда x j {0,1}, причем xj 1, если j-й предмет по-
мещен в ранец, xj 0 в противном случае.
К задаче о ранце сводится широкий класс задач дискретной оптимизации с ограниченными ресурсами.
Пример 1. Для оценки работоспособности систем перед их эксплуатацией производится проверка их функционирования. При проверке контролируются отдельные параметры системы, каждый из которых характеризуется вероятностью отказа проверяемых элементов qj и временем контроля t j. Так
как допустимое время контроля всей системы T ограничено, то для проверки необходимо выбрать параметры, контролирующие наиболее ненадежные элементы и требующие для контроля наименьшего времени.
107
Пусть n – общее количество параметров. Введем альтернативные булевы переменные:
1, |
есливыбирается j-йпараметр |
||
xj |
0 |
впротивномслучае |
|
|
|||
Тогда математическую модель задачи можно сформу- |
|||
лировать как одномерную задачу о ранце: |
|||
|
n |
|
|
|
q jx j |
max; |
|
|
j 1 |
|
|
|
n |
|
|
|
t jx j |
T; |
|
|
j 1 |
|
|
|
x j |
{0,1}. |
Задача о назначениях. Линейная задача о назначениях .
Имеется n исполнителей и n видов работ, которые они могут выполнять. ПустьCij - производительность i-го испол-
нителя при выполнении j работы. Каждый исполнитель может выполнять один вид работ, а каждый вид работ может быть выполнен одним исполнителем. Требуется таким образом распределить исполнителей по видам работ, чтобы общая производительность была максимальной.
Введем альтернативные переменные xij:
1, |
еслиi-йисполнитель назначаетсяна j-ю работу |
|
xij |
0 |
в противном случае |
|
Тогда математическая модель задачи имеет вид:
108
n n
Cij xij max;
i 1 |
j 1 |
|
|
|
|
|
n |
|
|
|
|
|
|
xij |
1,i |
1,n; |
|
|
||
j 1 |
|
|
|
|
|
|
n |
|
|
|
|
|
|
xij |
1, j |
|
|
|||
1,n; |
||||||
i 1 |
|
|
|
|
|
|
xij {0,1}.
Иногда задача о назначениях формулируется как задача минимизации, если в качестве cij выбирается время, затрачен-
ное i-м исполнителем на выполнение j-й работы. Необходимо заметить, что условие целочисленности
переменных в задаче о назначениях можно не накладывать, т.к. эта задача является частным случаем транспортной задачи и при целочисленности правых частей ограничений целочисленность решения обеспечивается автоматически.
К задаче о назначениях сводится широкий круг задач дискретной оптимизации (распределение исполнителей по видам работ, закрепление за станками операций, распределение задач между различными ЭВМ, назначение претендентов на вакантные должности при формировании штатного расписания и т.д).
Пример 2. При передаче сообщений по каналу с шумом необходимо каждой букве передаваемого алфавита поставить в соответствие букву принимаемого таким образом, чтобы сумма вероятностей правильности принимаемых букв была бы максимальна.
Пусть pij- вероятность соответствия принимаемой j-й
буквы передаваемой i-й букве. Введем альтернативные переменные:
1, |
если j-япринимаемая буква соответствует |
|
|
|
|
xij i-йпередаваемой |
|
|
|
в противном |
случае |
0 |
109