WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |

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

Данная задача решается методом динамического программирования, для этого формулируется ее математическая постановка.

Если u – производительность системы на -м шаге, = 1, 2,..., N;

r – заданная последовательность спросов, причем u r (спрос всегда удовлетворяется), u0 = q – фиксированный начальный уровень запасов; Q(u-r ) – убытки, вызванные тем, что u > r, (u – u–1) – убытки, вызванные тем, что u u–1, то суммарные издержки выражаются формулой N Q(u1,..., uN ) = (u- r)+ (u- u-1)].

[Q =Требуется определить уровни u, = 1,2,..., N, при u r таким образом, чтобы минимизировалась целевая функция (издержки) Q (u1,..., uN). Рекуррентное соотношение имеет вид B(u) = min [Q(u-r )+ (u- q)+ B+1(u )].

u r 5.4.4 Замена оборудования Одной из основных проблем промышленности является замена старого парка машин новым. Необходимо определить оптимальную политику модернизации и замены оборудования при различных предположениях относительно текущих издержек, производственных характеристик и будущего развития техники. Решения здесь принимаются почти ежегодно в зависимости от характерного для данного процесса периода времени, т.е. имеется многошаговый процесс решения.

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

Решения принимаются в моменты времени t = 0, 1, 2,... Возможны два решения: сохранить машину (K) или купить новую (P). Введем следующие обозначения: r (t) – годовой доход от машины возраста t, u (t) – годовые расходы на содержание машины возраста t, C (t) – стоимость замены машины возраста t. Если единица дохода на некотором шаге равносильна единицам дохода следующего шага, то суммарный доход B (t) при оптимальной политике за рассматриваемый период составит P : r(0)- u(0)- C(t)- B(1) B(t) = max.

K : r(t)- u(t)+ B(t + 1) Этот пример является примером бесконечного процесса.

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

B(0) = n(0)+ B(1), B(1) = n(1)+ B(2),...

B(T -1) = n(T -1)+ B(T ), B(T ) = -C(T )+ n(0)+ B(1).

Неизвестное значение T выбирается из условия максимума B(1).

5.4.5 Задача складирования Имеется склад фиксированной вместимости с некоторым начальным запасом товара, стоимость которого подвержена изменению. Какова должна быть оптимальная политика покупки, хранения и передачи этого товара Метод динамического программирования дает вычислительный алгоритм, но он также позволяет найти точное аналитическое решение задачи складирования.

Пусть p – затраты на единицу товара, C – продажная цена единицы товара, x – количество купленного товара, y – количество проданного товара, v – величина наличного запаса на каждом шаге, V – вместимость хранилищ склада.

На любую возможную политику накладываются ограничения:

- на покупку v + -y ) B, = 1, N;

(x j j j =-- на продажу y v + - y ), = 2, N ;

(x j j j =- неотрицательность x 0, y 0.

Целевая функция представляет собой суммарную прибыль, полученную при N-шаговом процессе N QN = y - p x ).

