Студопедия

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

КАТЕГОРИИ:

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






Решение задачи методом ветвей и границ 3 страница. Таблица 2.34 БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X5 -2




Таблица 2.34

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

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

Таблица 2.35

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

Решение оптимально.

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

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

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

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

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

Таблица 2.36

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

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

Таблица 2.37

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

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



Таблица 2.38

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
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
X11 3/2 -7/8 1/4 -1/4 5/8
Y -43/2 83/8 -9/4 1/4 15/8

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

Таблица 2.39

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
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
X11 1/2 -7/8 -1/4 5/8 1/4
Y -25/2 83/8 1/4 15/8 -9/4

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



Таблица 2.40

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
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
X11 1/12 -6/4 5/12 1/6 13/12
Y -55/4 17/2 5/4 3/2 1/4

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

Таблица 2.41

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

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

Таблица 2.42

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X8 7/2 -3/2 -9/2 -5 -1
X6 63/2 3/2 -1/2
X2 -1
X1
X4 -1
X7 -2 -7 -9 -3
X3 1/2 -1/2 -3/2 -1 -1
Y -51/2 17/2 47/2

Решение оптимально. Остановка: текущее значение целевой функции <=-21.

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

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

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

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

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

Таблица 2.43

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

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

Таблица 2.44

БП СЧ 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 -11/5 -1/5 -4/5 -1/5 1/5
Y -11 -3

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

Таблица 2.45

БП СЧ 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 -3/2 -5/8 -1/4 1/4 -1/8
Y -43/2 83/8 -9/4 1/4 15/8

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

Таблица 2.46

БП СЧ 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.47

БП СЧ 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 -5/12 -2/4 -1/12 1/6 -5/12
Y -55/4 17/2 5/4 3/2 1/4

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

Таблица 2.48

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X8 13/5 -2/5 -6/5 -16/5
X6 87/5 2/5 -19/5 -99/5
X2
X1 14/5 -1/5 -3/5 -13/5
X4 6/5 1/5 -2/5 -12/5
X9 6/5 1/5 -2/5 -12/5
Y -14 41/5 6/5 8/5 3/5

Решение оптимально.


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.014 сек.)Пожаловаться на материал