Задачи целочисленного программирования. Метод Гомори. 1 страница

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

Найти такое решение (назовем его план) Х=(х₁, х₂,…, х_n), при котором линейная функция

Рисунок 29.

принимает максимальное значение при ограничениях:

Рисунок 30.

Методы целочисленной оптимизации принято разделять на три основные группы:

a. методы отсечения;

b. комбинаторные методы;

c. приближенные методы.

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

• естественно оно должно быть линейным;

• должно отсекать найденный оптимальный нецелочисленный план;

• не должно отсекать ни одного целочисленного плана.

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

Далее задача решается с учетом этого нового ограничения. После этого в случае необходимости добавляется еще одно новое ограничение и т.д.

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

Алгоритм метода Гомори следующий:

1. Симплексным методом решается задача без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если первая задача неразрешима (то есть не имеет конечного оптимума или же условия ее противоречивы), то и вторая задача также неразрешима.

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

Неравенство, полученное введением дополнительной неотрицательной целочисленной переменной преобразовывают в равносильное уравнение

и включают его в систему ограничений

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

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

2.2.5. Динамическое программирование

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

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

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

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

Процесс перехода анализируемой системы из одного состояния в другое рассматривается как Марковский, то есть зависит от данного состояния. Это значит, что если система находится в некотором состоянии Sⁿ S_n , то дальнейшее развитие процесса зависит только от данного состояния и не зависит от того, каким путем система приведена в это состояние.

Очевидно, что процесс длится определенное число шагов (этапов) N. На каждом шаге осуществляется выбор только одного управления uⁿ (или целевой функции), под воздействием, которого система переходит из одного состояния Sⁿ в другое Sⁿ⁺¹: Sⁿ Sⁿ⁺¹. Поскольку процесс марковский, то очевидно, что Sⁿ = uⁿ (Sⁿ) зависит только от текущего состояния.

