Тематика контрольных работ и методические указания по их выполнению (для заочной формы обучения)
Задание 1. Использование сверхурочных работ
При изготовлении изделий двух видов осуществляется последовательная обработка соответствующих заготовок на двух различных станках. Каждый станок может использоваться для производства изделий по 8 часов в сутки, однако этот фонд времени можно увеличить на 4 часа за счет сверхурочных работ. Каждый час сверхурочного времени требует дополнительных расходов: для станка 1 это долл.5, для станка 2 — долл.7. Производительность станков и продажная цена изделий приведены в таблице.
Станок |
Производительность станков (изделие/ч) |
|
|
изделие 1 |
изделие 2 |
1 |
5 |
6 |
2 |
4 |
8 |
Цена изделия |
$6 |
$4 |
Требуется определить объемы производства изделий каждого вида и уровень использования сверхурочного времени на каждом из станков, обеспечивающие получение максимальной прибыли.
Содержимое изменяемых ячеек
Определим X11, Х12 как количества изделий первого типа, выпускаемых соответственно на первом и втором станках. Аналогично,
Х21, Х22 будут определять количество изделий второго типа, выпускаемых на этих же станках.
Т1с/у, Т2с/у — время сверхурочных работ соответственно на первом и втором станках.
Ограничения
1. По времени занятости станков:
XI1/5 + Х21/6 <= 8 + Tlc/y; X12/4 + Х22/8 <= 8 + Т2с/у; Т1с/у <= 4; Т2с/у <= 4.
2. «Естественные» ограничения:
Tlc/y >м 0; Т2с/у >= 0; Х11+Х22 >= 0. Целевая функция:
Z = (Х11+ Х12)*6 + (Х21 + Х22)*4 - (5*Т1с/у + 7*Т2с/у). Максимизировать Z.
Изменяемые ячейки: D3:E4; C10:Cll.
Ограничение по времени использования станков: С10:С11=Е10:Е11.
Целевая ячейка: G13.
|
A |
В |
С |
D |
E |
F |
G |
||
1 |
Станок |
Производительность станков (изделие/час) |
Количество произведенных изделий по станкам (шт) |
|
|
||||
2 |
|
Изделие 1 |
Изделие 2 |
Изделие 1 |
Изделие 2 |
|
|
||
3 |
1 |
5 |
6 |
|
|
|
|
||
4 |
2 |
4 |
8 |
|
|
|
|
||
5 |
|
Цена изделия ($) |
Общее количество изделий (шт) |
Выручка за произведенные изделия ($) |
|||||
6 |
|
6 |
4 |
=D3+D4 |
=ЕЗ+Е4 |
=B6*D6 |
=С6*Е6 |
||
7 |
|
|
|
|
ИТОГО ($) |
=F6+G6 |
|||
8 |
Станок |
Время, связанное с производством изделий (час) |
Издержки, связанные с использованием с/у времени ($) |
||||||
9 |
Рабочее |
Сверхурочное |
Общий ресурс времени |
Максимальное сверхурочное |
Стоимость часа с/у времени ($) |
|
|||
10 |
1 |
8 |
|
=В10+С10 |
4 |
5 |
=C10*F10 |
||
11 |
2 |
8 |
|
=ВП+С11 |
4 |
7 |
=C11*F11 |
||
12 |
|
|
|
|
ИТОГО ($) |
=G10+Gll |
|||
13 |
|
|
|
Общая прибыль |
=G7-G12 |
||||
Задание 2. Модель производства с запасами
Фирма переводит свой завод на производство новых изделий, которые планируется выпускать в течение четырех месяцев. Оценки спроса на изделия в каждый из этих месяцев приведены в таблице:
Месяц поставки изделия |
1 |
2 |
3 |
4 |
Спрос (шт.) |
100 |
200 |
180 |
300 |
В каждый месяц спрос можно удовлетворить за счет:
избытка изделий, произведенных в предшествующие месяцы;
изделий, произведенных в текущем месяце;
изделий, произведенных в последующие месяцы для погашения невыполненных ранее заказов.
Затраты на изготовление одного изделия составляют долл.4. Изделие, произведенное, но не поставленное потребителю в текущем месяце, влечет за собой дополнительные издержки на хранение в размере долл.0,5 за каждый месяц хранения. Изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере долл.2 за каждый месяц недопоставки.
Объем производства меняется от месяца к месяцу по внутризаводским причинам. В рассматриваемые 4 месяца планируется следующая программа выпуска изделий.
Месяц производства изделия |
1 |
2 |
3 |
4 |
Выпуск (штук) |
50 |
180 |
280 |
270 |
Требуется уточнить (доопределить) эту программу таким образом, чтобы она обеспечивала минимальные издержки, обусловленные несогласованностью спроса и предложения (дисбалансом).
Задачи такого типа в исследовании операций известны как «транспортные задачи». Это обусловлено тем, что чаще всего такие задачи связаны с оптимизацией процессов перевозок. Вместе с тем к этому типу сводится рассматриваемая задача и многие другие, не имеющие непосредственного отношения к транспорту. Специфика этих задач заключается в использовании таблицы-матрицы, строки и столбцы которой определяют факторы дисбаланса — спрос и предложение, место производства и потребления продукции и т. п.
Пусть i определяет месяц производства изделия, a j — месяц поставки. В качестве содержимого изменяемых ячеек будем использовать Xij — количество изделий, произведенных в i-ый месяц и поставленных в j-ый.
Месяц производства (i) |
Месяц потребления (j) |
Программа выпуска изделий |
|||
1 |
2 |
3 |
4 |
||
1 |
4 |
4,5 |
5 |
5,5 |
50 |
2 |
6 |
4 |
4,5 |
5 |
180 |
3 |
8 |
6 |
4 |
4,5 |
280 |
4 |
10 |
8 |
6 |
4 |
270 |
Спрос (шт.) |
100 |
200 |
180 |
300 |
|
В таком же виде определим программу производства изделий.
Месяц производства (i) |
Месяц потребления (j) |
Программа выпуска изделий |
|||
1 |
2 |
3 |
4 |
||
1 |
|
|
|
|
|
2 |
|
|
|
|
|
3 |
|
|
|
|
|
4 |
|
|
|
|
|
Ограничения:
предложение (объемы производства):
ХИ+Х12+Х13+Х14= 50;
Х21 +Х22+Х23+Х24= 180;
ХЗ1 +Х32+ХЗЗ+Х34=280;
Х41+Х42+Х43+Х44=270.
спрос:
Х11+Х21+Х31+Х41=100;
X12+Х22+Х32+Х42=200;
Х13+Х23+ХЗЗ+Х43=180;
Х14+Х24+Х34+Х44=300.
Целевая функция:
Z= Sj Z, (XifCij) для i= 1,2,3,4; j= 1,2,3,4.
Минимизировать Z.
Структура ЭТ
|
A |
B |
C |
D |
E |
F |
1 |
Затраты на производство, хранение и штрафы (S) |
|
||||
2 |
Месяц производства |
Месяц потребления |
Программа выпуска изделий(шт.) |
|||
3 |
|
1 |
2 |
3 |
4 |
|
4 |
1 |
4 |
4,5 |
5 |
5,5 |
50 |
5 |
2 |
6 |
4 |
4,5 |
5 |
180 |
6 |
3 |
8 |
6 |
4 |
4,5 |
280 |
7 |
4 |
10 |
8 |
6 |
4 |
270 |
8 |
Спрос (шт.) |
100 |
200 |
180 |
300 |
|
9 |
Объемы производства изделий (шт.) |
|||||
10 |
Месяц производства |
Месяц потребления |
Реальный выпуск изделий (шт) |
|||
11 |
1 |
2 |
3 |
4 |
||
12 |
1 |
|
|
|
|
=СУММ(В12:Е12) |
13 |
2 |
|
|
|
|
=СУММ(В13:Е13) |
14 |
3 |
|
|
|
|
=СУММ(В14:Е14) |
15 |
4 |
|
|
|
|
=СУММ(В15:Е15) |
16 |
Спрос (шт.) |
=СУММ( В12:В15) |
=СУММ( С12:С15) |
=СУММ( D12:D15) |
=СУММ( Е12:Е15) |
|
17 |
Суммарные издержки дисбаланса $ |
=СУММПРОЙЗВ( В12:Е15; В4:Е7) |
||||
Функция СУММ() находится в списке функций системы EXCEL.
Она реализует суммирование элементов массива. Функция СУММПРОИЗВ() суммирует произведения элементов двух массивов. Она также находится в списке функций EXCEL. Например,
СУММПРОИЗВ(В12:Е15; В4:Е7) = B12*B4+C12*C4+D12*D4+E12*E4+ B13*B5+C13*C5+D13*D5+E13*E5+ B14*B6+C14*C6+D14*D6+E14*E6+ B15*B7+C15*C7+D15*D7+E15*E7.
Изменяемые ячейки: В12:Е15, целевая ячейка F17. Ограничения:
по производственной программе: F4:F7=F12:F15; по спросу: В8:Е8=В16:Е16; естественные:
В12.Е15 целые, неотрицательные.
Задание 3. Составление «скользящих» графиков
Такие графики обычно связаны с расписаниями многосменной работы предприятия в условиях нестационарного спроса на товары или услуги, связанные с деятельностью этого предприятия. Эти задачи характеризуются наличием многих ограничений, действующих в разные периоды времени. Например, спрос на общественный транспорт сильно меняется в зависимости от времени суток, спрос на продаваемые товары в магазине меняется в зависимости от дня недели и времени суток и т. д. Задача состоит в том, чтобы организовать расписание обслуживания клиентов (пассажиров, покупателей и т. п.) таким образом, чтобы издержки от неравномерности спроса были бы минимальны.
Ниже приводится пример задачи, связанной с неравномерностью покупательского спроса в течение суток.
Составление скользящего расписания при нестационарном потребительском спросе
В таблице приведено количество продавцов, которое необходимо для удовлетворения покупательского спроса в торговом зале магазина в течение суток. Требуется так организовать расписание работы продавцов, чтобы их общее количество (и соответственно расходы на оплату их труда) было минимальным.
Время суток |
Требуемое количество продавцов |
0-4 |
2 |
4-8 |
2 |
8-12 |
5 |
12-16 |
7 |
16-20 |
7 |
20-24 |
4 |
Математическая формулировка задачи
Допустим, что продавцы в магазине работают по 8 часов (в смену).
В соответствии с данными задачи количество требуемых продавцов меняется через 4 часа. Если предположить, что в первую смену работает X1 продавцов, во вторую — Х2 и т. д., то график работы продавцов можно представить следующим рисунком.
Жирные линии означают смены, которые начинаются через 4 часа и продолжаются 8 часов. Смены перекрываются, т. е., например, с 4 до 8 часов в торговом зале присутствуют (X1 + Х2) продавцов, с 8 до 12 часов — (Х2 + ХЗ) продавцов, а с 0 часов до 4 работают (X1 + Х6) продавцов. Этот «скользящий» график и образует расписание смен.
X1 •*• Х6 определяют изменяемые (варьируемые) переменные, которые следует определять из условия минимального общего количества продавцов, т.е. целевая функция в этой задаче определяется выражением:
(Xl+X2+X3+X4+X5+X6)=>min.
В качестве ограничений при этом будут выступать условия: Х1+Х6>=2; Х1+Х2>=2; Х2+Х3>=5; Х3+Х4>=7; Х4+Х5>=7; Х5+Х6>=4.
Кроме того, (X1 + X6) должны быть целыми и положительными. Такая структуризация может быть реализована, например, в следующей электронной таблице.
1 |
А |
В |
С |
D |
Е |
F |
|
Номер смены |
Начало смены (час) |
Интервал времени (час) |
Кол-во продавцов в смене |
Кол-во продавцов в зале |
Требуемое кол-во продавцов |
2 |
1 |
0 |
0-4 |
|
=D7+D2 |
2 |
3 |
2 |
4 |
4-8 |
|
=D2+D3 |
2 |
4 |
3 |
8 |
8-12 |
|
=D3+D4 |
5 |
5 |
4 |
12 |
12-16 |
|
=D4+D5 |
7 |
6 |
5 |
16 |
16-20 |
|
=D5+D6 |
7 |
7 |
6 |
20 |
20-24 |
|
=D6+D7 |
4 |
8 |
Общее количество продавцов |
=СУММ (D2:D7) |
||||
Изменяемые ячейки: СЗ:С4, ЕЗ:Е4. В двух первых размещаются вложения первого года, в двух последних — вложения второго года. Ограничения: С5 = Н6; Е5 = D5; Целевая ячейка: Н5.
Таблица выбора вариантов заданий
Ниже приведены варианты исходных данных для решения задач 1-3 в контрольных работах студентов РГТЭУ, обучающихся по очно-заочной и заочной формам.
Вариант выбирается в соответствии с порядковым номером в журнале.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
||||
Задача 1 |
||||||||||||||||||
Производительность |
1 станок |
Изделие 1 |
5 |
6 |
4 |
2 |
4 |
9 |
4 |
3 |
6 |
5 |
4 |
5 |
4 |
4 |
||
Изделие 2 |
6 |
7 |
6 |
5 |
6 |
4 |
5 |
6 |
3 |
5 |
7 |
7 |
5 |
6 |
||||
2 станок |
Изделие 1 |
4 |
2 |
8 |
3 |
8 |
8 |
6 |
4 |
7 |
6 |
6 |
3 |
6 |
4 |
|||
Изделие 2 |
8 |
4 |
2 |
7 |
3 |
5 |
7 |
7 |
4 |
4 |
6 |
6 |
8 |
5 |
||||
Цена изделия |
1 |
6 |
5 |
5 |
8 |
5 |
4 |
3 |
5 |
8 |
7 |
3 |
8 |
5 |
7 |
|||
2 |
4 |
7 |
3 |
5 |
7 |
7 |
4 |
8 |
5 |
6 |
6 |
6 |
6 |
3 |
||||
Задача 2 |
||||||||||||||||||
Спрос по месяцам поставки товаров |
1 |
210 |
280 |
350 |
220 |
250 |
210 |
230 |
310 |
440 |
290 |
270 |
150 |
130 |
120 |
|||
2 |
340 |
210 |
410 |
120 |
220 |
200 |
270 |
200 |
340 |
260 |
520 |
330 |
310 |
250 |
||||
3 |
290 |
310 |
290 |
110 |
240 |
270 |
250 |
250 |
550 |
270 |
460 |
300 |
290 |
240 |
||||
4 |
150 |
200 |
280 |
170 |
290 |
250 |
200 |
270 |
400 |
280 |
310 |
190 |
260 |
190 |
||||
Выпуск по месяцам производства товаров |
1 |
340 |
210 |
420 |
130 |
230 |
190 |
280 |
190 |
620 |
270 |
530 |
320 |
300 |
260 |
|||
2 |
200 |
270 |
150 |
210 |
240 |
200 |
120 |
300 |
130 |
280 |
260 |
140 |
120 |
110 |
||||
3 |
290 |
310 |
290 |
110 |
340 |
210 |
250 |
250 |
550 |
270 |
460 |
300 |
290 |
240 |
||||
4 |
320 |
140 |
190 |
220 |
230 |
190 |
260 |
310 |
290 |
270 |
190 |
210 |
300 |
190 |
||||
Задача 3 |
||||||||||||||||||
Требуемое количество продавцов в зависимости от смены |
1 |
1 |
0 |
1 |
2 |
0 |
0 |
0 |
2 |
1 |
1 |
1 |
1 |
3 |
3 |
|||
2 |
1 |
1 |
2 |
2 |
1 |
1 |
2 |
2 |
1 |
1 |
3 |
2 |
3 |
4 |
||||
3 |
3 |
3 |
2 |
3 |
3 |
2 |
2 |
3 |
3 |
3 |
3 |
2 |
4 |
4 |
||||
4 |
4 |
3 |
4 |
3 |
3 |
2 |
4 |
5 |
3 |
3 |
3 |
3 |
4 |
4 |
||||
5 |
4 |
5 |
4 |
3 |
4 |
5 |
4 |
6 |
6 |
4 |
5 |
5 |
7 |
7 |
||||
6 |
2 |
5 |
2 |
2 |
3 |
4 |
6 |
4 |
4 |
4 |
3 |
3 |
3 |
7 |
||||
|
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
||||
Задача 1 |
||||||||||||||||||
Производительность |
1 станок |
Изделие 1 |
9 |
3 |
6 |
4 |
9 |
5 |
6 |
12 |
5 |
4 |
6 |
4 |
12 |
3 |
||
Изделие 2 |
7 |
6 |
4 |
7 |
7 |
7 |
7 |
10 |
3 |
4 |
5 |
6 |
13 |
5 |
||||
2 станок |
Изделие 1 |
10 |
2 |
3 |
6 |
8 |
7 |
6 |
8 |
4 |
7 |
3 |
8 |
15 |
2 |
|||
Изделие 2 |
13 |
8 |
8 |
5 |
6 |
5 |
5 |
14 |
7 |
6 |
7 |
4 |
10 |
8 |
||||
Цена изделия |
1 |
7 |
6 |
7 |
3 |
8 |
6 |
6 |
8 |
8 |
5 |
10 |
3 |
3 |
6 |
|||
2 |
9 |
9 |
5 |
5 |
7 |
4 |
7 |
6 |
5 |
9 |
15 |
8 |
5 |
4 |
||||
Задача 2 |
||||||||||||||||||
Спрос по месяцам поставки товаров |
1 |
340 |
210 |
420 |
130 |
230 |
190 |
280 |
190 |
620 |
270 |
530 |
320 |
300 |
260 |
|||
2 |
200 |
270 |
150 |
210 |
240 |
200 |
120 |
300 |
130 |
280 |
260 |
140 |
120 |
110 |
||||
3 |
290 |
310 |
290 |
110 |
340 |
210 |
250 |
250 |
550 |
270 |
460 |
300 |
290 |
240 |
||||
4 |
320 |
140 |
190 |
220 |
230 |
190 |
260 |
310 |
290 |
270 |
190 |
210 |
300 |
190 |
||||
Выпуск по месяцам производства товаров |
1 |
210 |
280 |
350 |
220 |
250 |
210 |
230 |
310 |
440 |
290 |
270 |
150 |
130 |
120 |
|||
2 |
340 |
210 |
410 |
120 |
220 |
200 |
270 |
200 |
340 |
260 |
520 |
330 |
310 |
250 |
||||
3 |
290 |
310 |
290 |
110 |
240 |
270 |
250 |
250 |
550 |
270 |
460 |
300 |
290 |
240 |
||||
4 |
150 |
200 |
280 |
170 |
290 |
250 |
200 |
270 |
400 |
280 |
310 |
190 |
260 |
190 |
||||
Задача 3 |
||||||||||||||||||
Требуемое количество продавцов в зависимости от смены |
1 |
2 |
2 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
2 |
2 |
|||
2 |
2 |
3 |
1 |
1 |
2 |
2 |
2 |
1 |
1 |
2 |
3 |
4 |
2 |
3 |
||||
3 |
3 |
3 |
1 |
2 |
2 |
3 |
2 |
2 |
4 |
4 |
4 |
4 |
3 |
3 |
||||
4 |
3 |
4 |
3 |
2 |
4 |
4 |
4 |
2 |
6 |
6 |
6 |
6 |
4 |
4 |
||||
5 |
4 |
6 |
4 |
3 |
4 |
4 |
4 |
3 |
6 |
6 |
8 |
8 |
4 |
6 |
||||
6 |
4 |
5 |
4 |
2 |
2 |
3 |
3 |
2 |
4 |
4 |
4 |
5 |
3 |
4 |
||||
EXCEL позволяет решать сложные задачи со многими неизвестными и ограничениями.
К этому кругу задач относятся, например:
Определение производственного плана с целью получения максимальной прибыли от продажи произведенной продукции при наличии ограничений на ресурсы.
Выбор оптимального плана перевозок продукции из сети складов к пунктам назначения.
Оптимальное распределение ресурсов на этапе составления раздела “Оборот наличного капитала. Существующий объем и структура финансирования проекта” и другие.
Очевидно, эти задачи являются одними из основных и важнейших задач управления, возникающих в экономике. Подобные проблемы можно решать либо эвристическим методом (по некоторым принятым правилам, рекомендуемым экспертом), либо оптимизационными методами.
В отличие от эвристического метода, при котором для каждого объекта задается строго определенная величина, в процессе разработки оптимального метода для каждого объекта задаются не конкретные значения, а нижние и верхние граничные условия. Цель проводимой оптимизации - максимизация или минимизация значения функций нескольких переменных, определенных на множестве с линейными и нелинейными ограничениями.
Решение поставленной задачи производится на основе составляемой математической модели объекта. Основная трудность - выполнить постановку задачи так, чтобы EXCEL нашел осмысленное решение. То есть, необходимы определенные математические знания и накопленный опыт по предметной области для того, чтобы сформировать набор входных данных и ограничения, которые действительно отражают суть проблемы.
В EXCEL для решения подобных задач используется инструмент SOLVER. SOLVER представляет собой мощный вспомогательный инструмент для выполнения сложных вычислений. Она позволяет по заданному значению результата находить множество значений переменных, удовлетворяющих некоторым указанным ограничениям.
Изучение возможностей надстройки целесообразно начать с использования команды Подбор параметра, позволяющей найти подходящее значение одной переменной, при котором формула принимает нужное значение. К несчастью, большая часть задач, с которыми мы сталкиваемся в научной и финансовой деятельности, не столь просты. Зачастую значения формул зависят от большого числа переменных, и при этом чаще всего требуется отыскать наилучшее, оптимальное решение (например, дающее максимальную прибыль или обеспечивающее минимальные затраты), удовлетворяющее при этом целому ряду дополнительных условий на значения используемых параметров. Для решения таких задач, намного более сложных, чем только что рассмотренные, требуется и намного более мощный инструмент. Именно таким могучим оружием, позволяющим решить сложные задачи, требующие применения математического аппарата линейного и нелинейного программирования и методов исследования операций и является имеющаяся в Excel надстройка "Поиск решения".
В таком небольшом параграфе мы можем лишь слегка затронуть эту довольно сложную тему, ограничившись первоначальным знакомством и разбором нескольких типичных примеров применения. Подробное рассмотрение надстройки "Поиск решения" само по себе заслуживает отдельной книги (или по крайней мере большой главы) и требует серьезного разбора используемого математического аппарата. К сожалению, это выходит за рамки нашей книги.
Впрочем, для того чтобы использовать надстройку "Поиск решения", вовсе не обязательно быть знатоком методов линейного программирования и исследования операций — нужно лишь понимать, какие задачи могут быть решены этими методами. От пользователя требуется умение с помощью серии диалоговых окон правильно сформулировать условия задачи, и если решение существует, то "Поиск решения" отыщет его.
Отметим, что в основе надстроек "Поиск решения" и "Подбор параметра" лежат итерационные методы. Однако надстройка "Поиск решения" использует гораздо более сложные методы, подбор параметра. Укажем здесь некоторые отличия этих двух инструментов:
"Поиск решения" позволяет использовать одновременно большое количество (в общей сложности до 200) изменяемых ячеек;
"Поиск решения" позволяет задавать ограничения для изменяемых ячеек. Например, при поиске решения, обеспечивающего максимальную прибыль, вы можете задать дополнительные условия, скажем, потребовать, чтобы при этом общий доход находился в диапазоне между 20% и 30% , или чтобы расходы не превосходили 1 000 000 рублей. Подобного рода условия называются ограничениями для решаемой задачи.
"Поиск решения" доставляет не заранее известный конкретный результат для целевой функции, как в случае использования метода подбора параметра, но отыскивает оптимальное (минимальное или максимальное), т.е. наилучшее из возможных решение.
Наконец, для сложных задач "Поиск решения" может генерировать множество различных решений. При этом вы можете сохранить варианты этих решений, определив для них соответствующие сценарии (для работы со сценариями в Excel имеется еще один полезный инструмент — Диспетчер сценариев.
Задачи, для решения которых можно воспользоваться надстройкой "Поиск решения", имеют ряд общих свойств:
Имеется единственная целевая ячейка, содержащая формулу, значение которой должно быть сделано максимальным, минимальным или же равным какому-то конкретному значению. Эта формула может, например, служить для вычисления чистой прибыли или общих транспортных расходов.
Формула в этой целевой ячейке содержит ссылки (прямые или косвенные) на ряд изменяемых ячеек (содержащих неизвестные, или переменные решаемой задачи). Поиск решения заключается в том, чтобы подобрать такие значения этих переменных, которые бы давали оптимальное значение для формулы в целевой ячейке. Изменяемые ячейки могут содержать, например, себестоимость или цену товаров, транспортные тарифы или налоговые ставки.
Кроме того, может быть задано некоторое количество ограничений — условий или соотношений, которым должны удовлетворять некоторые из изменяемых ячеек. Например, можно потребовать, чтобы общие затраты не превосходили 100 000 000 рублей или чтобы затраты на рекламную кампанию составляли от 10 до 15 % от общих расходов.
Тем, кто знаком с формулировками задач линейного программирования или исследования операций, перечисленные выше свойства покажутся хорошо знакомыми. Какие же задачи могут быть сформулированы подобным образом? Круг подобных задач удивительно широк. Приведем лишь несколько классических примеров.
Транспортная задача. Ее формулировка состоит в следующем: имеется несколько пунктов производства и пунктов потребления некоторого продукта. Для каждого из пунктов производства задан объем производства, а для каждого пункта потребления — объем потребления. Известна также стоимость перевозки из каждого пункта производства в каждый пункт потребления единицы продукта. Требуется составить план перевозок продукта, в котором все пункты потребления были бы обеспечены необходимыми продуктами, ни из какого пункта производства не вывозилось бы продуктов больше, чем там производится, а стоимость перевозки была бы минимальной.
Задача о выборе оптимального меню. Имеется набор некоторых продуктов, обладающих некоторой калорийностью, а также известны количества белков, жиров и углеводов для каждого из этих продуктов и их стоимость. Требуется составить меню, удовлетворяющее требованиям калорийности и сбалансированности питательных продуктов, и при этом минимизирующее суммарную стоимость1.
Задача о назначениях. Имеется несколько должностей и соответствующее количество претендентов на эти должности. Назначение i-того претендента на j-тую должность связано с затратами C[i,j]. Требуется распределить претендентов по должностям так, чтобы суммарные затраты были бы минимальны.
Задача о выборе портфеля ценных бумаг. Вкладчик хочет выбрать портфель ценных бумаг, при этом известны средние значения доходов от каждого вида ценных бумаг и ожидаемая дисперсия этих доходов. Требуется отыскать оптимальный портфель, обеспечивающий максимальный ожидаемый доход при минимальном рассеянии, и, следовательно, минимальном риске.
Задачи линейной алгебры. С помощью этих же методов можно решать различные системы линейных (и не только линейных) уравнений.
Лучше всего понять возможности надстройки "Поиск решения" может помочь разбор конкретных примеров решения подобных классических задач. В состав Microsoft Office входит специальная рабочая книга с примерами — …\EXCEL\EXAMPLES\SOLVER\SOLVSAMP.EXE, правда пояснения и комментарии очень кратки и касаются в основном размещения данных и формул в ячейках рабочего листа, а не постановки решаемых задач. Новичку разобраться в этих примерах весьма непросто, однако в случае успеха ваши усилия будут вознаграждены. Попробуем помочь делу и подробно прокомментировать решение одной из задач, представленных в этой рабочей книге (см. лист "Поиск решения" в рабочей книге SOLVSAMP.XLS). Мы лишь слегка "причесали" эту задачу и подробно описали ее постановку и все необходимые действия. Рекомендуем внимательно ознакомиться и с остальными примерами, имеющимися в рабочей книге SOLVSAMP.XLS.
Основы работы в ППП
Назначение и возможности надстроек "Пакет анализа" и "Поиск решения" Microsoft Excel. Знакомство с загрузкой и правилами работы с ними.
Указания.
Поиск решений является частью блока задач, который иногда называют анализ "что-если". Процедура поиска решения позволяет найти оптимальное значение формулы содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки.
Процедуру поиска решения можно использовать для определения значения влияющей ячейки, которое соответствует экстремуму зависимой ячейки — например можно изменить объем планируемого бюджета рекламы и увидеть, как это повлияет на проектируемую сумму расходов.
Пример поиска решения
В приведенном ниже примере объем продаж в каждом квартале зависит от уровня рекламы, что косвенно определяет сумму доходов, издержки, а также прибыль. Чтобы найти максимальную возможную сумму общего дохода, процедура поиска решения может повышать ежеквартальные расходы на рекламу (ячейки B5:C5), пока общие расходы не превысят ограничения в 20 тысяч (ячейка F5). Значения во влияющих ячейках служат для вычисления дохода за каждый квартал, поэтому они связаны с формулой в целевой ячейке F7, =СУММА(Q1 Прибыль:Q2 Прибыль).
1 --- Изменяемые ячейки
2 --- Ячейка с ограничениями
3 --- Целевая ячейка
После выполнения процедуры получены следующие значения:
Примеры расчетов с использованием процедуры поиска решения
В составе Microsoft Excel в папке Office\Samples находится книга с примерами (Solvsamp.xls) использования процедуры поиска решения (Solver.xls).
Примеры, содержащиеся в книге Solvsamp.xls, помогут разрешить ваши вопросы. Чтобы применить любой из шести примеров: «Структура производства», «Транспортная задача», «График занятости», «Управление капиталом», «Портфель ценных бумаг» и «Проектирование цепи», — откройте книгу, перейдите к нужному листу и выберите команду «Поиск решения» в меню «Сервис». В примерах уже подобраны целевая и влияющие ячейки, а также ограничения.
Алгоритм и методы поиска решения
Средство поиска решения Microsoft Excel использует алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University).
Алгоритмы симплексного метода и метода «branch-and-bound» для решения линейных и целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc. Чтобы получить более подробные сведения об используемых алгоритмах оптимального поиска, обратитесь по адресу:
Frontline Systems, Inc. P.O. Box 4288 Incline Village, NV 89450-4288 (775) 831-0300 Адрес в Интернете: http://www.frontsys.com Электронная почта: info@frontsys.com
Авторские права на исполняемый код надстройки Microsoft Excel поиска решения принадлежат Frontline Systems, Inc. и Optimal Methods, Inc.
Добавление, изменение и удаление ограничения на поиск решения
В меню «Сервис» выберите команду «Поиск решения».
Если команда «Поиск решения» отсутствует в меню «Сервис», загрузите соответствующую надстройку.
В меню «Сервис» выберите команду «Надстройки».
Нажмите кнопку «Обзор», чтобы найти надстройку, которой нет в окне «Список надстроек».
Установите в окне «Список надстроек» флажок той надстройки, которую необходимо загрузить, а затем нажмите кнопку «OK».
Следуйте инструкциям программы установки, если они имеются.
Добавьте или измените ограничения.
Инструкции
Добавление ограничения
В разделе «Ограничения» диалогового окна «Поиск решения» нажмите кнопку «Параметры».
В поле «Ссылка на ячейку» введите адрес или имя ячейки, на значение которой накладываются ограничения.
Выберите из раскрывающегося списка условный оператор ( <=, =, >=, цел или двоич ), который должен располагаться между ссылкой и ограничение. Если выбрано цел, в поле «Ограничение» появится «целое». Если выбрано двоич, в поле «Ограничение» появится «двоичное».
В поле «Ограничение» введите число, ссылку на ячейку или ее имя либо формулу.
Выполните одно из следующих действий.
Чтобы принять ограничение и приступить к вводу нового, нажмите кнопку «Добавить».
Чтобы принять ограничение и вернуться в диалоговое окно «Поиск решения», нажмите кнопку «OK».
Примечания
Условные операторы типа цел и двоич можно применять только при наложении ограничений на изменяемые ячейки.
Флажок «Линейная модель» в диалоговом окне «Параметры поиска решения» позволяет задать любое количество ограничений. При решении нелинейных задач на значения изменяемых ячеек можно наложить более 100 ограничений, в дополнение к целочисленным ограничениям на переменные.
Изменение и удаление ограничений
В списке «Ограничения» диалогового окна «Поиск решения» укажите ограничение, которое требуется изменить или удалить.
Выберите команду «Изменить» и внесите изменения либо нажмите кнопку «Удалить».
Изменение способа поиска решения
В меню «Сервис» выберите команду «Поиск решения».
Если команда «Поиск решения» отсутствует в меню «Сервис», установите надстройку «Поиск решения».
Инструкции
В меню «Сервис» выберите команду «Надстройки».
Нажмите кнопку «Обзор», чтобы найти надстройку, которой нет в окне «Список надстроек».
Установите в окне «Список надстроек» флажок той надстройки, которую необходимо загрузить, а затем нажмите кнопку «OK».
Следуйте инструкциям программы установки, если они имеются.
В диалоговом окне «Поиск решения» нажмите кнопку «Параметры».
В диалоговом окне «Параметры поиска решения» задайте один или несколько следующих параметров.
Время поиска и количество итераций
В поле «Максимальное время» введите интервал в секундах, чтобы ограничить время поиска решения задачи.
В поле «Предельное число итераций» введите максимальное количество количество итераций, отводимое на достижение конечного результата.
Примечание. При достижении границы отведенного временного интервала или при выполнении отведенного числа итераций на экране появляется диалоговое окно «Текущее состояние поиска решения».
Относительная погрешность
В поле «Относительная погрешность» введите необходимую погрешность — чем меньше введенное число, тем выше точность результатов.
Допустимое отклонение
В поле «Допустимое отклонение» введите необходимый допуск.
Сходимость
В поле «Сходимость» введите значение относительного изменения, при достижении которого в последних пяти итерациях поиск решения прекращается — чем меньше это значение, тем выше точность результатов.
Примечание. Для получения дополнительных сведений об этих параметрах нажмите кнопку «Справка» в данном диалоговом окне.
Нажмите кнопку «OK».
В диалоговом окне «Поиск решения» нажмите кнопку «Выполнить» или «Закрыть».
Создание отчета о поиске решения
Сформулируйте задачу и найдите решение.
Инструкции
В меню «Сервис» выберите команду «Поиск решения».
Если команда «Поиск решения» отсутствует в меню «Сервис», установите надстройку «Поиск решения».
Инструкции
В меню «Сервис» выберите команду «Надстройки».
Нажмите кнопку «Обзор», чтобы найти надстройку, которой нет в окне «Список» надстроек.
Установите в окне «Список» надстроек флажок той надстройки, которую необходимо загрузить, а затем нажмите кнопку «OK».
Следуйте инструкциям программы установки, если они имеются.
В поле «Установить целевую ячейку» введите ссылку на ячейку или имя конечной ячейки. Конечная ячейка должна содержать формулу.
Выполните одно из следующих действий:
чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному значению;
чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение минимальному значению;
чтобы установить значение в конечной ячейке равным некоторому числу, установите переключатель в положение значению и введите в соответствующее поле требуемое число.
В поле «Изменяя ячейки», введите имена или ссылки на изменяемые ячейки, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с конечной ячейкой. Допускается задание до 200 изменяемых ячеек.
Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку «Предположить».
В поле «Ограничения» введите все ограничения, накладываемые на поиск решения.
Инструкции
Добавление ограничения
В разделе «Ограничения» диалогового окна «Поиск решения» нажмите кнопку «Параметры».
В поле «Ссылка на ячейку» введите адрес или имя ячейки, на значение которой накладываются ограничения.
Выберите из раскрывающегося списка условный оператор ( <=, =, >=, цел или двоич ), который должен располагаться между ссылкой и ограничение. Если выбрано цел, в поле «Ограничение» появится «целое». Если выбрано двоич, в поле «Ограничение» появится «двоичное».
В поле «Ограничение» введите число, ссылку на ячейку или ее имя либо формулу.
Выполните одно из следующих действий.
Чтобы принять ограничение и приступить к вводу нового, нажмите кнопку «Добавить».
Чтобы принять ограничение и вернуться в диалоговое окно «Поиск решения», нажмите кнопку «OK».
Примечания
Условные операторы типа цел и двоич можно применять только при наложении ограничений на изменяемые ячейки.
Флажок «Линейная модель» в диалоговом окне «Параметры поиска решения» позволяет задать любое количество ограничений. При решении нелинейных задач на значения изменяемых ячеек можно наложить более 100 ограничений, в дополнение к целочисленным ограничениям на переменные.
Изменение и удаление ограничений
В списке «Ограничения» диалогового окна «Поиск решения» укажите ограничение, которое требуется изменить или удалить.
Выберите команду «Изменить» и внесите изменения либо нажмите кнопку «Удалить».
Нажмите кнопку «Выполнить» и выполните одно из следующих действий:
чтобы сохранить найденное решение на листе, выберите в диалоговом окне «Результаты поиска решения» вариант «Сохранить найденное решение»;
чтобы восстановить исходные данные, выберите вариант «Восстановить исходные значения».
Совет
Чтобы прервать поиск решения, нажмите клавишу ESC. Лист Microsoft Excel будет пересчитан с учетом найденных значений влияющих ячеек.
Если решение будет найдено, выберите тип отчета в списке «Отчеты» и нажмите кнопку «ОК».
Отчет будет помещен на новый лист книги.
Постановка задачи и оптимизация модели с помощью процедуры поиска решения
В меню «Сервис» выберите команду «Поиск решения».
Если команда «Поиск решения» отсутствует в меню «Сервис», установите надстройку «Поиск решения».
Инструкции
В меню «Сервис» выберите команду «Надстройки».
Нажмите кнопку «Обзор», чтобы найти надстройку, которой нет в окне «Список надстроек».
Установите в окне «Список надстроек» флажок той надстройки, которую необходимо загрузить, а затем нажмите кнопку «OK».
Следуйте инструкциям программы установки, если они имеются.
В поле «Установить целевую ячейку» введите ссылку на ячейку или имя конечной ячейки. Конечная ячейка должна содержать формулу.
Выполните одно из следующих действий:
чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение «максимальному значению»;
чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение «минимальному значению»;
чтобы установить значение в конечной ячейке равным некоторому числу, установите переключатель в положение «значению» и введите в соответствующее поле требуемое число.
В поле «Изменяя ячейки» введите имена или ссылки на изменяемые ячейки, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с конечной ячейкой. Допускается задание до 200 изменяемых ячеек.
Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку «Предположить».
В поле «Ограничения» введите все ограничения, накладываемые на поиск решения.
Инструкции
Добавление ограничения
В разделе «Ограничения» диалогового окна «Поиск решения» нажмите кнопку «Параметры».
В поле «Ссылка на ячейку» введите адрес или имя ячейки, на значение которой накладываются ограничения.
Выберите из раскрывающегося списка условный оператор ( <=, =, >=, цел или двоич ), который должен располагаться между ссылкой и ограничение. Если выбрано цел, в поле «Ограничение» появится «целое». Если выбрано двоич, в поле «Ограничение» появится «двоичное».
В поле «Ограничение» введите число, ссылку на ячейку или ее имя либо формулу.
Выполните одно из следующих действий.
Чтобы принять ограничение и приступить к вводу нового, нажмите кнопку «Добавить».
Чтобы принять ограничение и вернуться в диалоговое окно «Поиск решения», нажмите кнопку «OK».
Примечания
Условные операторы типа цел и двоич можно применять только при наложении ограничений на изменяемые ячейки.
Флажок «Линейная модель» в диалоговом окне «Параметры поиска решения» позволяет задать любое количество ограничений. При решении нелинейных задач на значения изменяемых ячеек можно наложить более 100 ограничений, в дополнение к целочисленным ограничениям на переменные.
Изменение и удаление ограничений
В списке «Ограничения» диалогового окна «Поиск решения» укажите ограничение, которое требуется изменить или удалить.
Выберите команду «Изменить» и внесите изменения либо нажмите кнопку «Удалить».
Нажмите кнопку «Выполнить» и выполните одно из следующих действий:
чтобы сохранить найденное решение на листе, выберите в диалоговом окне «Результаты поиска решения» вариант «Сохранить найденное решение»;
чтобы восстановить исходные данные, выберите вариант «Восстановить исходные значения».
Совет
Чтобы прервать поиск решения, нажмите клавишу ESC. Лист Microsoft Excel будет пересчитан с учетом найденных значений влияющих ячеек.
Загрузка модели оптимизации
Перед тем как использовать данную процедуру, необходимо сохранить хотя бы одну модель.
В меню «Сервис» выберите команду «Поиск решения».
В диалоговом окне «Поиск решения» нажмите кнопку «Параметры».
В диалоговом окне «Параметры поиска решения» нажмите кнопку «Загрузить модель».
Введите ссылку на весь диапазон ячеек с областью модели.
Применение стандартных значений параметров поиска решений
В меню «Сервис» выберите команду «Поиск решения».
Нажмите кнопку «Восстановить».
Сохранение модели оптимизации
Сформулируйте задачу и найдите решение.
Инструкции
В меню «Сервис» выберите команду «Поиск решения».
Если команда «Поиск решения» отсутствует в меню «Сервис», установите надстройку «Поиск решения».
Инструкции
В меню «Сервис» выберите команду «Надстройки».
Нажмите кнопку «Обзор», чтобы найти надстройку, которой нет в окне «Список надстроек».
Установите в окне «Список надстроек» флажок той надстройки, которую необходимо загрузить, а затем нажмите кнопку «OK».
Следуйте инструкциям программы установки, если они имеются.
В поле «Установить целевую ячейку» введите ссылку на ячейку или имя конечной ячейки. Конечная ячейка должна содержать формулу.
Выполните одно из следующих действий:
чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение «максимальному значению»;
чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение «минимальному значению»;
чтобы установить значение в конечной ячейке равным некоторому числу, установите переключатель в положение «значению» и введите в соответствующее поле требуемое число.
В поле «Изменяя ячейки» введите имена или ссылки на изменяемые ячейки, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с конечной ячейкой. Допускается задание до 200 изменяемых ячеек.
Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку «Предположить».
В поле «Ограничения» введите все ограничения, накладываемые на поиск решения.
Нажмите кнопку «Выполнить» и выполните одно из следующих действий:
чтобы сохранить найденное решение на листе, выберите в диалоговом окне «Результаты поиска решения» вариант «Сохранить найденное решение»;
чтобы восстановить исходные данные, выберите вариант «Восстановить исходные значения».
Совет
Чтобы прервать поиск решения, нажмите клавишу ESC. Лист Microsoft Excel будет пересчитан с учетом найденных значений влияющих ячеек.
В меню «Сервис» выберите команду «Поиск решения».
Нажмите кнопку «Параметры».
Нажмите кнопку «Сохранить модель».
Введите ссылку на верхнюю ячейку столбца, в котором следует разместить модель оптимизации.
Совет
Значения элементов управления диалогового окна «Поиск решения» записываются на лист при выполнении команды «Сохранить» в меню «Файл». Чтобы использовать на листе несколько моделей оптимизации, нужно сохранить их с помощью кнопки «Сохранить модель».
Просмотр промежуточных результатов поиска решения
Сформулируйте задачу.
В диалоговом окне «Поиск решения» нажмите кнопку «Параметры».
Чтобы просмотреть значения всех найденных решений, в диалоговом окне «Параметры поиска решения» установите флажок «Показывать результаты итераций», а затем нажмите кнопку «ОК».
В диалоговом окне «Поиск решения» нажмите кнопку «Выполнить».
В диалоговом окне «Текущее состояние поиска решения» выполните одно из следующих действий.
Чтобы остановить поиск решения и вывести на экран диалоговое окно «Результаты поиска решения», нажмите кнопку «Стоп».
Чтобы выполнить следующую итерацию и просмотреть ее результаты, нажмите кнопку «Продолжить».