Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Линейное программирование Часть 1 Метод указани...doc
Скачиваний:
8
Добавлен:
01.05.2025
Размер:
2 Мб
Скачать
☆

4.2.Алгоритм симплекс-метода

Приведем пошаговое описание симплекс-метода.

  1. Построить начальную симплексную таблицу: .

  2. Если все j0, то перейти на шаг 5. Если существует j=s такое, что s<0, то выбираем s-й столбец разрешающим.

  3. Выбираем разрешающую строку r по правилу: . Если , то делаем вывод, что f(x) не ограничена сверху в области допустимых решений задачи (Нр2) и переходим на шаг 6.

  4. Провести жордановы преобразования симплекс-таблицы с разрешающим элементом zrs и перейти на шаг 2.

  5. Симплекс-таблица оптимальна, т.е. определяет оптимальное решение задачи и максимальное значение целевой функции.

  6. Решение задачи завершено.

4.3.Построение начальной симплексной таблицы

Остановимся на построении начальной симплексной таблицы для некоторых форм задач линейного программирования.

1.Пусть задача ЛП дана в стандартной форме

(14)

От формы (14) легко перейти к канонической, добавив в каждое из ограничений слабую переменную.

Получим

(15)

где E-диагональная матрица порядка m.

Вектор будет опорным решением задачи (15)с базисом B=E.

Итак, получаем начальную симплексную таблицу, в которой :

x

U

A

=

b

f

-c

=

0

2.Задача ЛП задана в канонической форме

Не нарушая общности, можно считать . Пусть матрица A содержит m единичных ортов. Можно считать, что Симплексная таблица при этом имеет следующий вид:

сm+1

…

cn

cB

xm+1

…

xn

c1

x1

a1,m+1

…

am,n

=

b1

…

…

…

…

…

…

…

cm

xm

am,m+1

…

am,n

=

bm

f

m+1

…

m+1

=

где

(16)

3. Задача ЛП задана в канонической форме

и (17)

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

и (18)

Очевидно, что вектор является опорным решением задачи (18).

Справедливы утверждения:

Утверждение 4. Задача (18) всегда разрешима и .

Утверждение 5. Если , то система ограничений задачи (17) противоречива.

Утверждение 6. Если , и вектор -оптимальный опорный план задачи (18), то вектор является опорным планом задачи (17).

При этом из оптимальной симплекс-таблицы (С-Т) задачи (18) можно построить начальную симплекс-таблицу задачи (17). Рассмотрим возможные ситуации.

Ранг матрицы A равен m, задача (17) невырожденная. Тогда в оптимальной С-Т задачи (18) все искусственные переменные будут небазисными и для получения начальной С-Т нужно вычеркнуть все столбцы, отвечающие искусственным переменным, и пересчитать оценки, используя функцию f(x) и формулу (12).

Ранг матрицы A меньше m, задача (17) невырожденная. Тогда в оптимальной С-Т задачи (18) среди базисных переменных могут оказаться искусственные переменные. В соответствующих строках все элементы будут равны 0. Вычеркнув все 0-строки, получим первый случай.

Ранг матрицы A равен m, задача (17) вырожденная. Тогда в оптимальной С-Т задачи (18) среди базисных переменных могут оказаться искусственные переменные. В соответствующих строках элементы столбца равны 0, но среди остальных элементов этих строк будут элементы, отличные от 0. Выбрав любой из них в качестве разрешающего и выполнив жорданово преобразование С-Т, выведем искусственную переменную из базиса. Эти действия повторяем до тех пор, пока все искусственные переменные ни будут выведены из базиса. При этом получим первый случай.