Лгоритм метода потенциалов

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

2.Найти начальное решение Х0 методом минимальной стоимости или методом Северо-западного угла.

3.Проверить решение на вырожденность с помощью необходимого условия.

N=m+n-1,

где m – число поставщиков, n – число потребителей, а N – число заполненных клеток.

Если число заполненных клеток (ненулевых компонент плана Х0 системы ограничений) равно m+n-1, то в этом случае решение называется невырожденным, а если число ненулевых решений не равно m+n-1, то такое решение называется вырожденным (вводится значимый нуль в клетку с минимальным значением Cij из оставшихся так, чтобы можно было найти потенциалы (U,V).

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

4.1. Вычислить потенциалы.

Потенциалы находят из решения системы:

Cij = Ui+Vj,

U1=0,

где Ui, Vj – потенциалы, переменные двойственной задачи

Cij – стоимость перевозки единицы груза

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

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

5. Построить новый план

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

Цикл может быть представлен следующими фигурами:

5.2.Помечаем вершины цикла знаками «+» и «?» поочередно, начиная с разрешающего элемента.

5.3.Находим величину сдвига по циклу — минимальный из элементов цикла, помеченных знаком «?»:

?= min {xij}-, xij € Z, где Z — цикл

5.4.Строим новый план х1, добавляя или вычитая, в соответствии со знаками, величину ? к элементам цикла. И переходим на пункт 4.

6. Решить задачу в среде Microsoft Exсel, приложить отчет.

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

Имеется 4 оптовых склада с запасами однородного груза 41; 33; 25; 14. Имеются 5 магазинов с заказами на однородный груз соответственно. Обозначим хij-количество груза, перевозимого со склада А1 в магазин bj. Матрица перевозок задана в следующем виде:

Таблица 2.1 – Исходные данные

Условия разрешимости:

-задача закрытая

1. Математическая модель прямой ТЗ:

Двойственная задача составляется для следующих переменных:

U – переменные для складов или поставщиков;

V — переменные для магазинов или потребителей.

Математическая модель двойственной ТЗ:

Ограничения представлены на другой странице.

2.Нахождение начального решения методом Северо-Западного угла

Таблица 2.3 – Нахождение начального решения методом минимальной стоимости

Значение целевой функции L(x0) при начальном решении по методу минимальной стоимости меньше, чем по методу северо-западного угла, поэтому примем его за начальное решение.

2. Проверка решения х0 на вырожденность

Количество ненулевых элементов в решении х0 равно 8, проверим условие N= m + n -1= 4 + 5 — 1=8, т.е. решение х0 не является вырожденным.

Таблица 2.4. Проверка плана х0 на оптимальность.

		Ui

	12
			-2

			-1
Vj

План х0 не является оптимальным, т.к. есть два положительных решения и .

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

X34 – разрешающий элемент 0*. Минимальная поставка для отрицательных вершин

?1=min 8,14 =8.

. Организуем следующий цикл:

+25 8 — 33 0

— 14 ? + 6 8

Таблица 2.5 – Проверка плана х’ на оптимальность

		Ui

	12
			-2

			-1
Vj

план не оптимальный.

– разрешающий элемент 0*. Минимальная поставка для отрицательных вершин

?2=min 31,6 = 6.

Организуем второй цикл:

31 0 25 6

3 6 9 0

Строим новый план х2,

Таблица 2.6 – Проверка плана х2 на оптимальность

			Ui

	12


				-1
Vj		-2

Все Оптимум достигнут

ед.

План оптимален, но – это признак альтернативного оптимума, х41 – разрешающий элемент, находим альтернативные решения х3.

— + + —

25 10 11 24

? 14 14 0

ед.

Ответ: ед., ,

4. Решить транспортную задачу в среде Excel

В ячейках А1-Е5 вводим тарифы:

В ячейках G1-5 задаем запасы, а в ячейках А6-Е6 – заказы:

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

Отдельно задаем ячейку целевой функции, используя встроенную функцию СУММ ПРОИЗВ:

В ячейках F9-12 задаем суммы по строкам, а в ячейках А13-Е13 – по столбцам:

В окне Поиска решения в Параметрах выбираем метод сопряженных градиентов:

Задаем ограничения и изменяемые ячейки:

Получим решение:

ешение матричных игр

лгоритм решения

1.Проверить, имеет ли игра решение в чистых стратегиях

1.1. Найти целевую функцию первого игрока V1. Из всех чисел по строкам выбираем минимальные, а затем среди них выбираем максимальное значение:

V1=? = max min hij

i j

1.2. Найти целевую функцию второго игрока. Из всех чисел столбцов выбираем максимальные значения, а затем из них выбираем минимальное значение:

V2=? = min max hij

j i

1.3. Если ? = ?, то игра имеет решение в чистых стратегиях.

Если ? ? ?, то игра решается в смешанных стратегиях.

2. Решение игры в смешанных стратегиях:

2. 1. Упростить игру с помощью правил доминирования.

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

2. 2. Если после упрощения получили игру размерности [2 х 2], то находим решение аналитически с помощью формул. Если получили игры размерности [2 х n] или [m х 2], то с помощью геометрического доминирования эти игры свести к игре размерности [2 х 2] и решить аналитически.

2.3. Если после упрощения игра осталась размерности [m x n], то найти ее решение сведением к задачам линейного программирования.

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

2.2 Примеры решения матричных игр размерности [2х2], [2хn], [mx2]

1) Решение игр размерности [2×2]

Х*