Элементы таблицы
|
Формулы
|
Столбцы
|
|
Столбец свободных членов
|
|
Коэффициенты при переменных ,
|
|
Целевая функция в столбце ,
|
|
Решение
двойственных задач линейного программирования
Общий вид прямой задачи:
Общий
вид двойственной задачи
Правила
построения двойственной задачи:
1. Число неизвестных двойственной задачи равно числу ограничений
прямой задачи. Число ограничений двойственной задачи равно числу переменных
прямой задачи.
2. Если
целевая функция прямой задачи ориентирована на максимум, то целевая функция
двойственной задачи ориентирована на минимум. В прямой задаче на максимум
ограничения необходимо записать со знаками «» или «».
. Матрица
коэффициентов двойственной задачи является транспонированной матрицей
коэффициентов прямой задачи.
. Коэффициенты
целевой функции двойственной задачи являются свободными членами ограничений
прямой задачи.
. Если
ограничение в прямой задаче задано в виде уравнения, то соответствующая ему
переменная в двойственной задаче не определена по знаку. В остальных случаях .
. Если
какая-либо переменная в прямой задаче не определена по знаку, то
соответствующее ограничение двойственной задачи задается в виде уравнения. В
остальных случаях знак неравенства .
Решение
парных матричных игр с нулевой суммой
Упрощенная, формализованная модель конфликтной ситуации называется игрой,
а конфликтующие стороны - игроками. При решении парных матричных игр строки
матрицы соответствуют стратегиям первого игрока, а столбцы - стратегиям второго
игрока.
Нижняя цена игры
-
гарантированный минимальный выигрыш первого игрока («максиминная стратегия»).
Верхняя
цена игры
-
гарантированный максимальный проигрыш второго игрока «минимаксная стратегия».
Если
, то имеем игру с седловой точкой. Иначе - цена игры
C:
Решить
игру можно графически (если имеется игрок с двумя стратегиями) или как пару
двойственных задач линейного программирования.
Алгоритм
решения игры графическим методом
.
Вероятности игрока, имеющего две стратегии, отмечают на горизонтальной числовой
оси. В точках 0 и 1 восстанавливают два перпендикуляра, на которых отмечают
стратегии другого игрока, соединяя их отрезками.
.
Если первый игрок имеет две стратегии (в матрице 2 строки), то на нижней ломаной
выбирают самую верхнюю точку (вершину). Если второй игрок имеет две стратегии,
то на верхней ломаной выбирают нижнюю точку.
.
Длина перпендикуляра, опущенного из полученной вершины на числовую ось, равна
цене игры C. Причем
4.
Стратегии, участвовавшие в определении данной вершины, называются активными
стратегиями. С их помощью составляются системы уравнений для определения
вероятностей использования игроками своих оптимальных стратегий.
Алгоритм
сведения матричной игры к ЗЛП
1.
По теореме о цене игры
и
Зная,
что , ,
предполагают
2.
Получают прямую и двойственную задачу линейного программирования
, ;
,
3.
Решив ЗЛП, определить цену игры можно по формуле
а
вероятности .
Решение
статистической игры
Игры, в которых один противник "природа", а другой - человек
или один из игроков действует не сознательно, а в соответствии с определенными
законами, называются играми с "природой" или статистическими играми.
Для
составления матрицы рисков определяют
разности между максимальным выигрышем, который получил бы игрок, зная состояние
природы, и выигрышем, который получит игрок, применяя стратегию.
Если
известно распределение вероятностей состояний «природы»
то
используют критерий Байеса
(максимум
математического ожидания выигрыша) или
(минимум
математического ожидания риска).
Если
распределение вероятностей состояний "природы" неизвестно, то
используют:
а)
принцип "недостаточного основания Лапласа", где каждое состояние
природы равновероятно, т.е. р1=р2=...= рn=1/n;
б)
максиминный критерий Вальда: ;
в)
критерий минимального риска Сэвиджа: ;
г)
критерий Гурвица:
где
при
=0 - крайний оптимизм, при =1 - крайний пессимизм
Решение
транспортной задачи методом потенциалов\
Исходные данные
Если
то
имеем закрытую модель задачи. Если
то
данную открытую модель задачи, необходимо свести к закрытой модели, введя
недостающего фиктивного потребителя или поставщика с нулевыми тарифами.
Опорный
план строится тремя методами: северо-западного угла, минимального элемента и
аппроксимации Фогеля:
а) метод северо-западного угла: заполнение клеток таблицы начинается с
левой верхней клетки ("северо-западной"), в которую ставят
максимально возможное число, т.е. минимальное из чисел запасов и потребностей
для этой клетки. При этом исчерпываются либо запасы, либо потребности
(вычеркивается строка или столбец), выбирается следующая «северо-западная» клетка
и т.д. Число заполненных клеток равно m+n-1. Если на каком-либо шаге
вычеркиваются одновременно поставщик и потребитель, то в клетку,
соответствующую данному методу, ставится 0-поставка;
б) метод минимального элемента: заполнение клеток осуществляется по
принципу: "самая дешевая перевозка осуществляется первой". Выбирается
клетка с минимальным тарифом и заполняется максимально возможным числом, при
этом исчерпываются либо запасы, либо потребности (вычеркивается строка или
столбец), выбирается следующая клетка с минимальным тарифом и т.д. Если на
каком-либо шаге вычеркиваются одновременно поставщик и потребитель, то ставится
0-поставка в данной строке или столбце в клетку с минимальным тарифом;
в) метод аппроксимации Фогеля: во всех строках и столбцах найти разности
между двумя минимальными тарифами, записать их, соответственно, справа и внизу
таблицы. Среди найденных разностей выбирают максимальную. В строке (или
столбце), которой соответствует данная разность, заполняют клетку с минимальным
тарифом. Если максимальных разностей несколько одинаковых, выбирают ту, которой
соответствует минимальный тариф. Если минимальный тариф одинаков для нескольких
клеток в строке (столбце), то заполняют ту, которая стоит в столбце (строке),
имеющем наибольшую разность между двумя минимальными тарифами.
Среди полученных опорных решений выбирают план с минимальной стоимостью
перевозок и проверяют его на оптимальность:
1)
вычисляют потенциалы поставщиков и потребителей
из условия для всех
занятых клеток (при условии );
)
определяют оценки всех свободных клеток.
Если
все , то план является оптимальным (наличие равных 0
оценок свидетельствует о неоднозначности оптимального плана). Если существуют , то построенный план не оптимален. Для его улучшения
среди всех выбирают максимальное и для соответствующей свободной
клетки строят цикл пересчета:
1) цикл изображают в таблице в виде замкнутой ломаной линии. В любой
занятой клетке цикла возможен поворот линии на 900;
) отмечают вершины цикла пересчета (там, где линия поворачивает)
последовательно знаками "+" и "-" , начиная с "+"
в исходной клетке. Среди поставок, стоящих в "-" клетках, определяют
минимальную. К значениям, стоящим в "+" клетках, прибавляют эту
поставку, а из значений, стоящих в "-" клетках, ее вычитают;
) по этому циклу перераспределяются объемы перевозок. Перевозка
загружается в выбранную свободную клетку и освобождается одна из занятых
клеток, получается новое опорное решение, которое нужно проверить на
оптимальность.
Решение
транспортной задачи методом дифференциальных рент
Алгоритм решения транспортной задачи методом дифференциальных рент
1) В каждом столбце отметить клетку с минимальным тарифом.
) В эти отмеченные клетки максимально распределить груз. Сначала в
клетки, единственные отмеченные в строке и столбце, потом единственные в
столбце или в строке с минимальными тарифами.
) Необходимо получить оценки поставщиков:
а) если поставщик не все вывез, то его оценка «+n», где n - количество
оставшегося груза у данного поставщика;
б)
если все запасы исчерпаны, а потребности потребителей не удовлетворены с учетом
распределения по всему столбцу, то оценка поставщика «-», где -
количество груза, необходимого потребителям в отмеченных столбцах данной
строки, с учетом того груза, который, возможно, получил потребитель от других
поставщиков. Потребности потребителя, которому не хватило товара, при оценке
поставщиков учитываются один раз;
в)
если все запасы поставщика исчерпаны и в отмеченных клетках столбцов
потребитель удовлетворен с учетом всего столбца, то оценка «0». Знак нуля: если
отмеченная клетка в строке связана в столбце с отмеченной клеткой только в
отрицательной строке, то знак у нуля «-». В остальных случаях знак «+».
)
Для каждого столбца найти ренту: разницу между отмеченным тарифом в
«отрицательной» строке и минимальным тарифом в «положительной» строке.
)
Выбрать минимальную не нулевую разность, которая называется промежуточной
рентой.
)
Промежуточная рента добавляется к тарифам в отрицательных строках. После чего
составить новую таблицу с измененными тарифами и перейти к пункту 1 данного
алгоритма. Если все оценки равны 0, то найдено оптимальное решение.
Замечания:
)
Сумма всех оценок в каждой таблице должна быть равна 0.
)
При подсчете общей стоимости перевозки использовать исходные тарифы, а не те,
которые получились в последней таблице.
Решение
транспортной задачи с дополнительными ограничениями\
Если даны дополнительные ограничения в транспортной задаче
то
в таблице данные изменятся
а)
если , то
б)
если , то
в)
если , то столбец разбивается
на два столбца:
и
В
найденном решении поставки в этих столбцах суммируются.
Метод динамического
программирования
Метод динамического программирования состоит в том, что оптимальное
управление строится постепенно, шаг за шагом.
I. Задача об
оптимальном распределении ресурсов состоит в том, что предприятие имеет
возможность выделить С ден.ед. n филиалам (в зависимости от вложенной суммы филиал дает прирост прибыли ) с целью максимизации прибыли предприятия.
симплексный преобразование алгоритм базисный переменный
Алгоритм решения задачи об оптимальном
распределении ресурсов
1.
Составляется таблица, где вводят последовательность функций - максимальная прибыль фирмы, если х средств выделить
одновременно
Очевидно,
что
2.
Выполняется «обратный ход»:
а)
по определению
б)
средства в объеме x распределяются между первым и вторым филиалами:
второму в объеме x2 ден.ед.,
тогда средств выделяется первому филиалу. Общая прибыль
двух филиалов
в)
включается в рассмотрение 3-й филиал: из общей суммы х выделяется третьему
филиалу х3 ден.ед., тогда остальная часть средств оптимальным образом распределяется между двумя первыми
филиалами; общая прибыль
г)
аналогично находится
и т.д.
3.
Выполняется «прямой ход»:
находится
и оптимальное такое,
что , после чего результаты вычислений просматриваются в
обратном порядке. Зная , находят - объем
финансирования остальных n-1 филиалов, а следовательно, и и , и т.д.
до нахождения и .
II. Пусть
известны: возраст оборудования на начало планового периода лет, остаточная стоимость оборудования s(t) ден.ед.,
цена нового оборудования p ден.ед., стоимость продукции , произведенной за 1 год на оборудовании возраста и издержки на
обслуживание оборудования возраста . Для
расчета оптимальной стратегии предприятия по замене оборудования вводят функцию
- максимальная прибыль за последние i лет
планового периода. Очевидно, что
Алгоритм решения задачи о замене оборудования
1. Определить из условия задачи
,
и
справа таблицу дополнить столбцом .
.
Заполнить строку, переписав из таблицы данных соответствующие значения
, а все значения заменить
числом
, т.о.,
3.
Начиная с индекса i = 2, расчет по строкам производится в соответствии с
формулами
т.е.
в следующей последовательности:
а)
вычислить
б)
вычислить
Получаемые
значения вносить в соответствующие клетки строки, но начиная с
первого , оставшиеся клетки заполнить значением mi;
в)
клетки с первым значением в процессе заполнения таблицы отделить от значений,
расположенных в строке левее, разделительной границей смены управления;
г)
аналогично продолжить заполнение таблицы до последней строки, т.е. перейти к п.
а) данного алгоритма.
.
Дойдя до последнего шага (i=n), попадаем в начало планового периода, начинают
”прямой ход”: задавая t0 и
длительность планового периода, находим и строим
последовательность оптимальных управлений, начиная с первого года и заканчивая
последним.
Замечание:
используя полученные расчетные таблицы для задачи об оптимальном распределении
капиталовложений и о замене оборудования, можно получить решение с изменением
(уменьшением) исходных данных (количества филиалов, выделенных средств или
планового периода соответственно). Это так называемый «принцип погружения»
метода динамического программирования.
III. Пусть спрос
потребителей на продукцию составляет на 1-й, 2-й, 3-й этапы d1, d2,
d3 единиц соответственно. К началу первого этапа на складе имеется y1
единицы продукции. Затраты на хранение единицы продукции на разных этапах
различны и составляют соответственно h1, h2, h3.
Затраты на производство хj единиц на j-ом этапе определяются
функцией , . Для
нахождения оптимального количества производимой на каждом этапе продукции,
чтобы заявки были удовлетворены, а общие затраты на производство и хранение за
все три этапа были наименьшими, решение проводят по алгоритму.
Алгоритм
решения задачи о производстве и хранении продукции
1.
Составляется таблица значений функции затрат на производство
, где
2.
Выполняется «обратный ход»: составляются функциональные уравнения
минимальные
затраты за первые k месяцев, ограничения по величине запаса к концу k-го
месяца
,
балансовое уравнение
,
а
из него получают ограничении
а)
для k=1: составляются ограничения
,
а
также таблица значений функции
б)
для k=2: в зависимости от значений переменой
составляются
ограничения
,
а
также вспомогательные таблицы значений функции
Для
каждого значения выбирается минимальное значение и соответствующее ему значение ;
в)
для k=3: составляются ограничения
, (причем ),
а
также таблица значений функции
3.
Выполняется «прямой ход»:
а)
для определяют , из
балансового уравнения
выражают
;
б)
зная , из таблицы значений определяют
, а из балансового уравнения
выражают
;
)
зная , из таблицы значений определяют
;
г)
суммарные затраты за весь период .
Задачи
планирования на сетях
Граф геометрически представляет собой множество точек, называемых
вершинами, соединенных линиями: а) направленными, которые называются дугами и
обозначаются стрелками, или б) ненаправленными, которые называются ребрами.
Граф без петель можно задать матрицей инциденций A, строки которой соответствуют вершинам, а столбцы - дугам,
причем элементы матрицы A
определяются по формуле
Граф можно задать матрицей смежности вершин S, строки и столбцы которой соответствуют вершинам графа,
причем элементы матрицы sij равны числу дуг/ребер, идущих из хi в хj.
Графический способ упорядочения вершин (алгоритм
Фалкерсона)
1. Находятся вершины графа, в которые не входит ни одна дуга. Такие
вершины образуют первую группу.
. Вершины и выходящие из них дуги установленной группы исключаются из
дальнейшего рассмотрения.
. Устанавливается следующая группа вершин, в которые не входит ни одна
дуга.
. Если процесс упорядочения не окончен, то переход п. 2.
. В полученном графе, изоморфном исходному, перенумеровываются вершины.
Алгоритм решения задачи о максимальном потоке
. Построить начальный поток
2.
На основе заданной сети построить новую сеть:
а)
каждая дуга, для которой остаётся в новой сети с первоначальной rij;
б)
каждая дуга, для которой , заменяется на две: одна - того же направления с
пропускной способностью rij-; а вторая - противоположенного направления с
пропускной способностью .
.
Если в новой сети можно найти ненулевой поток из I в S, то
этот поток прибавляется к начальному. В результате получается новый поток и переходят к п. 2. Если ненулевой поток найти
невозможно, то поток максимальной мощности построен.
Алгоритм
расчета параметров сетевого графика
1) Изобразить события сетевого графика четырехсекторными кругами;
) перемещаясь по сетевому графику от истока к стоку по возрастанию
номеров событий, найти все ранние сроки наступления событий по формулам:
(исток)
и , где
3)
перемещаясь по сетевому графику от стока к истоку по мере убывания номеров
событий, найти поздние сроки наступления событий
(сток) и
,
4)
определить резерв времени каждого события ;
)
выделить критический путь - последовательность работ и событий, не имеющих
резервов времени;
)
вычислить свободный резерв времени и полный
резерв времени каждой работы .