2.6. ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ОБЪЕМА ПРОИЗВОДСТВА ШВЕЙНОГО ПРЕДПРИЯТИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

2.6.1. Верхняя и нижняя цена игры

Рассмотрим платежную матрицу игры Е = |е_у ||, раскрытую в

виде (2.2.1). Здесь /-я строка соответствует А,-й стратегии игрока A,j-й столбец соответствует Bf й стратегии игрока В.

Пусть игрок А выбирает некоторую стратегию А „ тогда, в наи­худшем случае (например, если выбор станет известен игроку В), он получат выигрыш равцый minp,-,. Предвидя эту возможность,

игрок А должен выбрать такую стратегию, чтобы максимизиро­вать свой минимальный в каждой стратегии выигрыш а. Таким образом,

а = шах min or,-..                                                                  (2.6.1)

' i

Величина а называется нижней ценой игры (а — это гаранти­рованный выигрыш игрока А). Очевидно а находится в одной из

91

 

строк матрицы Е, пусть в 1_а, тогда стратегия А1₀ называется мак- симинной.

Итак, если игрок А будет придерживаться максиминной стра­тегии, то ему при любом поведении игрока В гарантирован выиг­рыш, во всяком случае не меньший а.

С другой стороны, противник — игрок В, заинтересован в том, чтобы обратить выигрыш игрока А в минимум, поэтому он дол­жен пересмотреть каждую свою стратегию с точки зрения макси­мального выигрыша игроком А при этой стратегии. Другими сло­вами, при выборе некоторой стратегии В, он должен исходить из максимального проигрыша в этой стратегии, равного тахау, и найти такую стратегию, при которой этот проигрыш буДет наи­меньшим, то есть не более, чем

Р = гат шах а, ] <

Величина /3 называется верхней ценой игры, а соответствую­щая ему стратегия В_]0 — минимаксной.

Принцип осторожности, диктующий игрокам выбор страте­гий максиминной ими минимаксной соответственно, в теории игр именуют принципом «минимакса», а сами стратегии максимин- ные и минимаксные — общим термином «минимаксные страте­гии».

Вполне определенной игрой или игрой с седловой точкой на­зывается игра, у которой совпадают нижняя и верхняя цены игры, то есть выполняется равенство:

а = шах тт а_у = тш шах = а_ц = (3

/ 1 " 1

При этом V = а = /3 называется ценой игры, а элемент а,₀у₀, соответствующий равенству, называется седловой точкой.

Простота решения игры с седловой точкой заключается в том, что оптимальные стратегии обоих игроков находятся сразу. Для игрока А это стратегия А_1о, для игрока В — В р. Причем, такое решение обладает свойством устойчивости в том смысле, что, если один из игроков применяет свою оптимальную стратегию, то лю­бое отклонение другого игрока от оптимальной стратегии может оказаться не выгодным для него.

 

Действительно, пусть игрок А выбрал оптимальную страте­гию А,о, соответствующую а = max min а_у = а^, то есть игрок/4

обеспечивает себе выигрыш, равный одному из элементов i₀ стро­ки, причем, элемент в jo столбце наименьший среди них (aj₀j>a_i0j₀, j Ф jo)- и если игрок В выберет j- Ю стратегию отличную ОТ jo, то он проиграет сумму, равную (a_ioj - (Xiojo), а игрок А соответственно выиграет ее. Аналогичные рассуждения показывают невыгодность стратегии, отличной от оптимальной, для игрока А, когда В при­держивается своей оптимальной стратегии.

Среди конечных игр, имеющих практическое значение, срав­нительно редко встречаются игры с седловой точкой. Более ти­пичным является случай, когда нижняя и верхняя цены игры не совпадают (а Ф ß), причем, нетрудно показать, что тогда а < ß.

Действительно, пусть а = max min a_i} =a_KS, это означает, что

в к-ой строке элемент O-ks наименьший, то есть при нахождении а.1 = max«,-, в их число попадут значения не меньшие a^s, так как

даже в этой строке элементы в других столбцах больше или рав­ны ocks- Значит и

min {max а } = min Off >a_KS. ij i

Откуда следует, что ß> а, но мы рассматриваем случай ß±a, зна­чит ß> а. Итак, в играх не имеющих седловой точки, нижняя цена игры а всегда меньше верхней ß.

Установленный факт означает, что если игра одноходовая, то есть партнеры играют один раз, выбирая по одной чистой страте­гии, то в расчете на разумно играющего противника они должны придерживаться принципа минимакса, это гарантирует выигрыш V> а игроку А и проигрыш V< ß игроку В. Следовательно, при применении минимаксных стратегий величина платежа V огра­ничена неравенством а< V<ß.

Если же игра повторяется неоднократно, то постоянное при­менение минимаксных стратегий становится неразумным. Напри­мер, если игрок В будет уверен в том, что на следующем ходу А применит прежнюю стратегию, то он несомненно выберет стра­тегию, отвечающую наименулему элементу в этой строке, а не прежнюю.

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

Для ответа на этот вопрос введем вероятность (относитель­ную частоту) X_t применения игроком А г'-й стратегии, и У, — ве­роятность применения j-й стратегии игроком В. Совокупности ЭТИХ ВерОЯТНОСТеЙ ОПреДеЛЯЮТ ВеКТОрЫ Х= {Xl, Х2, х_т}, где

т                                                                      т

^х, =1 и Y = {у\,уг, ...у„}, где ^у_} =1

