Методы динамического программирования

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

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

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

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

Использование в экономическом анализе метода динамического программирования покажем на простейшем примере (Более сложные задачи, решаемые методами математического моделирования требуют применения ЭВМ)

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

Для этого введем соответствующие обозначения:

Необходимо подобрать груз максимальной ценности с учетом грузоподъемности транспортного средства W.

Математически формализовать данную экстремальную задачу можно следующим образом:

 

 

 

 

 

 

 

 

Математическая теория игр

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

Решение подобных задач требует определенности в формулировании их условий: установления количества игроков и правил игры, выявления возможных стратегий игроков, возможных выигрышей (отрицательный выигрыш понимается как проигрыш). Важным элементом в условии задач является стратегия, т.е. совокупность правил, которые в зависимости от ситуации в игре определяют однозначный выбор данного игрока. Количество стратегий у каждого игрока может быть конечным и бесконечным, отсюда и игры подразделяются на конечные и бесконечные. При исследовании конечной игры задаются матрицы выигрышей, а бесконечной — функции выигрышей. Для решения задач применяются алгебраические методы, основанные на системе линейных уравнений и неравенств, итерационные методы, а также сведение задачи к некоторой системе дифференциальных уравнений.

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

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

Природные условия нередко сказываются и на эффективности работы промышленных предприятий.

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

Затраты фабрики в течение апреля — мая на единицу продукции составили: платья — 8 денежных единиц, костюмы — 27, а цена реализации равняется соответственно 16 и 48. По данным наблюдений за прошлое время, фабрика может реализовать в течение этих месяцев в условиях теплой погоды 600 костюмов и 1975 платьев, а при прохладной погоде — 625 платьев и 1000 костюмов.

Задача заключается в максимизации средней величины дохода от реализации выпущенной продукции, учитывая капризы погоды. Фабрика располагает в этих ситуациях двумя следующими стратегиями: в расчете на теплую погоду (стратегия А); в расчете на холодную погоду (стратегия В).

Если предприятие примет стратегию А, т.е. продукция, соответствующая теплой погоде (стратегия природы — С), будет полностью реализована, то доход фабрики в этой ситуации составит: