Постановка и решение оптимизационной задачи в MS Excel

а) Определение целевой функции

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

Цель модели определяет целевую функцию, которая задается на множестве допустимых решений D. Само множество D выражает меру осуществления цели:

- если D пусто, то решения  не существует;

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

При этом, если D конечно, то оптимальное решение может быть

найдено в результате простого перебора всех точек D и вычисления в них функции цели.

Если D счетно или D является континуумом, то оптимальное решение приходиться искать на бесконечном множестве допустимых решений.

В основе математической модели лежит допущение, что все переменные, параметры, ограничения и целевая функция модели количественно измеримы.

Если переменные X=(x1, x2, …, xN) представляет собой N управляемых переменных, Z=(z1, z2, …, zK) – K неуправляемых параметров и условие функционирования исследуемой системы определяется M ограничениями, то математическая модель может быть записана в следующем виде: найти точку Y=(y1, y2, …, yN), в которой достигается экстремум, минимум или максимум, целевой функции ƒ(X,Z):

ƒ(Y,Z)=extrƒ(X,Z) (1.1)

при ограничениях ψj(X,Z) ≤ (≥,=) bj, j=1, 2, …, M

xi≥0, i=1, 2, …, N.

Задача на условный экстремум обычно имеет смысл, когда M<N. Именно в этом случае множество допустимых решений может содержать более одной точки. Подразумевается, что все ограничения независимы. Если какое-либо из ограничений оказывается следствием других ограничений, то оно исключается из системы ограничений.[2, с.31]

в) Этапы определения оптимального решения

Процесс нахождения оптимального решения, как правило, состоит из четырех этапов:

1) формулировки проблемы;

2) построение модели;

3) нахождения оптимального модельного решения;

4) проверки адекватности  модели.

На первом этапе – при формулировке проблемы – можно выделить следующие стадии: формулировку цели исследования; выявление возможных альтернатив решения применительно к исследуемой ситуации; определение требований, присущих исследуемой системе условий и ограничений.

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

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

делить переменные (искомые величины) задачи?

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

3. В чем состоит оптимальная  цель?

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

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

Однако такой способ непригоден при разработке новых систем, так как нет необходимых данных для проверки модели. Интуитивные методы также могут играть важную роль при оценке адекватности модели.[3, с.31]

с) Оптимизация плана производства

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

- максимум прибыли,

- минимум расходов,

- максимум объема готовой  продукции,

- минимум использования  ресурсов и т.д.

Линейная модель оптимального плана производства имеет вид:

 ƒ=p1x1+p2x2+…+pNxN

Следует определить объем выпускаемой продукции, обеспечивающий максимальное (или минимальное) значение целевой функции учитывая, что имеющиеся ресурсы подчинены следующим ограничениям:

aj1x1+aj2x2+…+ajNxN ≤ (или ≥) bj, j=1, 2,…, M

xi≥0, i=1, 2,…, N,

где N – количество видов выпускаемой продукции;

M – число типов производственных  ресурсов;

xi – объем выпуска i-й продукции;

pi – стоимостная характеристика, связанная с выпуском единицы i-й продукции;

aji – удельный вес j-го ресурса, расходуемого на производство i-й

продукции;

bj – количество имеющегося ресурса j-го типа;

ƒ определяет доходы (или расходы) при производстве продукции.

Линейные модели подобного типа применяется в ситуациях, когда в процессе производства закупка готовых полуфабрикатов или комплектующих может оказаться более выгодной, чем производство их на собственных мощностях. Также линейные модели планирования производства рассматриваются, если учитывается динамика спроса, производства и хранения продукции.[10, с.31]

1.4. Распределение капиталовложений между предприятиями

