Алгоритмы по математике

Стандартная форма ЗЛП имеет канонический вид, если в каждом уравнении системы ограничений существует переменная с коэффициентом +1, причем в других ограничениях и в целевой функции этой переменной нет, т.е. коэффициент равен 0. Каноническая форма называется допустимой, если все , иначе - недопустимой.

Алгоритм перехода к стандартной форме ЗЛП

Избавиться от переменных неопределенного знака. Для этого заменить каждую такую переменную разностью:

, где

Сориентировать целевую функцию , учитывая соотношение

.

Используя уравновешивающие переменные, преобразовать имеющиеся неравенства в уравнения.

Алгоритм перехода к каноническому виду стандартной формы ЗЛП

1. Избавиться от переменных неопределенного знака. Для этого необходимо заменить каждую такую переменную разностью

, где

Сориентировать целевую функцию , учитывая соотношение

В системе ограничений каждое уравнение без переменной, создающей канонический вид, записать в виде двух неравенств ().

Используя уравновешивающие переменные, преобразовать неравенства в уравнения.

При необходимости уравнения можно умножить на (-1).

Графический метод решения ЗЛП

Алгоритм решения ЗЛП графическим методом

1. Построить область допустимых решений: всем ограничениям системы ограничений ставят в соответствие уравнения, для которых строят прямые; после чего определяют полуплоскости, удовлетворяющие исходным неравенствам системы ограничений.

2. Выделить штриховкой область допустимых решений (полученное выпуклое множество).

Построить линию уровня целевой функции .

3. Построить градиент

, где .

Градиент перпендикулярен линии уровня.

4. Линию уровня перемещаем до крайней точки допустимой области по направлению градиента (при задании целевой функции на максимум) или антиградиента (при ).

Определить оптимальный план как точку пересечения линии уровня с крайней точкой допустимой области. Найти координаты этой вершины, решив систему линейных уравнений тех прямых, которые пересекаются в этой точке. Если переменных было более двух, найти остальные значения .

Вычислить значение F.

Замечание: если в исходной задаче более двух переменных, то элементарными преобразованиями сводят задачу к двум переменным.

Симплексные преобразования при изменении базисных переменных

Условием для решения ЗЛП симплекс-методом является наличие модели задачи, записанной в каноническом виде стандартной формы.

Для удобства решения задачи составляют таблицу

В зависимости от знаков (значений свободных членов, стоящих в правых частях системы ограничений) и (коэффициентов целевой функции ) возможны различные методы решения ЗЛП: основной, двойственный и смешанный.

Алгоритм основного симплекс-метода (все , но существуют )

Записать в нулевую начальную таблицу исходную каноническую стандартную форму, взяв в качестве базисных переменных те, которые создают канонический вид.

Среди отрицательных коэффициентов целевой функции () (при неискусственных переменных) находится максимальный по модулю. Соответствующий столбец над этим числом называется разрешающим столбцом (обозначается *).

Вычислить отношения правых частей ограничений () к положительным элементам разрешающего столбца по горизонтали и выбрать минимальное отношение . Соответствующая строка называется разрешающей строкой (обозначается *).

Элемент, стоящий на пересечении разрешающих строки и столбца, называется разрешающим элементом (выделяется ?).

Переходим к новой таблице. Заменяется базисная переменная, стоящая в разрешающей строке, на переменную, стоящую в разрешающем столбце (т.е. получается новый базисный набор).

Заполняются базисные столбцы (на пересечении базисной переменной в строке и столбце стоит 1, а остальные элементы в столбце равны 0).

Если существуют нулевые элементы в разрешающем столбце прежней таблицы, то все строки с этими нулями переписываются без изменения в новую таблицу.

Если существуют нулевые элементы в разрешающей строке прежней таблицы, то соответствующие столбцы с этими нулями переписываются в новую таблицу.

Составляется опорная строка в новой таблице делением бывшей разрешающей строки на разрешающий элемент.

Все остальные элементы находят по правилу треугольника: новый элемент равен бывшему значению минус произведение соответствующего по строке элемента в разрешающем столбце прежней таблицы на элемент в опорной строке столбца искомого элемента новой таблицы. Исключение - коэффициент в целевой функции , где вместо «-» в правиле треугольника необходимо использовать «+».

Если выполняется критерий оптимальности: коэффициенты , коэффициенты (при неискусственных переменных) целевой функции , то получен оптимальный план. Иначе - переход к пункту 2 данного алгоритма.

Алгоритм двойственного симплекс-метода (если все, но существуют )

1. Записать в нулевую таблицу исходную каноническую стандартную форму.

2. Среди отрицательных свободных членов выбрать максимальный по модулю. Соответствующая строка - разрешающая.

3. Среди всех отношений коэффициентов целевой функции к отрицательным элементам разрешающей строки выбрать минимальное по модулю. Соответствующий столбец - разрешающий.

4. Далее решение аналогично основному симплекс-методу, начиная с пункта 4.

Алгоритм смешанного симплекс-метода (существуют и )

Начать решение основным симплекс-методом, при этом уравнения с отрицательной правой частью не рассматриваются при определении разрешающей строки (т.е. соответствующие им базисные переменные нельзя выводить из базиса на этом этапе).

После того, как коэффициенты целевой функции станут , а среди правых частей уравнений ограничений существуют , продолжить решение двойственным симплекс-методом.

Решение ЗЛП методом искусственного базиса

Если в системе ограничений существуют неравенства (со знаками или >) или уравнения (без переменных, создающих канонический вид), то для создания канонического вида стандартной формы удобно использовать метод искусственного базиса.

При решении ЗЛП методом искусственного базиса неравенства ограничений сначала приводят к системе уравнений. После этого в уравнения без переменных, создающих канонический вид, вводят искусственные переменные. Так как в уравнения вводятся неотрицательные переменные, то для соответствия новой задачи исходной, необходимо, чтобы искусственные переменные были равны нулю. Для этого составляется целевая функция , равная сумме всех введенных искусственных переменных. Функцию G необходимо выразить через неискусственные переменные и ввести в симплекс-таблицу. При определении разрешающего столбца в симплекс-таблице выбирают максимальный по модулю отрицательный коэффициент функции (при неискусственных переменных). Когда коэффициенты целевой функции при неискусственных переменных равны нулю, а при искусственных переменных коэффициенты равны 1 (т.е. сумма всех искусственных переменных равна нулю), тогда вычеркивается строка со вспомогательной функцией и переходят к строке целевой функции для определения разрешающего столбца и продолжают решение. Если в процессе решения получается, что все коэффициенты в строке (при неискусственных переменных) положительные, то задача неразрешима (допустимая область значений пуста).