Мегаобучалка Главная | О нас | Обратная связь

Решение задачи методом ветвей и границ




Согласно методу для каждой целочисленной переменной возможно задать верхнюю и нижнюю границу, в пределах которых содержится ее оптимальное значение. В данном случае нижняя граница равна нулю. На практике верхний предел не вводят в виде дополнительного ограничения, а учитывают его в процессе решения не явно, то есть к исходным ограничения на практике добавляется ограничение, которое определяется самим методом.

Решаем исходную задачу - Задачу №1(п.1.3) до получения оптимального решения методом линейного программирования. Воспользуемся итоговой таблицей (Таблица 1.13). Эта таблица и будет исходной для нашей задачи (Таблица 2.1.6).

Таблица 2.1.6

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X5 -5 -2
X1 9/2 -1 -1/2
X2 7/4 -2 1/4 -1 1/2
X3 5/4 -1 -1/4 1/2
Y -16

 

Полученное решение не удовлетворяет требованиям целочисленности.

Поэтому составляем относительно любой нецелочисленной переменной две новых порожденных задачи (2 и 3). Выберем переменную x1. ПримемY1 = 0.

Новые ограничения строятся по формуле:

1) х ≤ [х*]

2) x ≥ [х*] + 1

где [х*] – целая часть числа х* (нецелочисленная переменная)

Задача №2:

Добавляется ограничение x1≥5. Тогда задача примет вид:

 

При ограничениях:

x1≥5

и целые.

Выразим допустимый базис в форме Таккера:

x5=-3-(-x1-2x2+0x3+0x4)

x6=-9-(-2x1+0x2+0x3+2x4)

x7=-5-(-x1-x2+x3+2x4)

x8=-2-(-x1+0x2+2x3-x4)

x9=-5-(-x1+0x2+0x3+0x4)

Целевая функция в форме Таккера

Y=0-(4x1+x2-3x3+2x4)

 

Таблица 2.1.7

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -3 -1 -2 0 0 1 0 0 0 0
X6 -9 -2 0 0 2 0 1 0 0 0
X7 -5 -1 -1 1 2 0 0 1 0 0
X8 -2 -1 0 2 -1 0 0 0 1 0
X9 -5 -1 0 0 0 0 0 0 0 1
Y 0 4 1 -3 2 0 0 0 0 0

Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6

Таблица 2.1.8

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 3/2 -2 -1 -1/2
X1 9/2 -1 -1/2
X7 -1/2 -1 -1/2
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
Y -18 -3

Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x7



Таблица 2.1.9

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 5/2 -2 -3 1/2 -2
X1 9/2 -1 -1/2
X2 1/2 -1 -1 1/2 -1
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
Y -37/2 -2 3/2

Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x9

Таблица 2.1.10

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -2 -4 -2
X1 -1
X2 -1 -2 -1
X8 -1 -1
X6 -2
Y -20 -2

Используем обычный симплекс-метод. Вводим в базис x3, выводим из базиса x8

Таблица 2.1.11

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -5 -2
X1 -1
X2 3/2 -5/2 -1 1/2 1/2
X3 3/2 -1/2 1/2 -1/2
X6 -2
Y -17

Решение данной задачи: Y=-17; X=(5;3/2;3/2;0;5;1;0;0;0)

 

Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи.

Для образования порожденных задач выберем переменную x2

Задача №4:

Добавляется ограничение x2≥2.

Выразим допустимый базис в форме Таккера:

x5=-3-(-x1-2x2+0x3+0x4)

x6=-9-(-2x1+0x2+0x3+2x4)

x7=-5-(-x1-x2+x3+2x4)

x8=-2-(-x1+0x2+2x3-x4)

x9=-5-(-x1+0x2+0x3+0x4)

x10=-2-(0x1-x2+0x3+0x4)

Целевая функция в форме Таккера

Y=0-(4x1+x2-3x3+2x4)

Таблица 2.1.12

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -3 -1 -2
X6 -9 -2
X7 -5 -1 -1
X8 -2 -1 -1
X9 -5 -1
X10 -2 -1
Y -3

Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6

Таблица 2.1.13

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 3/2 -2 -1 -1/2
X1 9/2 -1 -1/2
X7 -1/2 -1 -1/2
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
X10 -2 -1
Y -18 -3

Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10

