Математическая модель прямой задачи
Математическая модель двойственной задачи:
Экономический смысл переменных:
Z – целевая функция прямой задачи (суммарные затраты); Z ' – целевая функция двойственной задачи (суммарная потенциальная прибыль от перевозки груза); Сij – стоимость перевозки единицы продукции из i-го пункта в j-ый; Xij – объем перевозок от i-го поставщика j-му потребителю; Ui – условная плата перевозчику за вывоз единицы груза из i-го пункта отправления; Vj – условная плата перевозчику за доставку единицы груза в j-ый пункт назначения.
Проверяем на вырожденность: R=m+n-1=3+5-1=7 m= 3 – количество поставщиков; n = 5 – количество потребителей. Базисных клеток 7, план не вырожден.
Проверяем план на оптимальность, используя метод потенциалов. Для базисных клеток составляем систему уравнений Ui + Vj = Сij находим значение потенциалов так как переменных на 1 больше, чем уравнений, то переменной U3 присваиваем значение 0 и решаем систему уравнений, получаем
Проверяем выполнение неравенства в свободных: клетках Ui + Vj ≤ Сij
более всего не выполняется условие Ui + Vj ≤ Сij, сюда ставим «+W», строим контур перераспределения W и находим его значение:
Составляем следующий план:
Так как переменных на i больше, чем уравнений, то переменной U3 присваиваем значение 0 и решаем систему уравнений, получаем
проверяем выполнение неравенства в свободных клетках Ui + Vj ≤ Сij,
– более всего не выполняется условие Ui + Vj ≤ Сij, сюда ставим «+W», строим контур перераспределения W и находим его значение:
Составляем следующий план:
Проверяем выполнение неравенства Ui + Vj ≤ Сij, в свободных клетках:
Неравенство Ui + Vj ≤ Сij,в свободных клетках выполняется, построенной план является оптимальным.
Анализ решения.
1. Оптимальный план перевозки продукции: – от поставщика А1 перевозится 250 ед. продукции потребителю В1; 150 ед. продукции остается у поставщика; – от поставщика А2 перевозится 250 ед. продукции потребителю В2; 50 ед продукции остается у поставщика; – от поставщика А3 перевозится 100 ед.продукции потребителю В1, 150 ед, потребителю В3, 250 ед. потребителю В4.
2.Суммарные затраты на изготовление и перевозку продукции:
Контрольные вопросы. 1.Как сформулировать постановку транспортной задачи? 2.Какие величины в математической модели транспортной задачи постоянные и какие переменные? 3.Как составить математическую модель прямой и двойственной транспортной задачи? 4.Какая клетка в плане транспортной задачи называется «базисной» и какая «свободной»? 5.Приведите пример сбалансированной и несбалансированной транспортной задачи. Как сбалансировать исходный план транспортной задачи? 6.Поясните понятие «вырожденность» и «невырожденность» плана. Как построить «невырожденный» план? 7.Алгоритм метода наименьшего (наибольшего) элемента. 8.Метод потенциалов и его алгоритм. 9.Какой план транспортной задачи называется опорным? 10.Какой критерий оптимальности плана транспортной задачи? 11.Поясните понятие «коэффициент перераспределения груза – W» и как он определяется? 12.Как построить контур перераспределения W? 13.Анализ решения транспортной задачи.
4. Теория игр Основные понятия.
Теория игр - это математическая теория, исследующая конфликтные ситуации, в которых принятие решений зависит от нескольких участников. Математическая модель конфликтной ситуации называется игрой. Стороны, участвующие в конфликте - игроки, а исход конфликта - выигрыш (проигрыш). Выигрыш или проигрыш может быть задан количественно. Игра называется антагонистической или игрой с нулевой суммой, если выигрыш одного из игроков равен проигрышу другого, поэтому для полного «задания» игры достаточно указать величину выигрыша первого игрока. Стратегией игрока называется совокупность принципов, определяющих выбор его действий при каждом личном ходе в зависимости от сложившейся ситуации. Для того чтобы найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получать максимальный выигрыш, когда второй игрок придерживается своей стратегии. В тоже время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. При выборе оптимальной стратегии следует полагать, что оба игрока ведут себя разумно с точки зрения своих интересов. Матрица, элементы которой характеризуют прибыль первого игрока при всех возможных стратегиях (обозначается (αij)),называется платежной матрицей игры. Величина α = max min a ij называется нижней ценой игры. i j Величина β = min max a ij называется верхней ценой игры. j i В некоторых задачах, приводящихся к игровым, имеется неопределенность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупательский спрос и т.п.). Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности. Такие игры называются играми с природой. Человек в играх с природой старается действовать осмотрительно, второй игрок (природа и т.п.) действует случайно. При решении задач, относящихся к теории игр, необходимо правильно классифицировать задачу, потому что методы, применяемые к антагонистическим играм кардинально отличаются от методов решения игр с природой.
|
при условии что,
Перераспределяем W=50 по контуру.
перераспределяем W=100 по контуру.
ден. ед.
