Алгоритмы по математике
Методическое пособие - Математика и статистика
Другие методички по предмету Математика и статистика
?ательных свободных членов выбрать максимальный по модулю. Соответствующая строка - разрешающая.
.Среди всех отношений коэффициентов целевой функции к отрицательным элементам разрешающей строки выбрать минимальное по модулю. Соответствующий столбец - разрешающий.
.Далее решение аналогично основному симплекс-методу, начиная с пункта 4.
Алгоритм смешанного симплекс-метода (существуют и )
- Начать решение основным симплекс-методом, при этом уравнения с отрицательной правой частью не рассматриваются при определении разрешающей строки (т.е. соответствующие им базисные переменные нельзя выводить из базиса на этом этапе).
После того, как коэффициенты целевой функции станут , а среди правых частей уравнений ограничений существуют , продолжить решение двойственным симплекс-методом.
Решение ЗЛП методом искусственного базиса
Если в системе ограничений существуют неравенства (со знаками или >) или уравнения (без переменных, создающих канонический вид), то для создания канонического вида стандартной формы удобно использовать метод искусственного базиса.
При решении ЗЛП методом искусственного базиса неравенства ограничений сначала приводят к системе уравнений. После этого в уравнения без переменных, создающих канонический вид, вводят искусственные переменные. Так как в уравнения вводятся неотрицательные переменные, то для соответствия новой задачи исходной, необходимо, чтобы искусственные переменные были равны нулю. Для этого составляется целевая функция , равная сумме всех введенных искусственных переменных. Функцию G необходимо выразить через неискусственные переменные и ввести в симплекс-таблицу. При определении разрешающего столбца в симплекс-таблице выбирают максимальный по модулю отрицательный коэффициент функции (при неискусственных переменных). Когда коэффициенты целевой функции при неискусственных переменных равны нулю, а при искусственных переменных коэффициенты равны 1 (т.е. сумма всех искусственных переменных равна нулю), тогда вычеркивается строка со вспомогательной функцией и переходят к строке целевой функции для определения разрешающего столбца и продолжают решение. Если в процессе решения получается, что все коэффициенты в строке (при неискусственных переменных) положительные, то задача неразрешима (допустимая область значений пуста).
Устойчивость решений ЗЛП при изменении параметров
Если известно решение исходной задачи, то приведенные ниже формулы расчета симплекс-таблицы позволяют найти оптимальное решение задачи, при незначительном изменении ее параметров, не решая задачу заново. Матрица , составленная из оптимальной таблицы (из коэффициентов в столбцах тех переменных, которые были базисными в исходной (нулевой) таблице) называется обращенным базисом.
Симплекс-множители находятся в целевой функции оптимальной таблицы под обращенным базисом .
Ниже представлены расчетные формулы, где значения , берут в нулевой (исходной) таблице, а значения в данной (вычисляемой) таблице.
Формулы расчета симплекс-таблицы с помощью обращенного базиса и симплекс-множителей
Элементы таблицыФормулыСтолбцыСтолбец свободных членовКоэффициенты при переменных , Целевая функция в столбце ,
Решение двойственных задач линейного программирования
Общий вид прямой задачи:
Общий вид двойственной задачи
Правила построения двойственной задачи:
1.Число неизвестных двойственной задачи равно числу ограничений прямой задачи. Число ограничений двойственной задачи равно числу переменных прямой задачи.
2.Если целевая функция прямой задачи ориентирована на максимум, то целевая функция двойственной задачи ориентирована на минимум. В прямой задаче на максимум ограничения необходимо записать со знаками или .
.Матрица коэффициентов двойственной задачи является транспонированной матрицей коэффициентов прямой задачи.
.Коэффициенты целевой функции двойственной задачи являются свободными членами ограничений прямой задачи.
.Если ограничение в прямой задаче задано в виде уравнения, то соответствующая ему переменная в двойственной задаче не определена по знаку. В остальных случаях .
.Если какая-либо переменная в прямой задаче не определена по знаку, то соответствующее ограничение двойственной задачи задается в виде уравнения. В остальных случаях знак неравенства .
Решение парных матричных игр с нулевой суммой
Упрощенная, формализованная модель конфликтной ситуации называется игрой, а конфликтующие стороны - игроками. При решении парных матричных игр строки матрицы соответствуют стратегиям первого игрока, а столбцы - стратегиям второго игрока.
Нижняя цена игры
- гарантированный минимальный выигрыш первого игрока (максиминная стратегия).
Верхняя цена игры
- гарантированный максимальный проигрыш второго игрока минимаксная стратегия.
Если , то имеем игру с седловой точкой. Иначе - цена игры C:
Решить игру можно графически (если имеется игрок с двумя стратегиями) или как пару двойственных задач линейного программирования.
Алгоритм решения игры графическим методом
. Вероятности игрока, имеющего две стратегии, отмечают на горизонтальной числовой оси. В точках 0 и 1 восстанавливают два перпендикуляра, на которых отмечают стратегии др?/p>