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