Каждый шаг (выбор очередного решения) связан с определенным эффектом (называется выигрышем), который зависит от текущего со стояния и принятого решения: (Sⁿ, Sⁿ⁾.

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

Требуется найти такое решение uⁿ для каждого шага (n = 1, 2, 3,..., N), то есть последовательность (u¹,..., u^N), чтобы получить максимальный эффект (выигрыш) за N шагов.

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

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

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

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

Любая возможная допустимая последовательность решений (u¹,..., u^N) принято называть стратегией управления. Стратегия управления, доставляющая оптимальность критерию, называется оптимальной.

В основе общей концепции метода ДП лежит принцип оптимальности Беллмана:

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

 

,

Рисунок 31.

где — все допустимые управления при условии, что система находится в состоянии Sⁿ;

(Sⁿ, Sⁿ⁾ — эффект от принятия решения uⁿ;

— эффект за оставшиеся n шагов.

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

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

В качестве примера построения РДП нужно рассмотреть использование принципа оптимальности для реализации математической модели задачи оптимального распределения некоторого ресурса в объеме х:

Рисунок 32.

где x_j — необходимое количество ресурса, используемое j-м способом;

— полкченный доход от применения способа j, j = 1, N.

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

 

Рисунок 33.

 

2.3.ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ИГР

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

Уже начиная с момента ее зарождения, которым считают публикацию в 1944 г. монографии Дж. Неймана и О. Моргенштерна “Теория игр и экономическое поведение”, многие ученые предсказали настоящую революцию в чоциальных и экономических науках благодаря использованию нового подхода. Эти прогнозы некоторые считали излишне смелыми, а некоторые экономисты считали даже теорию игр циничной и аморальной. Однако с самого начала данная теория претендовала на описание рационального поведения при принятии решений во взаимосвязанных ситуациях, что характерно для большинства актуальных проблем в экономических и социальных науках. Такие тематические области, как стратегическое поведение, конкуренция, кооперация, риск и неопределенность, являются ключевыми в теории игр и непосредственно связаны с управленческими системными задачами.

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

В последние десятилетия эти методы проникли и в управленческую практику. И уже постоянно субьекты рынка называются игроками. Вполне вероятно, что теория игр наряду с теориями трансакционных издержек и “патрон – агент” будет восприниматься как наиболее экономически обоснованный элемент теории организации. Следует отметить, что уже в 80-х годах М. Портер ввел в обиход некоторые ключевые понятия теории, в частности такие, как “стратегический ход” и “игрок”. Правда, эксплицитный анализ, связанный с концепцией равновесия, в этом случае еще отсутствовал.

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

Игры охватывают, как правило, несколько периодов, в течение которых игроки предпринимают последовательные или одновременные действия. Эти действия обусловленнын правилами обозначаются термином “ход”. Действия могут быть связаны с ценами, объемами продаж, затратами на научные исследования и разработки и так далее. Периоды, в течение которых игроки делают свои ходы, называются этапами игры. Выбранные на каждом этапе ходы, в конечном счете, определяют выигрыш или убыток каждого игрока, которые могут выражаться в материальных ценностях или деньгах (преимущественно дисконтированная прибыль) или в любых измеримых единицах.

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

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

Чтобы установить первую связь со сферой управления, игру упрощенно можно описать следующим образом. Два предприятия (игрока), производящие однородную продукцию, стоят перед выбором. В одном случае они могут закрепиться на рынке благодаря установлению высокой цены, которая обеспечит им среднюю картельную прибыль П_K. При вступлении в жесткую конкурентную борьбу оба получают прибыль П_W. Если один из конкурентов устанавливает высокую цену, а второй – низкую, то последний реализует монопольную прибыль П_M, другой же несет убытки П_G. Подобная ситуация может, например, возникнуть когда обе фирмы должны объявить свою цену, которая впоследствии не может быть пересмотрена.

При отсутствии жестких условий обоим предприятиям выгодно назначить низкую цену. Стратегия “низкой цены” является доминирующей для любой фирмы: вне зависимости от того, какую цену выбирает конкурирующая фирма, самой всегда предпочтительней устанавливать низкую цену. Но в таком случае перед фирмами возникает дилемма, так как прибыль П_K (которая для обоих игроков выше, чем прибыль П_W) не достигается.

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

Что касается указанной выше дилеммы, то ее разрешение зависит, в частности, от уникальности ходов игроков. Если предприятие имеет возможность пересмотреть свои стратегические переменные (в данном случае цену), то может быть найдено кооперативное решение проблемы даже без жесткого договора между игроками. Практика подсказывает, что при многократных контактах игроков появляются возможности добиться приемлемой “компенсации”. Так, при известных обстоятельствах совсем нецелесообразно стремиться к краткосрочным высоким прибылям путем ценового демпинга, если в дальнейшем может возникнуть “война цен”.

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

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

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

Рисунок 34.

Квадранты 1 и 2 характеризуют ситуацию, когда реакция конкурентов не оказывает существенного влияния на платежи фирмы. Это происходит в тех случаях, когда у конкурента нет мотивации (поле 1) или возможности (поле 2) нанести “ответный удар”. Поэтому нет необходимости в детальном анализе стратегии мотивированных действий конкурентов.

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

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

Лишь ситуация, показанная в квадранте 4 (возможность ответных шагов рыночных партнеров), требует использования положений теории игр. Однако здесь отражены лишь необходимые, но далеко недостаточные условия, чтобы оправдать применение базы теории игр для борьбы с конкурентами. Часто бывают ситуации, когда одна стратегия, безусловно, доминирует над всеми другими, независимо от того, какие действия предпримет конкурент. Если взять, например, рынок лекарственных препаратов, то для фирмы часто бывает важно первой заявить новый товар на рынке: прибыль “первопроходца” оказывается столь значительной, что всем другим “игрокам” остается только быстрее активизировать свою инновационную деятельность.

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

Другое предприятие, действующее, к примеру, на рынке периферийного оборудования для ЭВМ, обдумывает вопрос о проникновении на рынок персональных компьютеров, что связвно с переналадкой своего производства. Компания-аутсайдер, конечно, может принять решение о вступлении или невступлении на рынок. Компания-монополист может отреагировать на появление нового конкурента либо агрессивно, либо дружественно. Очевидно, сто оба предприятия вступают в двухэтапную игру, в которой первый ход делает компания-аутсайдер. Игровая ситуация с указанием платежей показана в виде дерева на рис.35.

Рисунок 35.

Та же самая игровая ситуация может быть представлена и в нормальной форме (рис.35). Здесь обозначены два состояния – “вступление/дружественная реакция” и “невступление/ агрессивная реакция”. Очевидно, что второе равновесие несостоятельно. Из развернутой формы следует, что для уже закрепившейся на рынке компании нецелесообразно реагировать агрессивно на появление нового конкурента: при агрессивном поведении теперешний монополист получает 1(платеж), а при дружественном – 3. Компания-аутсайдер к тому же знает, что для монополиста не рационально начинать действия по ее вытеснению, либо она не считает аутсайдера конкурентом и поэтому она принимает решение о вступлении на рынок. Грозившие потери в размере (-1) компания-аутсайдер не понесет.

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

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

Рассмотрим типичные примеры, какую пользу могут извлечь компании из анализа на базе теории игр? Известен, например, случай столкновения интересов компаний IВМ и Telex. В связи с объявлением о подготовительных планах последней к вступлению на рынок состоялось экстренное “кризисное” совещание руководства IВМ, на котором были проанализированы мероприятия, направленные на то, чтобы заставить нового конкурента (Telex) отказаться от намерения проникнуть на новый рынок.

Компании Telex, видимо, стало известно об этих мероприятиях. Так вот анализ на базе теории игр показал, что угрозы IВМ из-за высоких затрат безосновательны.

Это свидетельствует, что компаниям полезно в эксплицитном виде обдумывать возможные реакции партнеров по игре. Изолированные хозяйственные расчеты, даже опирающиеся на теорию принятия решений, часто носят, как в изложенной ситуации, ограниченный характер. Так, компания-аутсайдер могла бы, конечно, и выбрать ход “невступление”, если бы предварительный анализ убедил ее в том, что проникновение на рынок вызовет агрессивную реакцию монополиста (что орасно). В этом случае в соответствии с критерием ожидаемой стоимости разумно выбрать ход “невступление” при вероятности агрессивного ответа 0,5.

Следующий пример связан с соперничеством компаний в области технологического лидерства. Исходной является ситуация, когда предприятие 1 ранее обладало технологическим превосходством, но в настоящее время располагает меньшими финансовыми ресурсами для научных исследований и разработок (НИР), чем его конкурент. Оба предприятия должны решить вопрос, попытаться ли с помощью крупных капиталовложений добиться доминирующего положения на мировом рынке в соответствующей технологической области. Если оба конкурента вложат в дело крупные средства, то перспективы на успех у предприятия 1 будут лучше, хотя оно и понесет большие финансовые расходы (как и предприятие 2). На рис. эта ситуация представлена платежами с отрицательными значениями.

Для предприятия 1 лучше всего было бы, если бы предприятие 2 отказалось от конкуренции. Его выгода в таком случае составила бы 3 (платежа). С большой вероятностью предприятие 2 выиграло бы соперничество, когда предприятие 1 приняло бы урезанную программу инвестиций, а предприятие 2 – более широкую. Это положение отражено в правом верхнем квадранте матрицы.

Анализ ситуации наглядно показывает, что равновесие наступает при высоких затратах на НИР предприятия 2 и низких затратах предприятия 1. При любом другом раскладе у одного из конкурентов появляется резон отклониться от стратегической комбинации: так, для предприятия 1 предпочтителен сокращенный бюджет, если предприятие 2 откажется от участия в соперничестве; в то же время предприятию 2 известно, что при низких затратах конкурента ему выгодно инвестировать в НИР.

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

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

С точки зрения теории игр подобные обязательства равнозначны изменению хода игры: ситуация одновременного принятия решений сменяется ситуацией последовательных ходов. Предприятие 1 твердо демонстрирует намерение пойти на крупные затраты, предприятие 2 регистрирует этот шаг и у него нет больше резона участвовать в соперничестве. Новое равновесие вытекает из расклада “неучастие предприятия 2 ” и “высокие затраты на НИР предприятия 1 ”.

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

Рисунок 36.

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

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

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

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

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

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

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

Рисунок 37.

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