1=1                                                                  7=1

Эти векторы или наборы вероятностей выбора чистых стра­тегий называются смешанными стратегиями игроков.

В частности, решение игры с седловой точкой дается вектора­ми X и У , Среди компонент которых Xio = 1, X, = 0 (/Ф Іо) и уjo= 1, У] = 0 (J Ф]_с).

Для получения ограничений на средний выигрыш или проиг­рыш рассмотрим математическое ожидание выигрыша первого игрока

п т

=                                                                                              (2.6.4)

М i=1

Если второй игрок В выбрал некоторую смешанную стратегию У, то первому игроку, естественно, считать лучшей ту смешан­ную стратегию X, при которой достигается max М(Х; F):

М(Х;К') = тахМ(Х;К')

Аналогично, при выборе первым игроком некоторой стратегии X второму игроку следует выбирать стратегию Y такую, что

M(X',Y) = шіпМ(Х';У)

Ясно, что X зависит от Т и Y зависит от X. Перед каждым игроком, таким образом, возникает задача выбора оптимальной стратегии, под которой для игрока понимается смешанная стра­тегия X, которая максимизирует математическое ожидание его выигрыша, для игрока В — стратегия У*, минимизирующая мате­матическое ожидание его проигрыша.

Основная теорема теории игр (доказана фон Нейманом в 1928 году) утверждает:

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

шах min М (X; Y) = min max М (X; Y) = М (X'; У*).

Число V- М(Х*\ Y*) называют ценой игры.

Примечание. Нулевая сумма означает, что выигрыш одного игрока равен проигрышу другого.

Из основной теоремы следует, что каждая конечная игра име­ет цену и она лежит между нижней и верхней ценами игры

a<V<ß                                                                               (2.6.5)

И если один из игроков придерживается своей оптимальной стратегии, то выигрыш (проигрыш) его остается неизменным не­зависимо от тактики другого игрока, если, конечно, последний не выходит за пределы своих «полезных» стратегий, иначе выигрыш (проигрыш) возрастает.

Это означает выполнение неравенств

т

х* > V(j -1, п),

i=i

п

^a_ljy]<V(i = l,m).                                                               ₍₂₆₆₎

М

Примечание. Эти неравенства будут необходимы при сведе­нии матричной игры к задаче лилейного программирования.

2.6.2. Сведение матричной игры к задаче линейного программирования

При наличии неопределенности, причиной которой является при­сутствие нескольких принципов оптимальности G = {G,}, i=l,m, удобно воспользоваться двойственной задачей линейного про­граммирования.

Будем считать, что принципу G, соответствует определенный критерий оптимальности К_{. В качестве К,, могут выступать: эко­номические, технические, социальные и иные критерии оптималь­ности. Показатели К;, являются функцией управляемых факторов

X = {Х_;} i = 1, т и неуправляемых факторов Y = } i = 1, т.

Итак, набору принципов G\{X, У), С₂(Х, У), ..., G_m(X, У) соот­ветствует набор критериев оптимальности К\(Х, У), К₂(Х, У), ...,