Таблица 2.1.14

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 11/2 -1 -1/2 -2
X1 9/2 -1 -1/2
X7 3/2 -1/2 -1
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
X2 -1
Y -20 -3

Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x9

Таблица 2.1.15

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -1 -2
X1 -1
X7 -1 -1
X8 -1 -1
X6 -2
X2 -1
Y -22 -3

Используем обычный симплекс-метод. Вводим в базис x3, выводим из базиса x8

Таблица 2.1.16

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -1 -2
X1 -1
X7 1/2 5/2 -1/2 -1/2 -1
X3 3/2 -1/2 1/2 -1/2
X6 -2
X2 -1
Y -35/2 1/2 3/2 5/2

Решение данной задачи: Y=-35/2; X=(5;2;3/2;0;6;1;1/2;0;0;0)

 

Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи.

 

Для образования порожденных задач выберем переменную x3

Задача №6:

Добавляется ограничение x3≥2

Выразим допустимый базис в форме Таккера

x5=-3-(-x1-2x2+0x3+0x4)

x6=-9-(-2x1+0x2+0x3+2x4)

x7=-5-(-x1-x2+x3+2x4)

x8=-2-(-x1+0x2+2x3-x4)

x9=-5-(-x1+0x2+0x3+0x4)

x10=-2-(0x1-x2+0x3+0x4)

x11=-2-(0x1+0x2-x3+0x4)

Целевая функция в форме Таккера

Y=0-(4x1+x2-3x3+2x4)

Таблица 2.1.17

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 -3 -1 -2
X6 -9 -2
X7 -5 -1 -1
X8 -2 -1 -1
X9 -5 -1
X10 -2 -1
X11 -2 -1
Y -3

Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6

Таблица 2.1.18

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 3/2 -2 -1 -1/2
X1 9/2 -1 -1/2
X7 -1/2 -1 -1/2
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
X10 -2 -1
X11 -2 -1
Y -18 -3

Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10

Таблица 2.1.19

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 11/2 -1 -1/2 -2
X1 9/2 -1 -1/2
X7 3/2 -1/2 -1
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
X2 -1
X11 -2 -1
Y -20 -3

Используем двойственный симплекс-метод. Вводим в базис x3, выводим из базиса x11

Таблица 2.1.20

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 11/2 -1 -1/2 -2
X1 9/2 -1 -1/2
X7 -1/2 -1/2 -1
X8 -3/2 -2 -1/2
X9 -1/2 -1 -1/2
X2 -1
X3 -1
Y -14 -3

Используем двойственный симплекс-метод. Вводим в базис x4, выводим из базиса x8

Таблица 2.1.21

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 25/4 -1/4 -1/2 -2 -1
X1 21/4 -1/4 -1/2 -1
X7 -5/4 -3/4 1/2 -1
X4 3/4 1/4 -1/2 -1
X9 1/4 -1/4 -1/2 -1
X2 -1
X3 -1
Y -37/2 1/2

Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x7

Таблица 2.1.22

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 20/3 -1/3 -2/3 -5/3 -5/3
X1 17/3 -1/3 -2/3 1/3 -5/3
X6 5/3 -4/3 -2/3 4/3 -8/3
X4 1/3 1/3 -1/3 -1/3 -1/3
X9 2/3 -1/3 -2/3 1/3 -5/3
X2 -1
X3 -1
Y -58/3 2/3 10/3 1/3 13/3

Решение данной задачи: Y=-58/3;X=(17/3;2;2;1/3;20/3;5/3;0;0;2/3;0;0)

 

Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи.

 

Для образования порожденных задач выберем переменную x1

 

Задача №8:

Добавляется ограничение x1≥6

Выразим допустимый базис в форме Таккера:

x9=-3-(-x1-2x2+0x3+0x4)

x6=-9-(-2x1+0x2+0x3+2x4)

x7=-5-(-x1-x2+x3+2x4)

x8=-2-(-x1+0x2+2x3-x4)

x9=-5-(-x1+0x2+0x3+0x4)

x10=-2-(0x1-x2+0x3+0x4)

