Поскольку min f(x) эквивалентен max [- f(x)], то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный (прямой, простой) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

Графический метод

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции задачи.

Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

Табличный симплекс – метод

Для его применения необходимо, чтобы знаки в ограничениях были вида “меньше либо равно”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

Если в исходной системе ограничений присутствовали знаки “ равно ”

или “ больше либо равно ”, то в указанные ограничения добавляются

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

2. Формируется симплекс-таблица.

3. Рассчитываются симплекс – разности.

4. Принимается решение об окончании либо продолжении счёта.

5. При необходимости выполняются итерации.

На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

Метод искусственного базиса

Данный метод решения применяется при наличии в ограничении знаков

“равно”, “больше либо равно”, “меньше либо равно” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m, а в задачи минимизации - с положительными m. Таким образом, из исходной получается новая m - задача.

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

Модифицированный симплекс – метод

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

В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта, хороша для ситуаций, когда число переменных n значительно превышает число ограничений m.

В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс – разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.

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

Двойственный симплекс – метод

Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов, составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными).

Общий вид задачи линейного программирования