Алгоритм решения ТЗЛП методом потенциалов

 

1. Построить опорный план по одному из правил.

2. Проверить план на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно m+ n- 1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток.

3. Проверка плана на оптимальность.

3.1. Определение потенциалов поставщиков и потребителей. Для всех занятых клеток рассчитываются потенциалы по формуле

 

                                        (3.8)

 

где u_i – потенциалы поставщиков (строк);

v_j – потенциалы потребителей (столбцов).

Так как всех занятых клеток должно быть m+ n -1, т.е. на единицу меньше числа потенциалов (их m+ n), то для определения чисел u_i, v_j необходимо решить систему из m+ n -1 уравнений u_i+ v_j= c_ij c m+ n неизвестными. Система неопределенная, и, чтобы найти частные решения, одному из потенциалов придают произвольное числовое значение (обычно полагают u ₁=0), тогда остальные потенциалы определяются однозначно.

3.2. Для всех свободных клеток рассчитываются оценки по формуле

 

)                                                      (3.9)

 

Здесь – реальные тарифы, а – косвенные тарифы.

Если все s то полученный план является оптимальным. При этом, если все s_ij >0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка s_ij =0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции. Если хотя бы для одной свободной клетки , то план может быть улучшен. Переход к шагу 4.

4. Среди отрицательных оценок выбирается минимальная. Например, для клеток (i, j) и (k, l) имеем оценки: s_ij =–2, s_{k l}=–4. В этом случае наиболее потенциальной (перспективной) является клетка (k,l). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загрузки данной клетки единицей груза. Так, от загрузки клетки (i, j) единицей груза транспортные расходы уменьшаются на  денежных единиц, а от загрузки единицей груза клетки (k, l) – на  денежных единиц. Эффективность плана от загрузки потенциальной клетки грузом в  единиц составит денежных единиц.

Для наиболее перспективной свободной клетки (клетки с min отрицательной оценкой) строится замкнутый цикл. Для этого из выбранной свободной клетки проводится по строке или столбцу прямая линия до любой занятой клетки, затем под углом 90 линия проводится до следующей занятой клетки и так до тех пор пока цепь не замкнется в исходной клетке (цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Каждое звено цепи соединяет две клетки строки (столбца). Для свободной клетки всегда можно построить единственный цикл. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободной клетки).

5. В вершинах цепи, чередуя проставляются знаки «+» и «–», начиная с выбранной свободной клетки (в нее помещают знак «+»). В клетках со знаком «–» выбирается минимальная поставка (, которая перераспределяется по цепи: там, где стоит знак «+» она прибавляется, а где «–» – отнимается. В результате чего баланс цикла не нарушается. Исходная свободная клетка становится занятой, а клетка в которой выбрана минимальная поставка – свободной (рис.3.1 а, б)

                       а)                                                                       б)      

       +                            –                                           20                  20

                                           40                              

 

       –                            +                                                                       80

      20                            60

 

  

        

Рис.3.1

 

Может случится, что найденное наименьшее число (  одинаково для нескольких клеток цепи, помеченных знаком «–» (рис.3.2а). В этом случае во всех таких клетках (с минимальными стоимостями), кроме одной, нужно оставить нулевые (фиктивные) поставки (рис.3.2б).

 

                          а)                                                                                      б)      

        + 4                                    – 3                                                                        33

                                                           20                                20

                                       –             +                                                       10           30            

                                  30              10                                                                   

 

          – 2              +                                                           0          60        

         20               40             

                                                        Рис.3.2

 

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

 

Пример решения транспортной задачи линейного программирования

 

На четырех текстильных предприятиях В ₁, В ₂, В ₃, В ₄ изготавливается в день соответственно 20,120,20 60 м² тканей одного типа. Из этих тканей на трех автоматизированных швейных фабриках А ₁, А ₂, А ₃ изготавливаются пододеяльники в количестве соответственно 100,70 и 50 м². Известны стоимости перевозки (табл. 3.2) 1м² тканей из каждого пункта производства в каждый пункт потребления (ден. ед./ м²).

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

РЕШЕНИЕ.

Исходное опорное решение получим по методу «северо-западного угла» (табл. 3.3) и по методу min элемента (табл.4).

Здесь ,т.е имеем закрытую модель ТЗ (табл. 3.2).

 

Табл. 3.2. Исходные данные

Bj      Ai	20	120	20	60
100	6	4	2	4
70	1	2	7	2
50	2	4	1	4

 

Табл. 3.3. Решение методом «северо-западного» угла

Bj Ai	20	120	20	60
100	6 20	4 80	2	4
70	1	2 40	7 20	2 10
50	2	4	1	4 50

 

Транспортные расходы f=

 

Табл. 3.4. Решение методом min элемента

Bj         Ai	20	120	20	60
100	6	4 100	2	4
70	1 20	2	7	2 50
50	2	4 20	1 20	4 10

 

f=

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

Количество заполненных клеток в табл. 3.4 равно 6: m+ n -1=3+4-1=6.

Следовательно, полученный план невырожденный.

Для определения потенциалов (см. формула 3.8) составляем уравнения:

 

u₁+v₂=4, u₂+v₁=1, u₂+v₄=2, u₃ +v₂=4, u₃+v₃=1, u₃+v₄=4.

Положим u₁=0, тогда v₂=4, u₃=0, v₃=1, v₄=4, u₂=-2, v₁=3.

 

Потенциалы проставлены в табл. 3.5 (последняя строка и последний столбец). Их можно вычислять и непосредственно в таблице не выписывая систему уравнений. Т.к. если известны потенциал и тариф (стоимость перевозки) занятой клетки, то из соотношения u_i+ v_j= c_ij легко определить неизвестный потенциал (из суммы вычесть известное слагаемое, получим неизвестное слагаемое. Роль суммы в данном равенстве играет тариф c_ij)

