Лабораторная работа № 2
Дана ЗЛП:
,
.
В табл. 1.5. приведены варианты значений параметров a, b, c.
Таблица 1.5
|
a |
b |
c |
|
a |
b |
c |
|
a |
b |
c |
|
a |
b |
c |
1 |
2 |
3 |
-1 |
6 |
5 |
2 |
3 |
11 |
2 |
1 |
2 |
16 |
3 |
3 |
1 |
2 |
3 |
1 |
1 |
7 |
4 |
3 |
6 |
12 |
3 |
3 |
4 |
17 |
4 |
1 |
2 |
3 |
4 |
2 |
-1 |
8 |
6 |
1 |
5 |
13 |
5 |
2 |
-1 |
18 |
3 |
1 |
0 |
4 |
7 |
2 |
3 |
9 |
2 |
2 |
2 |
14 |
7 |
1 |
5 |
19 |
4 |
1 |
3 |
5 |
8 |
3 |
4 |
10 |
5 |
3 |
7 |
15 |
6 |
3 |
8 |
20 |
5 |
2 |
6 |
Необходимо выполнить следующие задания:
Привести ЗЛП к канонической форме.
С помощью алгоритма перестроения базисного решения ЗЛП найти четыре различных базисных решения и выбрать среди них наилучшее.
2. Симплекс-метод
Как было показано выше, с помощью перебора базисных решений можно получить оптимальное решение, если задача разрешима.
Заметим, что число базисных решений хотя и конечно, однако может быть весьма большим, при больших размерах задачи. Поэтому если имеется некоторая базисная точка, то хотелось бы знать:
Не является ли она оптимальной и если это так, то просмотр остальных точек не целесообразен;
Не является ли задача неразрешимой из-за неограниченности целевой функции. В этом случае просмотр остальных точек также не целесообразен;
Если точка неоптимальная, то нельзя ли определить вектор-столбец, подлежащий введению в базис, такой, что значение целевой функции будет обязательно больше предыдущего.
2.1. Основная теорема линейного программирования
Будем называть
(2.1.1)
оценкой
вектора
.
Теорема:
Пусть имеется базисное решение ЗЛП
со значением целевой функции
и для всех j
найдены оценки
.
Тогда:
Если имеется
для
любых j,
то базисное решение оптимально;Если существует
,
то существует бесчисленное множество
допустимых решений
,
для которых
.
При этом
2а. Если столбец , то задача неразрешима из-за неограниченности целевой функции;
2б.
Если имеется
,
то существует новое базисное решение,
значение целевой функции на котором
больше, чем на исходном , то есть
.
Замечание:
Теорема справедлива, если базисное
решение не вырождено, то есть
.
На основе этой теоремы строится метод решения ЗЛП, называемый симплекс-методом, который фактически является методом перестроения базисного решения с учетом оценок небазисных столбцов.