К_т{Х, У). Располагая множеством критериев К = {K(X,Y)_l} i = l,m, необходимо определить вектор управляемых переменных Х= (Ä"i, Х₂, ..., Х_т), принадлежащий допустимой области решений X, ко­торый обеспечивает оптимальное (в определенном смысле) реше­ние по каждому из частных критериев.

Рассмотрим матрицу игры (2.2.1). Соотношениям отыскания нижней а и верхней ß цены игры можно поставить в соответствие эквивалентные им задачи:

max {а: М(Х; Y) > а},                                                         (2.6.7)

min {ß: М(Х; Y)< ß},                                                        (2.6.8)

т т

где М(Х; У) = X Е ^ач^х>У}                                                 (2-6.9)

j=1 i=i

есть математическое ожидание выигрыша первого игрока. Тогда для любой чистой стратегии Y(j) игрока П

Y(j) = {У\ = 0,У2= о, ..., yj_ 1 = 0, yj = 1, y_j+l = 0, ..., у_т = 0) можно записать

т

М(ЛГ; Уф) = ]£>,,                                                             (2-6.10)

i=i

а для любой чистой стратегии X(i) игрока Р

X(i) = (xi = 0, х₂ = 0, ..., = 0, Xi = 1, Х/+1 = 0, ..., х_т = 0) м^жно записать

т

M(X(i);Y) = ^e_tjyj.                                                                  _(26П)

7=1

Следовательно, задачи (2.6.7) — (2.6.11) допускают следую­щую запись в форме задач линейного программирования:

т                                                   _____________ т

max{er: Л/ (X; У (у)) = e,jX_t >a,j = 1, m; x_t > 0, i = l,m; ^Гх,- =1}, i=i i=i

(2.6.12)

тт{Р:М(Ха);¥) = ^е^<Р, 1 = 1,т; у, >0, 7 = 1,т;

(2.6.13)

Нетрудно видеть, что задачи (2.6.12) и (2.6.13) взаимнодвой- ственные, а поэтому их оптимальные значения должны совпадать, т.е. а_опт = р_опт = V, где V — цена игры (требуемое значение эф­фективности).

Для задачи (2.6.12) положим:

и Г = 1,                                                                              (2.6.14)

а для задачи (2.6.13) положим:

Тогда отыскание оптимальной смешанной стратегии Х_от иг­рока Р приводит к необходимости решения следующей задачи линейного программирования:

минимизировать линейную функцию

1 + /2+... +*т                                                              (2.6.16)

при условиях

т

X V« ^ 1 = !.«; '< ^о, 1 = 1,/и,                                           (2.6.17)

1=1

а отыскание оптимальной смешанной стратегии К_ОГ1Т игрока П приводит к необходимости решения следующей задачи линейно­го программирования:

максимизировать линейную функцию

г = щ + «2 + ... + и„                                                             (2.6.18)

при условиях

п

XV; -¹' 1 = ^и] 1 = ¹>^п-                                                           (2.6.19)

н

Исходя из основной теоремы теории двойственности, задачи (2.6.16) -Г- (2.6.19) имеют конечное решение И Гит =

2.6.3. Выбор оптимального ассортимента продукции

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

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

По данным наблюдений за предшествующие одиннадцать лет предприятие в течении апреля — мая в условиях теплой погоды может реализовать 600 костюмов, 2000 платьев и 300 плащей, в условиях прохладной погоды —1000 костюмов, 500 платьев и 800 плащей и в условиях обычной погоды — 800 костюмов, 1100 пла­тьев и 600 плащей. Затраты на единицу продукции в течение указанных месяцев составили для костюмов 30 ден. ед., для плать­ев 10 ден. ед. и для плащей 15 ден. ед., а цена реализации равна соответственно 50 ден. ед., 20 ден. ед. и 28 ден. ед.

Задача заключается в максимизации средней величины при­были от реализации выпущенной продукции с учетом неопреде­ленности погоды в рассматриваемые месяцы.

Подобная задача рассматривается как игра с природой. Ее отличительная особенность состоит в том, что в ней сознательно действует только один из участников (предприятие), называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не дей­ствует, а выступает как не имеющий конкретной цели и случай­ным образом выбирающий очередные ходы партнер по игре.

