Студопедия

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

КАТЕГОРИИ:

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






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




Таблица 2.1.33

БП СЧ 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 1/2 1/2
Y -14 -3

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

Таблица 2.1.34

БП СЧ 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 -1/4 1/4 1/2
Y -37/2 1/2

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

Таблица 2.1.35

БП СЧ 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 -2/3 1/3 2/3 -1/3 5/3
Y -58/3 2/3 10/3 1/3 13/3

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

Таблица 2.1.36

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

Решение данной задачи: Решения нет.



 

Задача №7:

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

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

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=1-(0x1+0x2+x3+0x4)

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

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

Таблица 2.1.37

БП СЧ 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
Y -3

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

Таблица 2.1.38



БП СЧ 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
Y -18 -3

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

Таблица 2.1.39

БП СЧ 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
Y -20 -3

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

Таблица 2.1.40

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

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

Таблица 2.1.41

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

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

 

Задача №5:

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

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

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=1-(0x1+x2+0x3+0x4)

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

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

Таблица 2.1.42

БП СЧ 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
Y -3

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

Таблица 2.1.43

БП СЧ 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
Y -18 -3

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

Таблица 2.1.44

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
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
X10 1/2 -1/2
Y -37/2 -2 3/2

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

Таблица 2.1.45

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

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

Таблица 2.1.46

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

Решение данной задачи: Y=-18;X=(5;1;1;0;4;1;0;1;0;0)


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