лгоритм метода потенциалов
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. Математическая модель прямой ТЗ:
![]() | |||
![]() |
|
|
![](images/image-130-208.gif)
![](images/image-132-202.gif)
Двойственная задача составляется для следующих переменных:
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.
. Организуем следующий цикл:
|
- 14 ? + 6 8
Таблица 2.5 – Проверка плана х' на оптимальность
![]() ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | Ui | |
![]() | 12 ![]() |
![]() | |||||
![]() |
![]() | -2 | |||||
![]() |
![]() |
![]() |
![]() |
![]() | |||
![]() |
![]() | -1 | |||||
Vj |
план не оптимальный.
– разрешающий элемент 0*. Минимальная поставка для отрицательных вершин
2=min 31,6 = 6.
Организуем второй цикл:
|
|
3 6 9 0
Строим новый план х2,
Таблица 2.6 – Проверка плана х2 на оптимальность
![]() ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | Ui | |
![]() | 12 ![]() |
![]() |
![]() | ||||
![]() |
![]() | ||||||
![]() |
![]() |
![]() |
![]() | ||||
![]() |
![]() | -1 | |||||
Vj | -2 |
Все Оптимум достигнут
ед.
План оптимален, но
– это признак альтернативного оптимума, х41 – разрешающий элемент, находим альтернативные решения х3.
|
|
? 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) Решение игр размерности [2x2]
Х*
У*
Х*
У*
Проверка:
=
Ответ:
2) Решение игр размерности [mx2]
Целевая функция игроки 2:V2=min max HiYT, i=1,2,…,m.
yєS1 i
i = min hij j | V2 = max ii i |
-1 | |
j = max hij i | ||
V1 = min ii j |
Рис. 1. Геометрическая интерпретация исходной игры
С помощью геометрического доминирования исходная игра сведена к игре размерности [2х2]
,
,
.
Проверка:
X*HY*T =
Ответ:
3) Решение игр размерности [2xn]
Целевая функция игрока 1: V1=max min XHj, j=1,2,…,n.
xєS 1 j
i = min hij j | V1 = max ii i |
0.4 | 0.5 |
0.5 |
j = max hij i | 0.9 | ||
V2 = min ii j | 0.9 |
Рис. 2. Геометрическая интерпретация исходной игры
С помощью геометрического доминирования исходная игра свелась к игре размерности [2х2]
;
;
.
X*
Y* 5/11 0 6/11
Проверка:
Ответ: