Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




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

Задача №1 - ослабленная задача. Данная задача решена в пункте 1.3. Добавим задачу в основной список. Решение:

Таблица 2.6

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X4 7/2 -3/4 1/2 1/2 -3/4
X6 229/8 21/16 23/8 29/8 -99/16
X2 5/8 13/16 -1/8 -3/8 5/16
X1 35/8 11/16 1/8 3/8 -13/16
Y -109/8 139/16 9/8 11/8 3/16

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

Задача №2 - к исходным данным задачи №1 добавляется ограничение Х4>=4

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

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

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

x7=-11-(-1x1-5x2-4x3-1x4)

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

x9=-4-(0x1+0x2+0x3-1x4)

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

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

Таблица 2.7

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

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

Таблица 2.8

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -7/5 -12/5 -18/5 13/5 2/5
X6 -2 -3 -5
X2 11/5 1/5 4/5 1/5 -1/5
X8 -28/5 -8/5 -7/5 2/5 -2/5
X9 -4 -1
Y -11 -3

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

Таблица 2.9

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -3/2 -3/2
X6 17/2 45/8 -23/4 3/4 -15/8
X2 3/2 5/8 1/4 -1/4 1/8
X1 7/2 7/8 -1/4 1/4 -5/8
X9 -4 -1
Y -43/2 83/8 -9/4 1/4 15/8

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



Таблица 2.10

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -1 -3/2 -3/2
X6 63/2 45/8 3/4 -15/8 -23/4
X2 1/2 5/8 -1/4 1/8 1/4
X1 9/2 7/8 1/4 -5/8 -1/4
X4 -1
Y -25/2 83/8 1/4 15/8 -9/4

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

Таблица 2.11

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X8 2/3 -2/3 -2/3 -4/3
X6 131/4 15/2 -5/4 -1/2 -33/4
X2 5/12 2/4 1/12 -1/6 5/12
X1 59/12 3/2 -5/12 -1/6 -13/12
X4 -1
Y -55/4 17/2 5/4 3/2 1/4

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

Задача №4 - к исходным данным задачи №2 добавляется ограничение Х2>=1 .



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

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

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

x7=-11-(-1x1-5x2-4x3-1x4)

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

x9=-4-(0x1+0x2+0x3-1x4)

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

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

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

Таблица 2.12

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

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

Таблица 2.13

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -7/5 -12/5 -18/5 13/5 2/5
X6 -2 -3 -5
X2 11/5 1/5 4/5 1/5 -1/5
X8 -28/5 -8/5 -7/5 2/5 -2/5
X9 -4 -1
X10 6/5 1/5 4/5 1/5 -1/5
Y -11 -3

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

Таблица 2.14

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -3/2 -3/2
X6 17/2 45/8 -23/4 3/4 -15/8
X2 3/2 5/8 1/4 -1/4 1/8
X1 7/2 7/8 -1/4 1/4 -5/8
X9 -4 -1
X10 1/2 5/8 1/4 -1/4 1/8
Y -43/2 83/8 -9/4 1/4 15/8

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

Таблица 2.15

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -1 -3/2 -3/2
X6 63/2 45/8 3/4 -15/8 -23/4
X2 1/2 5/8 -1/4 1/8 1/4
X1 9/2 7/8 1/4 -5/8 -1/4
X4 -1
X10 -1/2 5/8 -1/4 1/8 1/4
Y -25/2 83/8 1/4 15/8 -9/4

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

Таблица 2.16

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X8 2/3 -2/3 -2/3 -4/3
X6 131/4 15/2 -5/4 -1/2 -33/4
X2 5/12 2/4 1/12 -1/6 5/12
X1 59/12 3/2 -5/12 -1/6 -13/12
X4 -1
X10 -7/12 2/4 1/12 -1/6 5/12
Y -55/4 17/2 5/4 3/2 1/4

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

Таблица 2.17

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X8 -1 -1 -3 -4
X6 69/2 -3/2 -19/2 -3
X2 -1
X1 11/2 -1/2 -3/2 -1
X4 -1
X7 7/2 -3 -1/2 -5/2 -6
Y -19

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

Задача №6 - к исходным данным задачи №4 добавляется ограничение Х1>=6 .

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

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

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

x7=-11-(-1x1-5x2-4x3-1x4)

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

x9=-4-(0x1+0x2+0x3-1x4)

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

x11=-6-(-1x1+0x2+0x3+0x4)

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

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

 

Таблица 2.18

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

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

Таблица 2.19

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 -7/5 -12/5 -18/5 13/5 2/5
X6 -2 -3 -5
X2 11/5 1/5 4/5 1/5 -1/5
X8 -28/5 -8/5 -7/5 2/5 -2/5
X9 -4 -1
X10 6/5 1/5 4/5 1/5 -1/5
X11 -6 -1
Y -11 -3

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

Таблица 2.20

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 -18/5 13/5 2/5 -12/5
X6 -5 -3
X2 4/5 1/5 -1/5 1/5
X8 -7/5 2/5 -2/5 -8/5
X9 -4 -1
X10 4/5 1/5 -1/5 1/5
X1 -1
Y -29 -3

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

Таблица 2.21

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

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


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.022 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал