Алгоритм метода потенциалов. 1 страница

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

2. находится опорный план перевозок путем составления 1-й таблицы одним из способов - северо-западного угла или наименьшей стоимости;

3. проверяем план (таблицу) на удовлетворение системе уравнений и на невыражденность; в случае вырождения плана добавляем условно заполненные клетки с помощью «0»;

4. для опорного плана определяются потенциалы u_i и v_j, соответствующие базисным клеткам, по условию:

u_i + v_j = c_ij

Таких уравнений будет m + n - 1, а переменных будет m + n. Для их определения одну из переменных полагают равной любому постоянному значению. Обычно принимают u₁ = 0.

После этого для небазисных клеток опорного плана определяются оценки ,

где

При этом если £ 0, то опорный план оптимален, если же среди окажется хотя бы один положительный элемент, то опорный план можно улучшить.

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

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

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

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

Цена цикла – это стоимость перевозки единицы продукта по циклу с учетом знаков вершин.

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

5. Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого:

а) в качестве начальной небазисной переменной принимается та, у которой оценка имеет максимальное значение;

б) составляется цикл пересчета;

в) находится число перерасчета по циклу: число X=min{X_ij}, где X_ij - числа в заполненных клетках со знаком «-»;

г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла;

6. Возвращаются к пункту 3 и т.д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм метода Гомори:

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

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

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

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

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

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

Тема 7

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

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

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

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

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

Процесс перехода производственно-экономической системы из одного состояния в другое должен быть марковским (процессом с отсутствием последействия). Это значит, что если система находится в некотором состоянии 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) называется стратегией управления. Стратегия управления, доставляющая максимум критерию оптимальности, называется оптимальной.

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

Тема 8

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

Основные понятия и критерии теории игр

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

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

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

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

Платежная матрица (матрица эффективности, матрица игры) включает все значения выигрышей (в конечной игре). Пусть игрок 1 имеет т стратегий А_i, а игрок 2 – n стратегий B_j . Игра может быть названа игрой т ´ n. Представим матрицу эффективности игры двух лиц с нулевой суммой, сопроводив ее необходимыми обозначениями (табл. 1.1).

Таблица 1.1.

В данной матрице элементы а_ij - значения выигрышей игрока 1 - могут означать математическое ожидание выигрыша (среднее зна­чение), если выигрыш является случайной величиной. Величины a_i, и b_j, – соответственно минимальные значения элементов а_ij по строкам и максимальные - по столбцам. Их содержательный смысл будет отражен ниже.

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

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

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

Взаимоотношения сторон. Согласно данному критерию игры делятся на кооперативные, коалиционные и бескоалиционные. Если игроки не имеют права вступать в соглашения, образовывать коалиции, то такая игра относится к бескоалиционным; если игроки могут вступать в соглашения, создавать коалиции - коалиционной. Кооперативная игра - это игра, в которой заранее определены коалиции.

Характер выигрышей. Этот критерий позволяет классифицировать игры с нулевой и с ненулевой суммой. Игра с нулевой суммой предусматривает условие: «сумма выигрышей всех игроков в каждой партии равна нулю». Игры двух игроков с нулевой суммой относят к классу антагонистических. Естественно, выигрыш одного игрока при этом равен проигрышу другого. Примерами игр с нулевой суммой служат многие экономические задачи. В них общий капитал всех игроков перераспределяется между игроками, но не меняется. К играм с ненулевой суммой также можно отнести большое количество экономических задач. Например, в результате торговых взаимоотношений стран, участвующих в игре, все участники могут оказаться в выигрыше. Игра, в которой нужно вносить взнос за право участия в ней, является игрой с ненулевой суммой.

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

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

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

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

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

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

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

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

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

Рассмотрим матричную игру, представленную матрицей выигрышей m´ n, где число строк i = а число столбцов j = (см. табл.1). Применим принцип получения максимального гарантированного результата при наихудших условиях. Игрок 1 стремится принять такую стратегию, которая должна обеспечить максимальный проигрыш игрока 2. Соответственно игрок 2 стремится принять стратегию, обеспечивающую минимальный выигрыш игрока 1. Рассмотрим оба этих подхода.

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

a._i = . (1.1)

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

a. = (1.2)

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

Подход игрока 2. Своими оптимальными стратегиями он стремится уменьшить выигрыш игрока 1, поэтому при каждой j -й чистой стратегии он отыскивает величину своего максимального проигрыша

в каждом j -м столбце, т.е. определяет максимальный выигрыш игро­ка 1, если игрок 2 применит j -ю чистую стратегию. Из всех своих п 7-х чистых стратегий он отыскивает такую, при которой игрок 1 получит минимальный выигрыш, т.е. определяет чистую верхнюю цену игры (минимакс):

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

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

Тема 9

Стратегии теории игр

Смешанные стратегии

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

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

• игра без седловой точки;

• игроки используют случайную смесь чистых стратегий с заданными вероятностями;

• игра многократно повторяется в сходных условиях;

• при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

• допускается осреднение результатов игр.

Применяются следующие обозначения смешанных стратегий.

Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий А₁, А₂,..., А_т с соответствующими вероятностями р₁, р_2, ..., р_т.

где .

Для игрока 2

где .

q_j — вероятность применения чистой стратегии B_j.

В случае когда р_i = 1, для игрока 1 имеем чистую стратегию

(1.7)

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

(1.8)

где и – векторы;

p_i и q_i – компоненты векторов.

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

(1.9)

Игрок 2 добивается того, чтобы выполнялось условие

(1.10)