- •Часть I
- •1.Основные понятия
- •1.1. Постановка и формы записи задачи лп
- •1.2. Правила преобразования задач
- •1.3. Задания
- •2. Геометрический метод решения простейших
- •2.1. Допустимое множество
- •2.2 Целевая функция
- •3. Базисные решения системы линейных
- •3.2. Жордановы таблицы
- •2.3. Задания
- •3.3. Задания
- •4. Симплекс-метод
- •4.1.Симплекс-таблица
- •4.2.Алгоритм симплекс-метода
- •4.3.Построение начальной симплексной таблицы
- •4.4.Примеры использования симплекс-метода
4.2.Алгоритм симплекс-метода
Приведем пошаговое описание симплекс-метода.
Построить начальную симплексную таблицу:
.Если все j0, то перейти на шаг 5. Если существует j=s такое, что s<0, то выбираем s-й столбец разрешающим.
Выбираем разрешающую строку r по правилу: . Если
,
то делаем вывод, что f(x)
не
ограничена сверху в области допустимых
решений задачи (Нр2) и переходим на шаг
6.Провести жордановы преобразования симплекс-таблицы с разрешающим элементом zrs и перейти на шаг 2.
Симплекс-таблица оптимальна, т.е. определяет оптимальное решение задачи и максимальное значение целевой функции.
Решение задачи завершено.
4.3.Построение начальной симплексной таблицы
Остановимся на построении начальной симплексной таблицы для некоторых форм задач линейного программирования.
(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.
Выбрав любой из них в качестве
разрешающего
и выполнив жорданово преобразование
С-Т, выведем искусственную переменную
из базиса. Эти действия повторяем до
тех пор, пока все искусственные переменные
ни будут выведены из базиса. При этом
получим первый случай.