x11=-2-(0x1+0x2-x3+0x4)

x12=-6-(-x1+0x2+0x3+0x4)

Целевая функция в форме Таккера

Y=0-(4x1+x2-3x3+2x4)

Таблица 2.1.23

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 -3 -1 -2
X6 -9 -2
X7 -5 -1 -1
X8 -2 -1 -1
X9 -5 -1
X10 -2 -1
X11 -2 -1
X12 -6 -1
Y -3

Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6

Таблица 2.1.24

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 3/2 -2 -1 -1/2
X1 9/2 -1 -1/2
X7 -1/2 -1 -1/2
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
X10 -2 -1
X11 -2 -1
X12 -3/2 -1 -1/2
Y -18 -3

Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10

Таблица 2.1.25

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 11/2 -1 -1/2 -2
X1 9/2 -1 -1/2
X7 3/2 -1/2 -1
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
X2 -1
X11 -2 -1
X12 -3/2 -1 -1/2
Y -20 -3

Используем двойственный симплекс-метод. Вводим в базис x3, выводим из базиса x11

Таблица 2.1.26

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 11/2 -1 -1/2 -2
X1 9/2 -1 -1/2
X7 -1/2 -1/2 -1
X8 -3/2 -2 -1/2
X9 -1/2 -1 -1/2
X2 -1
X3 -1
X12 -3/2 -1 -1/2
Y -14 -3

Используем двойственный симплекс-метод. Вводим в базис x4, выводим из базиса x8

Таблица 2.1.27

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 25/4 -1/4 -1/2 -2 -1
X1 21/4 -1/4 -1/2 -1
X7 -5/4 -3/4 1/2 -1
X4 3/4 1/4 -1/2 -1
X9 1/4 -1/4 -1/2 -1
X2 -1
X3 -1
X12 -3/4 -1/4 -1/2 -1
Y -37/2 1/2

Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x7

Таблица 2.1.28

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 20/3 -1/3 -2/3 -5/3 -5/3
X1 17/3 -1/3 -2/3 1/3 -5/3
X6 5/3 -4/3 -2/3 4/3 -8/3
X4 1/3 1/3 -1/3 -1/3 -1/3
X9 2/3 -1/3 -2/3 1/3 -5/3
X2 -1
X3 -1
X12 -1/3 -1/3 -2/3 1/3 -5/3
Y -58/3 2/3 10/3 1/3 13/3

Используем двойственный симплекс-метод. Вводим в базис x7, выводим из базиса x12

Таблица 2.1.29

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 -2 -1
X1 -1
X6 -4
X4 -1 -2
X9 -1
X2 -1
X3 -1
X7 -1 -3
Y -20

Решение данной задачи: Y=-20;X=(6;2;2;0;7;3;1;0;1;0;0;0)

 

Задача №9:

Добавляется ограничение x1≤5

Выразим допустимый базис в форме Таккера:

x5=-3-(-x1-2x2+0x3+0x4)

x6=-9-(-2x1+0x2+0x3+2x4)

x7=-5-(-x1-x2+x3+2x4)

x8=-2-(-x1+0x2+2x3-x4)

x9=-5-(-x1+0x2+0x3+0x4)

x10=-2-(0x1-x2+0x3+0x4)

x11=-2-(0x1+0x2-x3+0x4)

x12=5-(x1+0x2+0x3+0x4)

Целевая функция в форме Таккера:

Y=0-(4x1+x2-3x3+2x4)

Таблица 2.1.30

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 -3 -1 -2
X6 -9 -2
X7 -5 -1 -1
X8 -2 -1 -1
X9 -5 -1
X10 -2 -1
X11 -2 -1
X12
Y -3

Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6

Таблица 2.1.31

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 3/2 -2 -1 -1/2
X1 9/2 -1 -1/2
X7 -1/2 -1 -1/2
X8 5/2 -2 -1/2
X9 -1/2 -1 -1/2
X10 -2 -1
X11 -2 -1
X12 1/2 1/2
Y -18 -3

Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10

Таблица 2.1.32





Читайте также:





Читайте также:
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...
Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация...
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...

©2015 megaobuchalka.ru Все права защищены авторами материалов.

Почему 3458 студентов выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.028 сек.)