Методичка по информационным технологиям

51

Пусть fn(i) – оптимальный ожидаемый доход за этапы n, n+1, ..., N при условии, что система находится в состоянии i в начале n-й недели.

Тогда:

Где fN+1(j) = 0 при всех j. Пусть

,

тогда

В ячейку I5 введена формула:

=СУММПРОИЗВ(В5:D5;Е5:G5),

В ячейки диапазона I12:I17 последовательно введены формулы:

=I5

=I8

=I6

=I9

=I7

=I10,

упорядочивающие ожидаемые доходы по следующим парам: первое состояние без рекламы и при ее наличии, второе состояние без рекламы и при ее наличии и третье состояние без рекламы и при ее наличии.

В ячейки диапазона В13:В15 введены формулы:

=МАКС(I12:I13) =МАКС(I14:I15)

=МАКС(I16:I17),

определяющие максимальную ожидаемую прибыль на третьей неделе, если на предыдущей неделе система находилась в первом, втором или третьем состоянии, соответственно. В ячейках диапазона С13:С15 по формулам:

52

=ПОИСКПОЗ(В13;I12:I13;0) =ПОИСКПОЗ(В14;I14:I15;0) =ПОИСКПОЗ(В15;I16:I17;0)

определяется оптимальный вариант действий. Если 1, то деньги на рекламу не тратить, а если 2 – то тратить.

Перейдем ко второй неделе рекламной кампании. В ячейку J5 введена формула:

=I5+МУМНОЖ(В5:D5;$В$13:$В$15),

вычисляющая

которая протаскивается на диапазон J6: J10 для вычисления

…

В ячейки диапазона J12: J17 введены последовательно формулы:

=J5

=J8

=J6

=J9

=J7

=J10,

упорядочивающие ожидаемые доходы по следующим парам: первое состояние без рекламы и при ее наличии, второе состояние без рекламы и при ее наличии и третье состояние без рекламы и при ее наличии.

В ячейки диапазона D13:D15 введены формулы:

=МАКС(J12:J13) =МАКС(J14:J15) =МАКС(J16 :J17),

определяющие максимальную ожидаемую прибыль на второй неделе, если на предыдущей неделе система находилась в первом, втором или третьем состоянии, соответственно. В ячейках диапазона Е13:Е15 по формулам:

=ПОИСКПОЗ(D13;J12:J13;0) =ПОИСКПОЗ(D14;J14:J15;0) =ПОИСКПОЗ(D15;J16:J17;0)

определяется оптимальный вариант действий. Аналогично проводятся расчеты для первой недели.

Из рисунке видно, что на первой и второй неделях необходимо использовать рекламу, не считаясь с состоянием системы, однако, на третьей неделе рекламу следует использовать только тогда, когда система находится во втором или третьем состояниях. Суммарный ожидаемый доход фирмы составит 10736 при отличной оценке, 7923 – при хорошей и 4222 – при удовлетворительной оценке.

53

Тема 8. Поиск решения

В большинстве оптимизационных задач зависимости между переменными линейны. Линейность предполагает наличие двух свойств пропорциональности и аддитивности.

Пропорциональность означает, что вклад каждой переменной в целевую функцию и общий объем потребления соответствующих ресурсов прямо пропорционален уровню (величине) этой переменной.

Аддитивность заключается в том, что целевая функция представляет собой сумму вкладов от различных переменных. Аналогично левая часть каждого ограничения должна представлять собой сумму расходов, каждое слагаемое которой пропорционально величине соответствующей переменной. Если, например, фирма, производит два конкурирующих вида продукции, увеличение сбыта одного из которых отрицательно сказывается на объеме реализации другого, то такая модель не обладает свойством аддитивности.

Математическую модель задачи линейного программирования в общем виде можно записать в виде:

am1 x1 + am2 x2 + ... + amn xn (=, ) bm xj 0, j=1, 2, ... n

Задание 29. Планирование производства красок

Небольшая фабрика выпускает два типа красок: для внутренних (1) и наружных (2) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно.

Расходы продуктов А и В на 1т соответствующих красок:

Изучение рынка сбыта показало, что суточный спрос на краску 1 никогда не превышает спроса на краску 2 более чем на 1 тонну. Кроме того установлено, что спрос на краску 1 никогда не превышает 2 тонны в сутки. Оптовые цены одной тонны красок равны: 3000 рублей для краски 2 и 2000 рублей для краски 1. Какое

