Система m линейных уравнений с n неизвестными

Система m линейных уравнений с n переменными имеет вид

В задачах линейного программирования представляют интерес системы, в которых ранг матрицы

Любые m переменных системы m линейных уравнений с n переменными (m

Базисным решением системы m линейных уравнений с n переменными называется решение,

Основными могут быть разные группы из n переменных. Максимальное число групп

Пример. Найти все возможные группы основных переменных в системе

Решение системы называется допустимым, если оно содержит только неотрицательные компоненты, в

Базисным решением системы m линейных уравнений с n переменными называется решение,

Пример. Найти все базисные решения системы

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

Решение любой задачи линейного программирования можно найти симплексным методом.
Симплексный метод

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

Для реализации симплексного метода необходимо освоить три основных элемента:
Способ определения какого-либо

Пусть требуется найти максимальное (минимальное) значение функции

при условиях

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

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

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

Критерий оптимальности решения при отыскании максимума(минимума) линейной функции:
Если в выражении линейной

Если система ограничений непротиворечива, то выполнение конечного числа последовательных шагов симплексного

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

Алгоритм:
1. Систему линейных неравенств записываем в каноническом виде. Для этого в

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

2. Исходную расширенную систему заносим в первую симплексную таблицу.

3. Проверяем выполнение критерия оптимальности при решении задач на максимум-

4 Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный

Составляем оценочные отношения каждой строки по правилам:
∞, если bi и ais

Определяем

Если конечного минимума нет, то задача не имеет конечного оптимума (Fmax=∞)
Если

5. Переходим к следующей таблице по правилам:
в левом столбце записываем новый

новую строку с номером q получаем из старой строки делением на

Пример. Решим задачу об использовании ресурсов

1. Шаг

Заполняем первую симплексную таблицу, в которой переменные х3,х4,х5,х6 - основные