Методы и модели в экономике. Оптимальное распределение ресурсов. Транспортная задача: Методические указания к выполнению контрольных заданий, страница 9

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

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

Правила преобразования симплексной таблицы.

1. Выбирают разрешающий столбец из условия  и хотя бы один элемент .

2. Выбирают q-ю разрешающую строку из условия

Элемент , стоящий на пересечении разрешающего ( с индексом p) столбца и разрешающей ( с индексом q) строки, называется разрешающим элементом.

3. В состав базисных переменных вводят , её записывают в строку с номером q.

4. Производят пересчет элементов разрешающей q-й строки по формуле

В результате преобразования получают единицу на месте разрешающего элемента.

5. Вычисляют элементы всех остальных строк  (при k¹p) по формуле:

Строке с номером r+1 соответствует строка целевой функции, столбцу с номером n+1 соответствует столбец свободных членов.

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

6. Далее анализируем полученную таблицу. Если решение получено или выяснено, что его нет, процесс решения закончен. Иначе переходим к пункту 1.

Анализ базируется на основной теореме симплекс-метода.

ТЕОРЕМА

Если после выполнения очередной итерации (преобразования):

1)  найдется хотя бы один отрицательный коэффициент  и в каждом столбце с таким коэффициентом окажется хотя бы один положительный элемент, то можно улучшить решение, выполнив следующую итерацию;

2)  найдется хотя бы один отрицательный коэффициент  и в соответствующем столбце не содержится положительных элементов, то функция F не ограничена в области допустимых решений;

3)  все коэффициенты окажутся неотрицательными, то оптимальное решение достигнуто.

Рассмотрим решение той же задачи (1.21)-(1.23) с помощью симплекс таблиц.

Исходная симплекс таблица, определяемая соотношениями (1.21)-(1.23) показана на рис.(1.5).