54

количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Для решения этой задачи необходимл построить математическую модель. Процесс построения модели – это ответы на следующие вопросы:

1.Для определения каких величин строится модель?

2.В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?

3.Каким ограничениям должны удовлетворять неизвестные?

Решение.

1.В задаче требуется установить, сколько краски каждого вида надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого вида красок:

x1 – суточный объем производства краски 1-го вида, [т краски/сутки]; x2 – суточный объем производства краски 2-го вида, [т краски/сутки].

Тогда целевая функция Z= 2000*х1+3000*х2 – суммарный доход от реализации.

2.В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремится к максимуму, т.е. целевая функция

Z= 3000*х2+2000*х1 – максимальная.

3.Ограничения:

Объем не должен быть отрицательным, следовательно

х1, х2 >=0

Расход исходного продукта для производства обоих видов красок не может превосходить максимально возможный запас данного исходного продукта, следовательно:

х2+2*х1<=6 2*х2+х18

Кроме того, ограничения на величину спроса таковы:

х1-х2<=1 х1 <= 2

Для решения задачи в среде Excel целесообразно на рабочий лист занести исходные данные. Для этого установите ячейки для переменных величин А3 и В3.

Вячейку С3 введите функцию цели.

Вячейки А7:А10 введите левые части ограничений, а в ячейки В7:В10 - правые.

55

После внесения данных на рабочий лист, осуществляется Поиск решения из группы Анализ вкладки Данные. В диалоговом окне заполните поля:

Если решение найдено, его можно сохранить.

56

Задание 30. Планирование производства деревянных изделий

Руководство фирмы предполагает производить продукцию двух моделей А1 и А2. Их производство ограниченно наличием сырья, временем эксплуатации оборудования и денежными кредитами. Для каждого изделия модели А1 требуется 0,3 м3 древесины, 0,2 часа работы станков и затратить 1,6 денежных единиц, а для изделия модели А2 - 0,4 м3 древесины, 0,5 часа работы станков и 1 ден. ед. Фирма может получить от своих поставщиков до 170 м3 древесины в неделю и использовать оборудование в течение 160 часов. На финансирование проекта предполагается выделять 800 ден. ед. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А1 должно приносить 2 ден. ед. прибыли, а каждое изделие модели А2 - 4 ден. ед. прибыли?

Построение математической модели

Переменные. Так как нужно определить объемы производства каждого вида моделей продукции, переменными в модели являются:

х1 - количество выпущенных за неделю изделий модели А1, х2 - количество выпущенных за неделю изделий модели А2.

Целевая функция. Так как прибыль от реализации 1-го изделия модели А1 равна 2 денежным единицам, недельный доход от ее продажи составит 2*х1 ден. ед. Аналогично доход от реализации х2 штук изделия модели А2 составит 4*х2 ден. ед. в неделю.

При допущении независимости объемов сбыта каждой из моделей общий доход равен сумме двух слагаемых - дохода от продажи модели А1 и дохода от продажи модели А2.

Обозначив общий доход через W, можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х1 и х2, максимизирующие величину общего дохода W = 2*х1 + 4*х2.

Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход древесины, время эксплуатации оборудования и финансовые возможности фирмы.

Ограничение на расход древесины можно записать следующим образом:

0,3 х1 + 0,4 х2 170,

здесь 0,3 х1 расход древесины на выпуск недельного объема в х1 изделий модели А1, а 0,4 х2 - х2 изделий модели А2. Суммарный расход древесины на выпуск двух моделей не может превышать максимально возможный запас древесины в 170 м3.

Ограничение на время использование оборудования можно записать следующим образом:

0,2 х1 + 0,5 х2 160,

здесь: 0,2 х1 - количество часов работы оборудования в неделю для выпуска х1 изделий модели А, а 0,5 х2 - х2 изделий модели В в неделю. Время эксплуатации станков для выпуска обоих моделей не может превышать максимально возможный запас времени работы оборудования в160 часов.

Ограничение на использование финансов можно записать следующим образом:

1,6 х1 + 1,0 х2 800,

57

здесь: 1,6*х1 - количество денежных ресурсов расходуемых в неделю для выпуска х1 изделий модели А, а 1,0*х2 - х2 изделий модели В в неделю. Сумма затрат на выпуск обоих моделей не может превышать максимально возможный запас финансов.