Одним из основных источников денежных средств, направляемых на развитие производства или расширение бизнеса, являются инвестиции и нераспределенная прибыль, оставляемая для использования в бизнесе. Инвестор, вкладывая капитал в развитие фирмы или предприятия, вынужден действовать в условиях неопределенности, так как в современных условиях нестабильности как отечественной, так и зарубежных экономик, инвестирование связано с риском (вероятностью) неполучения прибыли. Риск может быть вызван непредвиденным снижением спроса, увеличением издержек производства и обращения производимой продукции, неблагоприятным изменением цены на произведенную продукцию и многими другими факторами, влияющими на размер дохода от реализации продукции. Умение правильно распределять денежные средства между инвестируемыми предприятиями позволит инвестору не только избежать значительных неоправданных потерь, но и получить максимально возможную прибыль. Пусть инвестор предполагает вкладывать денежные средства в два предприятия и, ежегодно получая с этих предприятий некоторую прибыль, заинтересован в таком распределении выделенных средств между предприятиями, чтобы за N лет получить максимальную суммарную прибыль. В дальнейшем будем считать, что прибыль, получаемая инвестором, в последующие годы в данные предприятия не инвестируется. Предположим, что у инвестора имеются денежные средства в количестве K ден.ед., которые предназначены для инвестиций в предприятия A1 и A2. Если x ден.ед. выделить предприятию A1, то годовая прибыль инвестора с этого предприятия с вероятностью p11 составит f1(x), с вероятностью p12 — f2(x), ..., с вероятностью p1k — fk(x). Возможные значения прибыли f1(x), f2(x), ..., fk(x) и соответствующие им вероятности p11, p12, ..., p1k являются эмпирическими данными, полученными либо в результате предыдущего опыта, либо в результате статистических исследований. Тогда в среднем готовую прибыль инвестора с предприятия A1 можно представить как математическое ожидание:

Исходные данные по предприятиям A1 и A2 можно свести в табл. 1.  Поскольку x ден. ед. выделены предприятию A1, то на долю предприятия A2 останется (K – x) ден. ед. Тогда годовая прибыль инвестора с предприятия A2 с вероятностью p31 составит y1(K – x) ден. ед., с вероятностью p32 — y2(K – x), ..., с вероятностью p3m — ym(K – x), а в среднем годовая прибыль инвестора с этого предприятия будет равна:

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

Это уравнение устанавливает связь между функциями f1(K) — максимальной прибылью, получаемой инвестором за первый год, и f2(K) — максимальной прибылью, получаемой им за первые два года.  Если за f3(K) обозначить максимальную суммарную прибыль, которая может быть получена им за первые три года, то:

При выводе функционального уравнения (6) использовался прямой ход рассуждений. Чтобы определить оптимальную политику распределения капитала K между предприятиями A1 и A2, применим обратный ход рассуждений.  Через xN* обозначим то значение x, при котором достигается максимум выражения (5), через xN–1* — значение x, при котором fN–1(K) достигает своего максимума, и т.д. И, наконец, найдем x1* — значение, приводящее к максимуму f1(K). Таким образом, для получения за N лет максимальной суммарной прибыли от инвестиций инвестору следует в первый год предприятию A1 выделить сумму x* = x1* , предприятию A2 — сумму (K – x*).  Заметим, что при неполучении прибыли от инвестиций вследствие указанных выше рисков рассматриваемую задачу следует переформулировать таким образом, чтобы оптимальная политика распределения инвестиций строилась не на максимизации суммарной прибыли, а на условии минимизации возможных суммарных убытков.[4, с.31]

 

 

 

ГЛАВА 2. ПОСТАНОВКА И РЕШЕНИЕ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ В MS EXCEL

Задача:

1. Постановки оптимизационных  задач линейного программирования  и методы их решения в Excel.

2. Решение задачи линейного  программирования.

Предприятие в Энске

Цех одного из крупных предприятий города Энска производит 8 различных видов деталей для двигателей A, B, C1, C2, C3, D, E6, F имея в своем распоряжении перечисленный ниже парк из 7 видов универсальных станков: 2 шт. -ADF, 3 шт. -SHG, 3 шт. -BSD, 1 шт. -AVP, 1 шт. -BFG, 3 шт. -ABM, 2 шт. -RL.

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

Обработка на	A	B	C1	C2	C3	D	E6	F
ADF	0.24	0.23	0.19	0.15	0.19	0.18	0.23	0.18
SHG	0.05	0.03	-	0.70	0.10	-	0.08	0.08
BSD	0.37	0.59	0.71	0.50	0.32	0.74	0.43	0.40
AVP	0.11	0.11	0.12	0.10	0.09	0.12	0.07	0.10
BFG	0.29	0.22	-	0.20	0.16	0.29	0.14	0.12
ABM	-	0.58	0.70	0.69	0.46	0.31	0.31	0.65
RL	0.08	0.01	0.08	0.11	0.12	0.08	-	0.12
Прибыль	5	6	8	6	7	8	6	4
Потребность рынка	200	350	280	300	350	220	100	200

 

 

