ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 20.12.2024
Просмотров: 625
Скачиваний: 1
Приложение.
Типовой отчет по лабораторной работе "Решение задач линейного программирования"
Задание.
Решить задачу линейного программирования:
max z = -x1 + 2x2 + x3
2x1 + 3x2 - 5x3 3
-x1 + 9x2 - x3 5
4x1 + 6x2 + 3x3 15
xi 0
Для приведения задачи к стандартной форме вводим дополнительные переменные:
max z = -x1 + 2x2 + x3
2x1 + 3x2 - 5x3 - x4 = 3
-x1 + 9x2 - x3 - x5 = 5
4x1 + 6x2 + 3x3 + x6 = 15
xi 0
Матрица системы ограничений не содержит выделенной единичной матрицы:
.
Вводим искусственные вектор-столбцы в матрицу А:
.
Исходная модель приобретает следующий вид:
max z = -x1 + 2x2 + x3 - Mx6 - Mx7
2x1 + 3x2 - 5x3 - x4 + x6 = 3
-x1 + 9x2 - x3 - x5 + x7 = 5
4x1 + 6x2 + 3x3 + x8 = 15
xi 0
Результаты решение ЗЛП с помощью программы представлены в следующих таблицах:
Исходные данные
|
1 |
Число переменных |
8 |
|
2 |
Число ограничений |
3 |
|
3 |
Признак оптимизации |
1 |
|
4 |
Число этапов моделирования |
1 |
Коэффициенты целевой функции
|
|
х1 |
х2 |
х3 |
х43 |
х5 |
х6 |
х7 |
х8 |
|
c |
-1 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
Фиктивные слагаемые коэффициентов целевой функции
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
|
cm |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
0 |
Номера базисных переменных
|
|
огр.1 |
огр.2 |
огр.3 |
|
x |
6 |
7 |
8 |
Матрица коэффициентов
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
правые части |
|
огр. 1 |
2 |
3 |
-5 |
-1 |
0 |
1 |
0 |
0 |
3 |
|
огр. 2 |
-1 |
9 |
-1 |
0 |
-1 |
0 |
1 |
0 |
5 |
|
огр. 3 |
4 |
6 |
3 |
0 |
0 |
0 |
0 |
1 |
15 |
Результирующая симплекс-таблица
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
правые части |
|
z |
2.333 |
0 |
0 |
0 |
0 |
0 |
0 |
0.333 |
5.000 |
|
zm |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0.000 |
|
x5 |
7 |
0 |
0 |
-0.846 |
1 |
0.846 |
-1 |
1.077 |
13.692 |
|
x2 |
0.667 |
1 |
0 |
-0.077 |
0 |
0.077 |
0 |
0.128 |
2.154 |
|
x3 |
0 |
0 |
1 |
0.154 |
0 |
-0.154 |
0 |
0.077 |
0.692 |
Условие оптимальности выполняется
Оптимальные значения исходных переменных задачи и оптимальное значение целевой функции равны:
x1 = 0, x2 = 2.154, x3 = 0.692, z = 5.0.
Решение ЗЛП с помощью соотношений двойственности приведено ниже:
Итерация 1.
|
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
||||
|
1 |
Решение ЗЛП симплекс-методом |
|
|
|
|
|
|||||||||||
|
2 |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
|
|
|
|
|
||||
|
3 |
Вектор с |
|
|
|
|
|
|||||||||||
|
4 |
-1 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
||||
|
5 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
0 |
|
|
|
|
|
||||
|
6 |
Матрица А |
|
Вектор b |
|
|
||||||||||||
|
7 |
2 |
3 |
-5 |
-1 |
0 |
1 |
0 |
0 |
|
3 |
|
|
|
||||
|
8 |
-1 |
9 |
-1 |
0 |
-1 |
0 |
1 |
0 |
|
5 |
|
|
|
||||
|
9 |
4 |
6 |
3 |
0 |
0 |
0 |
0 |
1 |
|
15 |
|
|
|
||||
|
10 |
Матрица базиса В |
|
Обратная матрица В-1 |
|
|
|
|
|
|||||||||
|
11 |
1 |
0 |
0 |
|
1 |
0 |
0 |
|
|
|
|
|
|
||||
|
12 |
0 |
1 |
0 |
|
0 |
1 |
0 |
|
|
|
|
|
|
||||
|
13 |
0 |
0 |
1 |
|
0 |
0 |
1 |
|
|
|
|
|
|
||||
|
14 |
Коэффициенты базисных переменных cb |
|
|
|
|
|
|
|
|||||||||
|
15 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
||||
|
16 |
-1 |
-1 |
0 |
|
|
|
|
|
|
|
|
|
|
||||
|
17 |
Двойственные переменные Y=cb*B-1 |
|
|
|
|
|
|
|
|||||||||
|
18 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
||||
|
19 |
-1 |
-1 |
0 |
|
|
|
|
|
|
|
|
|
|
||||
|
20 |
Вспомогательный массив F=Y*A |
|
|
|
|
|
|||||||||||
|
21 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|||||
|
22 |
-1 |
-12 |
6 |
1 |
1 |
-1 |
-1 |
0 |
|
|
|
|
|
||||
|
23 |
Симплекс-таблица |
|
|
|
|
|
|||||||||||
|
24 |
Оценки плана k=F-c |
|
|
|
|
|
|||||||||||
|
25 |
Матрица системы ограничений S=B-1*A |
|
|
|
|
|
|||||||||||
|
26 |
Значения базисных переменных xb=B-1*b |
|
|
|
|
|
|||||||||||
|
27 |
Значение целевой функции z=cb*xb |
|
|
|
|
|
|||||||||||
|
28 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
|
Решение |
|
Симплекс |
||||
|
29 |
k |
1 |
-2 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
|
*** |
||||
|
30 |
km |
-1 |
-12 |
6 |
1 |
1 |
0 |
0 |
0 |
|
-8 |
|
*** |
||||
|
31 |
х6 |
2 |
3 |
-5 |
-1 |
0 |
1 |
0 |
0 |
|
3 |
|
1 |
||||
|
32 |
х7 |
-1 |
9 |
-1 |
0 |
-1 |
0 |
1 |
0 |
|
5 |
|
0.556 |
||||
|
33 |
х8 |
4 |
6 |
3 |
0 |
0 |
0 |
0 |
1 |
|
15 |
|
2.5 |
||||
|
34 |
Включаемая переменная |
2 |
|
|
|
|
|
|
|
|
|||||||
|
35 |
Исключаемая переменная |
7 |
|
|
|
|
|
|
|
|
|||||||