a₁₁ x₁ + a₁₂ x₂ +…+ a_{1 n} x_n - 1x_{n +1} + 0x_{n +2} +…+0x_{n + m} = b₁ ;

a₂₁ x₁ + a₂₂ x₂ +…+ a_2n x_n +0x_n+1 -1x_n+2 +…+0x_n+m = b₂ ; (2.3.1)

. . . . . . . . . . . . . . . . . . . . . .

a_m1 x₁ + a_m2 x₂ +...+ a_mn x_n + 0x_n+1 + 0x_n+2 +...-1x_n+m = b_m .

Свободные переменные {x_{n +1} ,…,x_{n + m} }в этом случае уже невозможно использовать в качестве начального базиса, так как x_{n +1} <0,...,x_{n + m} <0. Поэтому в уравнения (2.3.1) дополнительно вводят искусственные переменные x_{n + m +1} ,…,x_{n + m + k} . Эти переменные не имеют ничего общего с реальной задачей, и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M>>c_i , (i = 1, 2, ..,m).

В случае решения задач минимизации искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

Знаки искусственных переменных x_{n + m +1} ,...,x_{n + m + k} должны совпадать со знаками соответствующих свободных членов. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

4. Проверка достоверности полученных результатов

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

· Значения элементов строки, содержащей ∆_j , вычисляются как элементы симплекс-таблицы (за исключением первой симплекс-таблицы, где такие вычисления невозможны).

· Значения элементов строки, содержащей ∆_j , вычисляются вторым способом, а именно по формулам непосредственного счета:

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

Дополнительным средством проверки достоверности является использование «Инженерного режима», реализованного в программе. В данном режиме можно посмотреть каждый этап вычисления задачи.

В программе также реализованы следующие методы обработки ошибок вычислений:

1. В случае если происходит «зацикливание» программы (в данной программе, если количество итераций больше 100), пользователю выдается сообщение об ошибке. Данная ситуация может возникнуть в случае вырожденности матрицы – вектор, который был ранее выведен из базиса, снова вводится в базис.

2. В случае если из базиса не удается вывести искусственные переменные, пользователю выдается сообщение об ошибке. Это означает, что ограничения задачи противоречивы и задача не имеет решения.

5. Алгоритм решения задачи

1. Проверка правильности ввода данных.

2. Построение симплекс-таблицы по введённым данным.

3. Добавление искусственных переменных.

4. Выбор направляющего элемента.

5. Деление направляющей строки на направляющий элемент.

6. Подсчет остальных элементов новой симплекс таблицы.

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

8. Если цикл расчета симплекс-таблиц не прекращается, принудительно прекращается процесс, пользователю выдается информация об ошибке.

9. Если из базисного решения не выведены все искусственные переменные, пользователю выдается информация об ошибке.

10. Если решение получено, результаты выводятся на экран.

6. Листинг программы, реализующий алгоритм задачи

const

m=25;