Цех работает 12 часов в день. Каждый месяц содержит 26 рабочих дней. Для упрощения задачи считаем, что возможен произвольный порядок обработки деталей на различных станках.

a. Составьте оптимальный план производства.

b. Определите, производство каких продуктов лимитировано рынком, и каких - техническими возможностями цеха. Какие машинные ресурсы должны быть увеличены в первую очередь, чтобы добиться максимального увеличения прибыли (при заданных потребностях рынка)?

c. Есть ли продукт, который невыгодно производить? Почему? Что нужно изменить, чтобы все продукты стало выгодно производить?

Решение задачи:

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

Целевая функция будет иметь вид:

Х1*5+Х2*6+Х3*8+Х4*6+Х5*7+Х6*8+Х7*6+Х8*4        max

Ограничения имеют несколько видов.

Ограничения по количеству станков:

ADF: Х1*0,24+Х2*0,23+Х3*0,19+Х4*0,15+Х5*0,19+Х6*0,18+Х7*0,23+Х8*0,18<=624

SHD: Х1*0,05+Х2*0,03+Х3*0+Х4*0,70+Х5*0,10+Х6*0+Х7*0,08+Х8*0,08<=963

BSD: Х1*0,37+Х2*0,59+Х3*0,71+Х4*0,50+Х5*0,32+Х6*0,74+Х7*0,43+Х8*0,40<=963

AVP: Х1*0,11+Х2*0,11+Х3*0,12+Х4*0,10+Х5*0,09+Х6*0,12+Х7*0,07+Х8*0,10<=312

BFG: Х1*0,29+Х2*0,22+Х3*0+Х4*0,20+Х5*0,16+Х6*0,29+Х7*0,14+Х8*0,12<=312

ABM: Х1*0+Х2*0,58+Х3*0,70+Х4*0,69+Х5*0,46+Х6*0,31+Х7*0,31+Х8*0,65<=963

RL: Х1*0,08+Х2*0,01+Х3*0,08+Х4*0,11+Х5*0,12+Х6*0,08+Х7*0+Х8*0,12<=624

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

ADF<=624

SHD<=963

BSD<=963

AVP<=312

BFG<=312

ABM<=963

RL<=624

Ограничения по потребностям рынка:

Х1>=200

Х1>0

Х2>=350

Х2>0

Х3>=280

Х3>0

Х4>=300

Х4>0

Х5>=350

Х5>350

Х6>=220

Х6>0

Х7>=100

Х7>100

Х8>=200

Х8>200

Для решения данной задачи будет использоваться пакет Excel.

Найдем сколько времени уходит на создание детали A. Для этого в ячейку В13 введем =СУММПРОИЗВ(B2:B8;1/$J$2:$J$8)*B9.

В окне Excel это выглядит так (рисунок 1):

Рисунок 1

Так же находим сколько времени уходит на создание детали В. Для этого вводим в ячейку С13 =СУММПРОИЗВ(C2:C8;1/$J$2:$J$8)*C9.

Получаем (рисунок 2):

Рисунок 2

Данную операцию проделываем для нахождения затраченного времени для каждой из деталей. Последней деталью является деталь F. Для нахождения потраченного времени для ее создания мы вводим я ячейку I13 =СУММПРОИЗВ(I2:I8;1/$J$2:$J$8)*I9.

Получаем (рисунок 3):

Рисунок 3

Далее находим время, которое каждый станок затрачивает на производство деталей А, В,…, F.

Для этого в ячейку К2 вводим =СУММПРОИЗВ(B2:I2;$B$9:$I$9)/$J2. Это мы найдем сколько времени тратит станок ADF.

В окне Excel это выглядит так (рисунок 4):

Рисунок 4

Так же находим сколько времени уходит на создание деталей на станке SHG. Для этого в ячейку К3 вводим =СУММПРОИЗВ(B3:I3;$B$9:$I$9)/$J3.

Получаем (рисунок 5):

Рисунок 5

Данную операцию проделываем для нахождения затраченного каждым из станков времени для деталей. Последним станком являет станок RL. Для нахождения потраченного им времени вводим в ячейку К8 =СУММПРОИЗВ(B8:I8;$B$9:$I$9)/$J8.