Идея и алгебра симплекс-метода

Симплекс-метод является общим методом решения задач линейного программирования. Запишем задачу линейного программирования в стандартной форме в развернутом виде:

Система ограничений представляет собой систему линейных алгебраических уравнений относительно неизвестных х" i = 1, /?. Особенностью задач линейного программирования является то, что число уравнений системы меньше числа неизвестных (т < и). То есть СЛАУ представляет собой недоопределенную систему и множество допустимых решений бесконечно. Отсюда следует, что выбор оптимального допустимого решения нетривиален.

Классическим методом решения недоопределенных СЛАУ является метод Гаусса-Жордана. Основная идея его состоит в сведении т уравнения с п неизвестными к каноническому или ступенчатому виду путем линейных преобразований над строками (сложение строк и умножение на скаляр). Это позволяет привести СЛАУ к следующему виду:

Переменные х, х₂, …, х_т называются базисными (зависимыми), которые входят в одно уравнение с коэффициентом 1, а в остальные — с коэффициентом 0.

х_ш+1, …, х" называют свободными (независимыми).

В канонических системах в любом уравнении присутствует только одна базисная переменная.

Выразим из системы (4.7) базисные переменные:

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

Определение. Базисным решением системы канонического вида называют решение, полученное при нулевых значениях независимых переменных. То есть.

Определение. Если Ь_: >0, / = 1, т, то полученное базисное решение называется допустимым базисным решением или опорным планом.

Отметим, что базисными переменными не обязательно являются первые т переменных. Ими могут быть любые т штук переменных системы.

Ниже приведены примеры использования основных модификаций метода Гаусса. Самыми популярными из них являются: метод последовательного исключения Гаусса со схемой единственного деления и с выбором главных элементов.