Открытая транспортная задача

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Постановка транспортной задачи рассмотрена в разделе 2.2.12, модель транспортной задачи имеет вид

, (2.13.1)

где – стоимость перевозок продукта от -го поставщика -му потребителю;

– неизвестный объем поставок продукта.

Ограничение по наличию продукта у поставщика

, , (2.13.2)

где – запас продукта у -го поставщика.

Ограничение на потребность продукта

, , (2.13.3)

где – потребность в продукте -го потребителя.

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

. (2.13.4)

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

Задача 2.2.13.1. Три овощеводческих хозяйства имеют запасы картофеля в объемах 300 т, 1200 т, 720 т и заключили договора на поставку картофеля в г. Барнаул на склад 1100 т, на спиртзавод 420 т и на товарную станцию ж-д 800 т. стоимости перевозок 1 т в денежных единицах приведены в матрице

Здесь – стоимость перевозки от -го поставщика -му потребителю 1 т картофеля.

Определить объемы поставок от каждого поставщика каждому потребителю.

Решение.

Задача является открытой, поэтому, необходимо введение «фиктивного поставщика» №1 с объемом поставки 2320–2220=100 т.

Транспортная таблица имеет вид

Таблица 13.1

Хозяйства		Барнаул 1100	Спиртзавод 420	Ж-д станция 800
№1	300	80 300	20	40	0
№2	1200	100 700	50	20 500	–20
№3	720	70	10 420	30 300	–30
Ф.П.	100	0 100	0	0	80
		80	–20	0

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

; . ; .

Проверка оптимальности плана по небазисным клеткам имеет результата

нет оптимума.

;

План не оптимален, в клетку (1, 3) необходимо ввести базисный объем перевозок в 300 единиц. Строится цикл перемещения этого объема. Новая транспортная таблица имеет вид.

Таблица 13.2

		Барнаул 1100	Спиртзавод 420	Ж–д станция 800
№1	300	80 300	20	40	–40
№2	1200	100 400	50	20 800	–60
№3	720	70 300	10 420	30	–30
Ф.П.	100	0 100	0	0	40
		40	–20	–40

Новая система потенциалов начинается с клетки (2,3), поскольку она не перетерпела изменений.

; . ; .

; .

Проверка оптимальности оценками небазисных клеток

;

Получаем оптимальный план, оценки клеток отрицательны.

Решение в виде матрицы

Потребитель «Барнаул» не получит 100 т.

2.2.14 Матричные игры.
Игры и

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

Игра называется с нулевой суммой, если один игрок выигрывает столько, сколько проигрывает другой.

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

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

Рассматривается игра, где игрок имеет стратегий, а игрок (противник) – стратегий.

Личные ходы однозначно определяют игру, – исход игры, выигрыш -го игрока при -м ходе противника.

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

Значения при выборе стратегий и можно отразить матрицей

. (2.14.1)

Антагонистическая игра, в которой каждый игрок имеет конечное множество стратегий называется матричной.

При задании платежной матрицы (2.14.1) игра называется матричной игрой. Стратегии первого игрока обозначаются номерами строк матрицы, стратегии второго игрока обозначаются номерами столбцов.

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

Найдем минимальное из чисел по строке :

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

(2.14.2)

– это нижняя цена игры (максиминный выигрыш).

Стратегия , которая дает такой выигрыш – максиминная стратегия.

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

Максимальное значение выигрыша по столбцам

Из них минимальное значение

(2.14.3)

является верхней ценой игры (минимальный выигрыш).

Придерживаясь такой стратегии, игрок гарантирован, что он проиграет не больше .

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

– чистая цена игры.

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

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

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

Если стратегии применяются с вероятностями соответственно , то обозначили смешанную стратегию

причем .

Аналогично для смешанной стратегии второго игрока

где .

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

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

. (2.14.4)

Наиболее простая игра с платежной матрицей

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

Решение может быть найдено из системы уравнений

(2.14.5)

Решение системы (2.14.5) является

, (2.14.6)

Цену игры можно найти подстановкой и в одно из уравнений (2.14.5).

Аналогично находится стратегия противника

из уравнений

(2.14.7)

откуда решение

(2.14.8)

Игра , где игрок имеет 2 стратегии, а игрок – стратегий, может быть сведена к игре .

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

У игры всегда имеется решение, в котором участвуют с каждой стороны 2 стратегии, которые являются активными. Если эти стратегии выделить, то игра превращается в игру и решение можно найти по формулам (2.14.6) и (2.14.8).

Задача 2.2.14.1. Найти решение игры, заданной матрицей

Решение .

1. Проверка на наличие седловой точки

, седловая точка отсутствует.

2. Графическое выделение активных стратегий.

На оси откладываем отрезок [0, 1] и строим стратегии .

Активные стратегии и , им соответствует матрица

3. Решение игры по формулам (2.14.6)

Определение цены игры по 1-му уравнению (2.14.5)

;

, откуда .

Для стратегии противника

; откуда ; .

Получили стратегии

; ;

и цена игры .

2.2.15 Матричные игры и
линейное программирование

Основные понятия теории игр содержатся в разделе 2.2.14.

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

, (2.15.1)

где – выигрыш игрока при -ой стратегии, при стратегии его противника.

Определяются два оптимальных плана в смешанных стратегиях

; ,

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

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

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

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

, . (2.15.2)

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

(2.15.3)

Разделим неравенства на и обозначим

, ,… , . (2.15.4)

В результате получим ограничения

(2.15.4)

и так как , то дополнительно

. (2.15.5)

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

. (2.15.6)

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

Обозначив

; ; … , (2.15.7)

получим задачу

, (2.15.8)

(2.15.9)

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


0,8	0,2	0,4
0,4	0,5	0,6
0,1	0,7	0,3

Сторона стремится воспрепятствовать боевой задачи. Найти решение задачи, т.е. вероятности .

Решение.

Освободимся от дроби, для чего элементы матрицы умножим на 10

Цена игры получит значение .

Задача для игрока примет вид

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

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

Канонический вид ее приведен ниже с добавлением переменных .