Здравствуйте, Елизавета!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение задачи указанным методом находится в файле.