Поскольку х1 и х2 выражают еженедельный объём выпускаемых изделий, то они не могут быть отрицательными, т.е. х1 0 и х2 0 (условие не отрицательности переменных).

Итак, математическую модель задачи № 1 можно записать следующим образом:

Решение

Начиная с ячейки с именем А1 на Листе окна Excel постройте следующую таблицу:

Вячейки с адресами В2:С4 заносятся коэффициенты при неизвестных х1 и х2 в ограничениях (2)–(4).

Вячейки с адресами В5:С5 занесены коэффициенты в целевой функции (1).

Встроке Переменные ячейки В6:С6 пусты; в них после решения задачи, будут

занесены рассчитанные значения переменных х1 и х2 .

Встолбце Ограничения в ячейки G2:G4 занесены формулы для расчеты левых частей ограничений (2)–(5).

Вячейку G2 введите следующее: =СУММПРОИЗВ(B2:C2;B6:C6). Здесь записано, что числа в ячейках с адресами В2:С2 умножаются на соответствующие им числа в ячейках В6:С6 и затем результаты произведений просуммированы. Тем самым задано ограничение (2). Задание ограничений (3) и (4) содержится в ячейках G3, G4;

вних напечатайте формулы =СУММПРОИЗВ(B3:C3;B6:C6) и =СУММПРОИЗВ(B4:C4;B6:C6) соответственно.

58

В ячейку В7 занести формулу =СУММПРОИЗВ(B5:C5;B6:C6), которой записана целевая функция (1). В эту же ячейку бедет занесено вычисленное значение целевой функции.

Запустите Поиск решения. В поле Установить целевую ячейку занести $B$7.

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

Вполе Изменяя ячейки занесем диапазон $B$6:$C$6 так как именно эти ячейки отведены под значения вычисляемых переменных.

Вполе Ограничения занесем ограничения (2)–(5). Для этого щелкнем мышью на кнопке Добавить. Появится диалоговое окно Добавление ограничения.

59

Вполе Ссылка на ячейку поместим G2, где задана формула ограничения. В среднее поле занесем соответствующий знак неравенства. В поле Ограничение занесем правую часть ограничения, расположенную в ячейке Е2. Щелкнуть на кнопке ОК. Попадаем снова в поле Поиск решения. Затем повторяя описанные выше действия, заносим остальные ограничения.

Вокне Поиск решения выберите кнопку Параметры.

На экране появится диалоговое окно Параметры поиска решения. В этом окне устанавливаются параметры поиска решения. Здесь отметить квадратики Линейная модель, Неотрицательные значения, Автоматическое масштабирование.

Вернитесь в диалоговое окно Поиск решения и завершите процесс.

Результаты решения задачи:

В столбце Ограничения выводятся их рассчитанные значения . В строке переменные – значения рассчитанных переменных х1 и х2 . В ячейке с целевой функцией – рассчитанное значение целевой функции.

Итак найдено решение: х1 = 300, х2 = 200, Fmax = 1400.

60

Задание 31. Самостоятельно. Оптимальная диета.

Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед.

Содержание их в каждой единице продуктов П1 и П2 равно соответственно

(0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед.

Стоимость 1 ед. продукта П1 – 2 руб., П2 –3 руб.

Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ и решите задачу в Excel.

Задание 32. Самостоятельно. Управление запасами ресторана.

Ежедневно в ресторане фирменный коктейль (порция составляет 0,33 л) заказывают в среднем 600 человек. Предполагается, что в ближайшее время их количество увеличится в среднем на 50 человек. Согласно рецепту в составе коктейля должно быть:

•не менее 20%, но и не более 35% спирта;

•не менее 2% сахара;

•не более 5% примесей;

•не более 76% воды;

•не менее 7% и не более 12% сока.

В таблице приведены процентный состав напитков, из которых смешивается коктейль, и их количество, которое ресторан может ежедневно выделять на приготовление коктейля.

Постройте модель, на основании которой можно будет определить, хватит ли ресторану имеющихся ежедневных запасов напитков для удовлетворения возросшего спроса на коктейль и решите задачу в Excel.

Задание 33. Об оптимальном составе сплава

Рассмотрим задачу о нахождении оптимального состава сплава. Для получения сплавов А и B используются четыре металла I, II, III и IV. Требования к содержанию этих металлов в сплавах А и В приведены в таблице.