Первоочередной задачей является построение платежной мат­рицы.

Предприятие располагает тремя чистыми стратегиями: страте­гия Р] с расчетом на теплую погоду, стратегия Рг с расчетом па про­хладную погоду и стратегия Р₃ с расчетом на обычную погоду.

Природа, рассматриваемая как второй игрок, также распола­гает тремя стратегиями: обычная погода (стратегия ПО, прохлад­ная погода (стратегия П₂) и теплая погода (стратегия Пз).

Если предприятие выберет стратегию Рь то в случае обычной погоды (стратегия природы П|) доход составит:

(50 - 30) 600 + (20 - 10)1100 + (28 - 15)300 - (20 - 10)(2000 - 1000)=

= 17900 ден. ед.,

в случае прохладной погоды (стратегия природы П₂) доход будет равен

20 • 600 + 10 • 500 + 13 • 300 - 10(2000 - 500) = 5900 ден. ед.,

и в случае теплой погоды (стратегия природы Пз) имеем доход, равный

20 • 600 + 10 • 2000 + 13 • 300 = 35900 ден. ед.

Если предприятие выберет стратегию Рг, то реализация про­дукции в условиях обычной погоды дает доход:

20 • 800 + 10 • 500 + 13 • 600 - 20(1000 - 800) - 13(800 - 600) = = 22000 ден. ед.,

в условиях прохладной погоды доход будет:

20 • 1000 + 10 • 500 + 13 • 800 = 35400 ден. ед.,

а в условиях теплой погоды имеем доход:

20 • 600 + 10 • 500 + 13 • 300 - 20(1000 - 600) - 13(800 - 300) =

= 6400 ден. ед.

Если предприятие выберет стратегию Рз, то в случае обычной погоды доход будет равен:

20 • 800 + 10 • 1100 + 13 • 600 = 34800 ден. ед.,

при прохладной погоде имеем доход, равный:

20 • 800 + 10 • 500 + 13 • 600 - 10(1100 - 500) = 22800 ден. ед.,

и в случае теплой погоды доход составит:

20 • 600 + 10 • 1100 + 13 • 300 - 20(800 - 600) - 13(600 - 300) = = 16000 ден. ед.

 

Результаты вычислений сведены в табл. 2.8.

 

Платежная матрица рассматриваемой производственной си­туации имеет вид:

17900 5900 35900 22000 35400 6400 34800 22800 16000

Платит, естественно, не природа, а некая третья сторона (или совокупность сторон, влияющих на принятие решений игро­ком 1 и объединенных в понятие «природа»). В данной ситуации платит само предприятие, получая меньшую или большую при­быль.

Можно задавать матрицу игры с природой и в виде так назы­ваемой матрицы рисков И = || или матрицы упущенных возмож­ностей. Величина риска — это размер платы за отсутствие инфор­мации о состоянии среды. Матрицу Я построим на основе матри­цы выигрышей Е = |ву ||.

Риском г у игрока при использовании им стратегий Р\, Р₂ или Рз и При состоянии природы П_и П₂ или Щ будем назы­вать разность между выигрышем, который игрок получил бы, если бы он узнал, что состоянием среды будет или П\, или П₂, или Пз и выигрышем, который игрок получит, не имея этой ин­формации.

Матрицу рисков находим по формуле (2.2.2).

 

Для матрицы (2.6.20) имеем /3, = 34 800, ß₂ = 35 400, /З₃ = 35 900. Получаем матрицу рисков:

 

(16900 29500 0 ^ 12800 0 29500 0 12600 19900

 

Для определения критериев эффективности построим табл. 2.9.

Т а б л и ц а 2.9

Вспомогательная таблица

 

Для предприятия лучшими являются стратегии: по критерию гарантированного результата:

Е_г = шах min e_tj = max {5900, 6400,16000} = 16000 - Р₃; i j

по критерию оптимизма:

Е₀ = max max*?,, = max{35900, 35400, 34800} = 35900-Р,; < i

по критерию пессимизма:

Е„ = min min е,. = min {5900, 6400,16000} = 5900- Р,; ' j

по критерию Сэвиджа, исходя из матрицы рисков (2.6.21):

E_rc = min max r_tj = min{29500, 29500,19900} = 19900 - P₃;

i j ^y i

по критерию Гурвица при коэффициенте оптимизма к = 0,6

Е_г = max{A: min е_и + (1 - к) max e_tj } = ' J   i

= max{17900,18000, 23520} = 23520-P₃.

i

 

Стратегия Я₃ повторяется в качестве оптимальной по трем критериям выбора из пяти критериев, а стратегия Р\ — по двум критериям. Однако, преимущество дал критерий Гурвица, зави­сящий от коэффициента оптимизма к и, если принять к = 0,9, то по критерию Гурвица оптимальной будет стратегия Рг■ Поэтому к практическому применению можно рекомендовать как страте­гию Р\, так и стратегию Р3.

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

Дальнейший экономический анализ, с целью определения оп­тимального объема производства, проведем с использованием те­ории двойственности задач линейного программирования.

Для матрицы (2.6.20), исходя из общей постановки (2.6.16) — (2.6.19) имеем следующую пару двойственных задач:

для определения оптимальной стратегии игрока Р нужно ре­шить задачу линейного программирования: найти минимум функции

Т- /1 + /2 + Ь                                                                    (2.6.22)

при ограничениях

17900Г, +22000/₂ + З4800г₃ >1, 5900г, +35400г₂ +22800г₃ >1, 35900^ + 6400г₂ +16000?₃ > 1,      (2.6.23)

г, >0, ; = 1,2,3.

гп

Оптимальную стратегию игрока П определим, решив задачу ли­нейного программирования: найти максимум функции

г = щ + и₂ + и_г                                                                    (2.6.24)

т \я оп

при ограничениях

V

17900м, +5900м₂ + 35900«₃ <1, 22000к, + 35400м₂ + 6400м₃ < 1,

34800«! + 22800« ₂ +16000м ₃ < 1,                                     (2.6.25)

Ц] >0, ] = 1,2,3.