Определим по формуле (3.9) оценки свободных клеток:

 

s₁₁=6-(0+3)=3>0, s₁₃=2-(0+1)=1>0, s₁₄=4-(0+4)=0

s₂₂=2-(-2+4)=0, s₂₃=7-(-2+1)=8>0, s₃₁=2-(0+3)= -1<0

 

табл. 3.5. Исходный план                                табл. 3.6. Новый план

Bj Ai	20	120	20	60	ui		Bj Ai	20	120	20	60	ui
100	6	4 100	2	4	0		100	6	4 100	2	4	0
70	– 1 20	2	7	+ 2 50	-2		70	- 1 10	+ 2	7	2 60	-1
50	2 +	4 20	1 20	– 4 10	0		50	+ 2 10	- 4 20	1 20	4	0
vi	3	4	1	4			vj	2	4	1	3

 

План неоптимальный, т.к. s₃₁<0. Строим для клетки (3;1) цикл непосредственно в табл. 3.5. В цикл войдут клетки (3;1), (3;4), (2;4), (2;1). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком,  В результате смещения  по циклу получим новый план (табл.6). Транспортные расходы  (а были равны 660).

Будет ли полученный план оптимальным? План невырожденный.

Определим для него новые потенциалы:

u₁+v₂=4, u₂+v₁=1, u₂+v₄= 2, u₃+v₁=2, u₃+v₂=4, u₃+v₃=1. Положим u₁=0, тогда v₂=4, u₃=0, v₁=2, v₃=1, u₂= -1, v₄=3. Проставим значения найденных потенциалов в табл.6.

Определим оценки свободных клеток:

s₁₁=6-(0+2)=4>0, s₁₃=2-(0+1)=1>0, s₁₄=4-(0+3)=1>0

s₂₂=2-(-1+4)=-1<0, s₂₃=7-(-1+1)=7>0, s₄₄=4-(0+3)=1>0.

План (табл. 3.6) неоптимальный, т.к. s22<0. Строим для клетки (2;2) цикл непосредственно в табл.6. В цикл войдут клетки (2;2), (2;1), (3;1), (3;2). Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком,  В результате смещения  по циклу получим новый план (табл. 3.7). План невырожденный. Транспортные расходы

f =  (а были равны 650).

 

Табл. 3.7. Новый план

Bj         Ai	20	120	20	60	ui
100	6	4 100	2	4	0
70	1	2 10	7	2 60	-2
50	2 20	4 10	1 20	4	0
vj	2	4	1	4

 

Будет ли полученный план оптимальным?

Определим для него новые потенциалы:

u₁+v₂=4, u₂+v₂=2, u₂+v₄=2, u₃+v₁=2, u₃+v₂=4, u₃+v₃=1. Положим u₁=0, тогда v₂=4, u₂=-2, v₄=4, u₃=0, v₁= 2, v₃=1. Проставим значения найденных потенциалов в табл.7.

Определим оценки свободных клеток:

s₁₁=6-(0+2)=4>0, s₁₃=2-(0+1)=1>0, s₁₄=4-(0+4)=0

s₂₁=1-(-2+2)=1>0, s₂3=7-(-2+1)=8>0, s₃₄=4-(0+4)=0

Оценки свободных клеток неотрицательны, следовательно, полученный план является оптимальным:

x ₁₂=100, x ₂₂=10, x ₂₄=60, x ₃₁=20, x ₃₂=10, x ₃₃=20

Минимальные транспортные расходы для этого плана f =640.

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

ОТВЕТ.

Согласно оптимальному плану, с первого текстильного предприятия A₁ нужно поставить 100м² тканей на вторую швейную фабрику B₂, с текстильного предприятия А₂ – 10м² на швейную фабрику В₂ и 60м² на швейную фабрику В₄, с текстильного предприятия А₃ – 20м² на швейную фабрику В₁, 10м³ на швейную фабрику В₂ и 20м² на строительную площадку В₃.

Лекция 5. Теория игр

 

Основы теории игр

 

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

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

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

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

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

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

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

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

Элементами игры являются ходы, представляющие собой определённую последовательность этапов развития партии. Например, в шахматах перестановка пешки с «Е2» на «Е4».

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

Личный ход – осознанный ход одного из игроков. Решение, принятое игроком при личном ходе, называется выбором. Например, каждый ход в шахматах является личным ходом, причём первый ход – выбор из 20 возможных вариантов (восемь пешек и два коня по две возможных позиции, т.е. 8 ´2+2 ´2=20).

Случайный ход – ход одного из игроков, в результате воздействия на него какого-либо случайного процесса. Этот случайный процесс реализуется каким-либо механизмом: сдача карт, бросание монеты, прибор типа Гальтона и т.п. Выбор, осуществляемый при случайном ходе, называется исходом этого хода. Например, выбор ворот и право первого удара в футболе определяется подбрасыванием монеты судьёй.

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

По отношению к ходам правила игры имеют следующую структуру (рисунок 5.1).

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

 

Рисунок 5.1 – Структура правил игры

 

Для каждого следующего хода правила определяют в зависимости от выборов и исходов предыдущих ходов:

- будет этот ход личным или случайным;

- если он будет случайным ходом, то представляющиеся варианты и вероятности их выбора;

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

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

Важным понятием теории игр является понятие стратегии.

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

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

Определение оптимальных стратегий игроков в условиях КС является основной задачей теории игр, основывающаяся на основном принципе: «противник (второй игрок) также умён, как и первый игрок!».

Существует следующая классификация игр по основным признакам (рисунок 5.1).

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

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

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

ИГРЫ