(C j j j j j =Рекуррентное соотношение Беллмана BN (U ) = max [CN yN - pN xN + BN -1(v + xN - yN )] xN, yN при условиях: 0 yN v, xN 0, v + xN - yN V.

5.4.6 Пример решения задачи методом динамического программирования В определенный момент времени на предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в табл. 5.1.

Таблица 5.Время r, в течении которого используется оборудование Исходные данные (лет) 0 1 2 3 4 Годовой выпуск продукции R (r) 80 75 65 60 60 в стоимостном выражении, тыс. р.

Ежегодные затраты z (r), связанные с содержанием и ремонтом оборудования, тыс. р. 20 25 30 35 45 Зная, что затраты связаны с приобретением и установкой нового оборудования идентичного с установленным, составляют 40 тыс. р., а заменяемое оборудование списывается, составить такой план замены оборудования в течение 5 лет, при котором общая прибыль за данный период времени максимальна.

Эту задачу можно рассматривать как задачу динамического программирования, в которой в качестве системы выступает оборудование. Состояние этой системы определяется фактическим временем использования оборудования (его возраста) r, т.е. описывается единственным параметром r.

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

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

Для определения условных оптимальных решений необходимо составить функциональное уравнение Беллмана.

В предположении того, что к началу k-го года (k = 1, 5) может быть принято только одно из двух решений – заменять или не заменять оборудование, то прибыль предприятия за k-й год составит R z(rk) при u1;

(rk) Qk(rk, uk)= (rk R = 0)- z(rk = 0)- Cn при u2, где rk – возраст оборудования к началу k-го года (k = 1,5); un – управление, реализуемое к началу k-го года, Cn – стоимость нового оборудования.

Таким образом, в данном случае уравнение Беллмана имеет вид R z(rk)+ Qk +1 +(rk)- (rk ), Qk(rk)= max r (rk (rk = 1).

R = 0)- z(rk = 0)- Cn - Qk +Используя последнее уравнение можно приступить к нахождению решения исходной задачи. Это решение необходимо начать с определения условно оптимального решения (управления) для последнего 5-го года, в связи с чем находится множество допустимых состояний оборудования к началу данного года.

Так как в начальный момент имеется новое оборудование (r1 = 0), то возраст оборудования к началу 5-го года может составлять 1, 2, 3, 4 года. Поэтому допустимые состояния системы на данный период време5 ни таковы: r15 = 1, r2 = 2, r35 = 3, r4 = 4. Для каждого из этих состояний находится условно оптимальное решение и соответствующее значение функции Q5 ( r5). В результате рассмотрения последнего года расчетного периода соотношение Q6(rk +1)= 0 и следовательно R z(r5);

(r5) Q5(r5)= max (r5=0)R z(r5=0)- Cn.

Учитывая данные табл. 5.1 и r15 = 1, находят R z(r15 = 1) (r15)75- Q5(r15)= max = max = 50;

(r5 80-20- R = 0)- z(r5 = 0)- Cn откуда следует, что условно оптимальное решение u0 = u1, т.е. должно быть принято решение о сохранении оборудования.

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

65 - Q5(r2 )= max = 35, u0 = u1;

- 20 - 60 - Q5(r35)= max = 25, u0 = u1;

- 20 - 60 - Q5(r4 )= max = 20, u0 = u2.

- 20 - Полученные результаты вычислений сведены в табл. 5.2.

Теперь рассматриваются возможные состояния оборудования к началу 4-го года. Здесь допустимыми состояниями являются r14 = 1, r24 = 2, r34 = 3. Для каждого из них определяются условно оптимальное решение и соответствующее значение функции Q4 (r4). Для этого используется функциональное уравнение Беллмана и данные табл. 5.1 и 5.2:

4 R = 1)- z(z1 = 1)+ Q5(r2 = 2) (r Q4(r14)= max = (r R = 0)- z(z4 = 0)- Cn + Q5(r15 =1) 75-25+ = max = 85; u0 = u1;

80-20-40+ 65-30+ Q4(r24)= max = 70, u0 = u2;

80-20-40+ 60-35+ Q4(r34)= max = 70, u0 = u2.

80-20-40+ 5.2 Условно оптимальные решения для 5-го года Условно оптиВозраст оборудо- Значение функмальное решение вания r5 лет ции Q5(r5), тыс. р.

u 1 50 u2 35 u3 25 u4 20 u5.3 Условно оптимальные решения для 4-го года Возраст оборудо- Значения функ- Условно оптивания, r4 лет ции Q4(r4), тыс. р. мальное решение 1 85 u2 70 u3 70 uПолученные результаты сведены в табл. 5.3.

К началу 3-го года условно оптимальное решение для каждого из допустимых состояний оборудования с учетом, что r13 = 1, r2 = 2 и данных табл. 5.1 и 5.3 будет R = 1)- z(r13 = 1)+ Q4(r = 2) (r Q3(r13)= max = (r R = 0)- z(r3 = 0)- Cn + Q4(r = 1) 75-25+ = max = 120;

80-20-40+ 65 - 30 + u0 = u1; Q3(r2 )= max = 105; u0 = u2.

- 20 - 40 + Из последнего выражения видно, что если к началу 3-го года возраст оборудования составляет 2 года, то независимо от того, будет ли принято решение u1 или u2 величина прибыли окажется одной и той же, т.е. в качестве условно оптимального управления может быть принято любое, например u2. Полученные значения для Q3 (r3) и соответствующее условно оптимальные решения сводятся в табл. 5.4.

5.4 Условно оптимальные решения для 3-го года Возраст оборудо- Значения функ- Условно оптивания, r3 лет ции Q3(r3), тыс. р. мальное решение 1 120 u2 105 uИ наконец, рассматриваются допустимые состояния оборудования к началу 2-го года. Вполне очевидно, что на данный момент времени возраст оборудования может быть равен только лишь одному году. Поэтому здесь предстоит сравнить лишь два возможных решения – сохранить оборудование или произвести замену:

R =1)- z(r12 =1)+ Q3(r3 = 1) (r Q2(r12)= max = (rR = 0)- z(r2 = 0)- Cn + Q3(r3 = 1) 75-25+ = max = 155, u0 = u1.

80-20-40+ Полученный результат сведен в табл. 5.5.

Согласно условию, в начальный момент установлено новое оборудование (r11 = 0). Поэтому проблемы выбора между сохранением и заменой оборудования не существует. Следовательно, условно оптимальным решением является u1, а значение функции Q1(r11)= R(r11 = 0)- z(r11 = 0)+ Q2(r1 =1)= 80 – 20 + 155 = 215.

Таким образом, максимальная прибыль предприятия может быть равна 215 тыс. р. Она соответствует оптимальному плану замены оборудования, который получается на основе данных табл. 5.5, 5.4, 5.3 и 5.2, т.е. в результате реализации второго этапа вычислительного процесса, состоящего в прохождении всех рассмотренных шагов с начала 1-го до начала 5-го года.

5.5 Условно оптимальные решения для 2-го года Условно оптиВозраст оборудо- Значения функмальное решение вания, r2 лет ции Q2(r2), тыс. р.

u1 155 u5.6 Оптимальный план замены оборудования Годы пятилетки 1 2 3 4 Сохра- Сохра- Заме- Сохра- СохраОпти- нить нить нить нить нить мальное обору- обору- обору- обору- оборурешение дова- дова- дова- дова- дование ние ние ние ние Для 1-го года решение единственно – сохранить оборудование. Значит, возраст оборудования к началу 2-го года равен одному году. Тогда в соответствии с данными табл. 5.5 оптимальным решением для 2-го года является решение о сохранении оборудования. Реализация такого решения приводит к тому, что возраст оборудования к началу 3-го года становится равным двум годам. При таком возрасте (табл. 5.4) оборудование в 3-ем году следует заменить. После замены оборудования его возраст к началу 4-го года составит 1 год. По данным табл. 5.3 при таком возрасте оборудование менять не следует. Поэтому возраст оборудования к началу 5-го года составит 2 года, т.е. менять оборудование нецелесообразно (табл. 5.2).

В результате получен следующий оптимальный план замены оборудования (табл. 5.6).

6 ИГРОВЫЕ МЕТОДЫ В ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ Одним из возможных типов задач при принятии решения являются, так называемые, состязательные задачи, в которых решение принимает не одно лицо, а два или большее число лиц. Например, одно лицо покупает сахар и хочет получить максимальную прибыль, но оно понимает, что его прибыль зависит не только от того, сколько сахара будет куплено, но и от того, сколько сахара купит его конкурент.

При этом либо оба лица стремятся "выиграть" (максимизировать свои целевые функции), либо одно лицо не стремится этого сделать (игры с природой).

Решению подобных состязательных задач посвящена теория игр [5]. Стороны или лица, принимающие решения в состязательных задачах, называются игроками.

Задача относится к теории игр, если:

а) результат решения задачи зависит от решения двух или более лиц, которые принимают эти решения независимо;