Решаем более простую обратную задачу (2.6.24) — (2.6.25). Вво­дя положительные базисные переменные (б.п.) «4,1/5, щ, систему не­равенств (2.6.24) — (2.6.25) записываем в виде системы уравнений

17900м, + 5900м₂ + 35900м ₃ + м₄ = 1, 22000м, + 35400м₂ + 6400м₃ + и₅ =1, 34800м, + 22800м₂ + 16000м₃ +и₆ = 1,                                                                                           (2.6.26)

-м,-м₂-м₃ + г = 0.

Систему (2.6.26) записываем в виде табл. 2.10.

 

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

 

Так как в табл. 2.11 все элементы в 2-строке и 1-столбце нео­трицательны, то получаем оптимальное решение.

Переходим к решению прямой задачи. Установим соответствие переменных двойственных задач:

СП.                                            Б. П.

и\                                        1/3              «4         1/5 Мб

/4                                        <6                           ¹2 Н

Транспонируем табл. 2.11, знаки перед всеми элементами, кро­ме элементов Z — строки, меняем на обратные, переменные I] за­меняем на соответствующие переменные и,-, получаем табл. 2.12.

Т = у = 0.48 ■ Ю^-4, то цена игры V = 20833. Из г, = 0,225-10"⁴

получаем xi = 0.469. Аналогично получим = 0,472 и х₃ = 0,059.

Это означает, что стратегию Р\ нужно применять с вероятно­стью 0,469, стратегию Рг — с вероятностью 0,472 и стратегию Р_ъ — с вероятностью 0,059.

Формируем оптимальный план производства:

(600 кост. + 2000 плат. + 300 плащ.) • 0,469 + (1000 кост. + + 500 плат. + 800 плащ.) • 0,472 + (800 кост. + 1100 плат. + + 600 плащ.) ■ 0,059 = 801 кост. + 1239 плат. + 554 плащ.

Таким обратом, предприятие при производстве 801 костюма, 1239 платьев и 554 плащей получит наибольшую прибыль, кото­рая в среднем составит 20833 ден. ед.

Для приведенной формулировки производственной задачи получили однозначный ответ.

Недостатком данного метода является достаточно большой объем вычислительных операций даже для матрицы с размерностью 3x3. Однако, существуют стандартные программы применения симплек­сного метода на ЭВМ и это снимает подобное неудобство.