Симплекс метод - пример решения.
Ниже приведено условие и решение задачи. Закачка решения в формате doc начнется автоматически через 10 секунд.
Z = -X1 + 8X2 max(min)
X1 – 2X2 ≤ -2,
-2X1 + 3X2 ≤ 6
2X1 + 4X2 ≤ 0,
X2≥0
Решение
Вместо переменной Х1 произвольного знака вводим переменные Х1’ и X1’’.
X1 = Х1’ - X1’’.
Запишем систему неравенств в виде:
(Х1’ - X1’’) - 2Х2 ≤ -2
-2(Х1’ - X1’’) + 3Х2 ≤ 6
2(Х1’ - X1’’) + 4Х2 ≤ 0
Получим:
Х1’ - X1’’- 2Х2 ≤ -2
-2Х1’ + 2X1’’+ 3Х2 ≤ 6 (1)
2Х1’ - 2X1’’ +4Х2 ≤ 0
Условие положительности:
Х1’≥0, X1’’≥0, X2≥0. (2)
Целевая функция:
F = -(Х1’ - X1’’) + 8X2 = -Х1’ + X1’’ + 8X2 (max) (3)
Задача записана в симметричной фоме записи. Приведем задачу к канонической форме записи, для этого введем дополнительные переменные Х3, Х4, Х5. Расширенная система задачи имеет вид:
Х1’ - X1’’- 2Х2 +Х3 = -2
-2Х1’ + 2X1’’+ 3Х2 +Х4 = 6
2Х1’ - 2X1’’ + 4Х2 +Х5 = 0
Условия неотрицательности примут вид:
Xj≥0 (j=1,..,5).
Заполним первую симплексную таблицу (Табл. 1), в которой переменные X3, X4, X5 являются базисными, переменные Х1’, X1’’, X2 свободными. Последняя строка заполняется коэффициентами целевой функции с противоположным знаком.
Таблица 1. Первая (начальная) симплексная таблица
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
X1'' |
X2 |
X3 |
X4 |
X5 |
||||
-1 |
1 |
8 |
0 |
0 |
0 |
||||
X3= |
0 |
-2 |
1 |
-1 |
-2 |
1 |
0 |
0 |
1 |
X4= |
0 |
6 |
-2 |
2 |
3 |
0 |
1 |
0 |
2 |
X5= |
0 |
0 |
2 |
-2 |
4 |
0 |
0 |
1 |
0 |
F |
0 |
1 |
-1 |
-8 |
0 |
0 |
0 |
|
В результате симплексного преобразования, получим вторую симплексную таблицу (Табл.2).
Таблица 2. Вторая симплексная таблица
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
X1'' |
X5 |
X3 |
X4 |
X5 |
||||
-1 |
1 |
8 |
0 |
0 |
0 |
||||
X3= |
0 |
-2 |
2 |
-2 |
0 |
1 |
0 |
0,5 |
1 |
X4= |
0 |
6 |
-3,5 |
3,5 |
0 |
0 |
1 |
-0,75 |
1,7142857 |
X2= |
8 |
0 |
0,5 |
-0,5 |
1 |
0 |
0 |
0,25 |
0 |
F |
0 |
5 |
-5 |
0 |
0 |
0 |
2 |
|
Таблица 3. Третья симплексная таблица
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
X1'' |
X5 |
X3 |
X4 |
X5 |
||||
-1 |
1 |
8 |
0 |
0 |
0 |
||||
X1''= |
1 |
1 |
-1 |
1 |
0 |
-0,5 |
0 |
-0,25 |
-2 |
X4= |
0 |
2,5 |
0 |
0 |
0 |
1,75 |
1 |
0,125 |
1,4285714 |
X2= |
8 |
0,5 |
0 |
0 |
1 |
-0,25 |
0 |
0,125 |
-2 |
F |
5 |
0 |
0 |
0 |
-2,5 |
0 |
0,75 |
|
Таблица 4. Четвертая симплексная таблица
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
X1'' |
X5 |
X3 |
X4 |
X5 |
||||
-1 |
1 |
8 |
0 |
0 |
0 |
||||
X1''= |
1 |
1,714286 |
-1 |
1 |
0 |
0 |
0,28571 |
-0,2143 |
|
X3= |
0 |
1,428571 |
0 |
0 |
0 |
1 |
0,57143 |
0,07143 |
|
X2= |
8 |
0,857143 |
0 |
0 |
1 |
0 |
0,14286 |
0,14286 |
|
F |
8,571429 |
0 |
0 |
0 |
0 |
1,42857 |
0,92857 |
|
В последней строке все элементы неотрицательные, критерий оптимальности выполнен, значит опорный план (0; 1,714; 0,857; 1,423; 0; 0) является оптимальным, а соответствующее ему значение 8,571 целевой функции будет максимальным. Х1 = - 1,714.
Мы получили такое же решение, что и графическим методом.
Найдем минимальное значение целевой функции. Для этого целевую функцию запишем в виде:
-F = Х1’ - X1’’ - 8X2 (max)
Первая симплексная таблица запишется в виде табл. 5. В таблице 5 в столбце свободных членов есть отрицательный элемент, следовательно, план не является опорным.
Таблица 5.
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
X1'' |
X2 |
X3 |
X4 |
X5 |
||||
1 |
-1 |
-8 |
0 |
0 |
0 |
||||
X3= |
0 |
-2 |
1 |
-1 |
-2 |
1 |
0 |
0 |
-2 |
X4= |
0 |
6 |
-2 |
2 |
3 |
0 |
1 |
0 |
-3 |
X5= |
0 |
0 |
2 |
-2 |
4 |
0 |
0 |
1 |
0 |
-F |
0 |
-1 |
1 |
8 |
0 |
0 |
0 |
|
Переходим ко второй симплексной таблице.
Таблица 6.
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
X1'' |
X2 |
X3 |
X4 |
X5 |
||||
1 |
-1 |
-8 |
0 |
0 |
0 |
||||
X3= |
0 |
-2 |
0 |
0 |
-4 |
1 |
0 |
-0,5 |
|
X4= |
0 |
6 |
0 |
0 |
7 |
0 |
1 |
1 |
|
X1'= |
1 |
0 |
1 |
-1 |
2 |
0 |
0 |
0,5 |
|
-F |
0 |
0 |
0 |
10 |
0 |
0 |
0,5 |
|
Таблица 7.
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
X1'' |
X2 |
X3 |
X4 |
X5 |
||||
1 |
-1 |
-8 |
0 |
0 |
0 |
||||
X2= |
-8 |
0,5 |
0 |
0 |
1 |
-0,25 |
0 |
0,125 |
|
X4= |
0 |
2,5 |
0 |
0 |
0 |
1,75 |
1 |
0,125 |
|
X1'= |
1 |
-1 |
1 |
-1 |
0 |
0,5 |
0 |
0,25 |
|
-F |
-5 |
0 |
0 |
0 |
2,5 |
0 |
-0,75 |
|
Таблица 8.
Базис |
C |
Свободный член |
Переменные |
Оценочное отношение |
|||||
X1' |
Имя файла: mathprog13.doc
Размер файла: 163.5 Kb
Если закачивание файла не начнется через 10 сек, кликните по этой ссылке