б) решения игроками принимаются в условиях неопределенности.

6.1 ПОСТАНОВКА ЗАДАЧИ Пусть имеется два лица (первое и второе) и оба эти лица стремятся получить максимальную выгоду. Следовательно, имеется две целевые функции: Q1 (x, y) – функция выигрыша первого лица, Q2 (x, y) – функция выигрыша второго лица, где x, y – решения, принимаемые соответственно первым и вторым лицом.

Таким образом, значение целевой функции первого игрока зависит не только от его решения x, которое он примет, но и от решения y, которое примет второй игрок. То же можно сказать и о целевой функции Q2 (x, y) второго лица.

Если бы решение у второго игрока было бы точно известно, то для первого игрока выбор оптимального решения х* был бы традиционным ^), x* = arg maxQ1(x, y xX ^ где y – известное решение второго лица, Х – множество возможных решений первого лица.

Совсем иначе обстоит дело, если решение у второго лица неизвестно. В этом случае необходимо условиться, каким образом оценивать "удачность" выбора решения х, так как значение целевой функции Q1 (x, y) зависит не только от х, но и от у, что иллюстрируется графиком (рис. 6.1).

QQ1(^) x ~ Q1(^) x y y y Рис. 6.1 Зависимость целевой функции первого игрока от решения второго игрока ^ Здесь следует ввести новую оценочную функцию Q1(x), которая позволила бы сравнивать какое из решений х1 или х2 первого лица "лучше".

Также можно оценивать "хорошесть" решения х по среднему значению целевой функции Qy Q1(x) = (x, y) P(y)dy.

Q y Эта оценка является хорошей, она учитывает вклад каждого решения второго лица и вероятность принятия таких решений. Однако, в этом случае необходимо знать вероятность принятия решения вторым лицом или плотность распределения вероятности, если множество Х является континиум. То же самое относится, очевидно, и к функции Q2( y). Если Р(у) не известно, то вычислить Q1( y) или Q2 ( y) невозможно, следует выбрать новую оценку "хорошего " решения.

Естественной оценкой в этом случае является "наихудшее" (минимальное) значение целевой функ~ ции Q1(x) ~ Q1(x) = minQ1(x, y).

yY ~ Чем больше минимальный выигрыш Q1(x), тем лучше х. Эта оценка слишком осторожна: на самом деле выигрыш получится наверняка больше, получиться меньше он уже не может. Такую оценку называют гарантированным выигрышем.

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

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

В теории игр принята следующая терминология.

Лица, принимающие решения, называются игроками.

Целевые функции называются платежными функциями, и считается, что они показывают выигрыш игрока. Так, платежная функция Q1 (x1, …, xn) показывает выигрыш первого игрока.

Множество возможных решений Хi каждого игрока называется множеством чистых стратегий i-го игрока, а решение хi из множества чистых стратегий Xi, xi Xi называется чистой стратегией i-го игрока.

Таким образом, чистой стратегией является то, что раньше называлось решением (управлением).

Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.