МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Практическая работа №7
«Целочисленное линейное программирование (ЗЦЛП)»
по дисциплине
«Теория принятия решений»
|
|
Студент |
|
|
|
Филатов А.А. |
|
||||||||
|
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
|
Группа |
|
АС-09 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
Принял |
|
|
|
|
|
||||||||
|
|
|
|
|
|
Корнеев А.М. |
|
||||||||
|
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
Липецк 2012
1. Задание
Найти оптимальное целочисленное решение.
1. Исходными данными взять результаты, посчитанные симплекс-методом.
2. Найти решение ЗЦЛП:
2.1 методом Гомори;
2.2 методом ветвей и границ.
2. Решение
Целевая функция
имеет вид:
.
Полученный оптимальный базисный план из практической работы №4 имеет вид:
|
Базис |
B |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
2 |
5 2/5 |
0 |
1 |
0 |
0 |
1/5 |
0 |
3/5 |
|
1 |
4 2/5 |
1 |
0 |
0 |
0 |
1/5 |
0 |
- 2/5 |
|
3 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
|
6 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
4 |
3/5 |
0 |
0 |
0 |
1 |
- 1/5 |
0 |
- 3/5 |
|
f(x) |
59 4/5 |
0 |
0 |
0 |
0 |
2 2/5 |
0 |
2 1/5 |
1) Найдем оптимальное целочисленное решение данной задачи методом Гомори:
Итерация 1
|
Определяем значения α и β : |
|
|
|
|
|||
|
b |
a |
|
|
|
|
|
|
|
3/5 |
0 |
0 |
0 |
0 |
4/5 |
0 |
2/5 |
Вводим новую строку в симплекс-таблицу:
|
Базис |
B |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
2 |
5 2/5 |
0 |
1 |
0 |
0 |
1/5 |
0 |
3/5 |
0 |
|
1 |
4 2/5 |
1 |
0 |
0 |
0 |
1/5 |
0 |
- 2/5 |
0 |
|
3 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
|
6 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
4 |
3/5 |
0 |
0 |
0 |
1 |
- 1/5 |
0 |
- 3/5 |
0 |
|
8 |
- 3/5 |
0 |
0 |
0 |
0 |
- 4/5 |
0 |
- 2/5 |
1 |
|
f(x) |
59 4/5 |
0 |
0 |
0 |
0 |
2 2/5 |
0 |
2 1/5 |
0 |
|
Базис |
B |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
2 |
5 1/4 |
0 |
1 |
0 |
0 |
0 |
0 |
1/2 |
1/4 |
|
1 |
4 1/4 |
1 |
0 |
0 |
0 |
0 |
0 |
- 1/2 |
1/4 |
|
3 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
|
6 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
4 |
3/4 |
0 |
0 |
0 |
1 |
0 |
0 |
- 1/2 |
- 1/4 |
|
5 |
3/4 |
0 |
0 |
0 |
0 |
1 |
0 |
1/2 |
-1 1/4 |
|
f(x) |
58 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
3 |
|
Итерация 2 |
|
|
|
|
|
|
|
|
|
Определяем значения α и β : |
|
|
|
|
|
|||
|
b |
a |
|
|
|
|
|
|
|
|
3/4 |
0 |
0 |
0 |
0 |
0 |
0 |
1/2 |
3/4 |
Вводим новую строку в симплекс-таблицу:
|
Базис |
B |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
2 |
5 1/4 |
0 |
1 |
0 |
0 |
0 |
0 |
1/2 |
1/4 |
0 |
|
1 |
4 1/4 |
1 |
0 |
0 |
0 |
0 |
0 |
- 1/2 |
1/4 |
0 |
|
3 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
6 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
4 |
3/4 |
0 |
0 |
0 |
1 |
0 |
0 |
- 1/2 |
- 1/4 |
0 |
|
5 |
3/4 |
0 |
0 |
0 |
0 |
1 |
0 |
1/2 |
-1 1/4 |
0 |
|
9 |
- 3/4 |
0 |
0 |
0 |
0 |
0 |
0 |
- 1/2 |
- 3/4 |
1 |
|
f(x) |
58 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
3 |
0 |
|
Базис |
B |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
2 |
4 1/2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
- 1/2 |
1 |
|
1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
|
3 |
4 1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 1/2 |
-2 |
|
6 |
2 1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
-1 1/2 |
2 |
|
4 |
1 1/2 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1/2 |
-1 |
|
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
1 |
|
7 |
1 1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 1/2 |
-2 |
|
f(x) |
56 1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 1/2 |
2 |
|
Итерация 3 |
|
|
|
|
|
|
|
|
|
|
Определяем значения α и β : |
|
|
|
|
|
|
|||
|
b |
a |
|
|
|
|
|
|
|
|
|
1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1/2 |
0 |
Вводим новую строку в симплекс-таблицу:
|
Базис |
B |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
2 |
4 1/2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
- 1/2 |
1 |
0 |
|
1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
|
3 |
4 1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 1/2 |
-2 |
0 |
|
6 |
2 1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
-1 1/2 |
2 |
0 |
|
4 |
1 1/2 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1/2 |
-1 |
0 |
|
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
1 |
0 |
|
7 |
1 1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 1/2 |
-2 |
0 |
|
10 |
- 1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
- 1/2 |
0 |
1 |
|
f(x) |
56 1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 1/2 |
2 |
0 |
|
Базис |
B |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
2 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
|
1 |
4 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
2 |
|
3 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-2 |
3 |
|
6 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
2 |
-3 |
|
4 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
1 |
|
5 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
-4 |
|
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
-2 |
3 |
|
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
-2 |
|
f(x) |
55 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
Найдено оптимальное решение.