Студопедия

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

КАТЕГОРИИ:

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






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




Таблица 2.22

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

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

Таблица 2.23

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X9 1/3 -2/3 1/3 2/3 -2/3
X6 113/3 -1/3 5/3 10/3 -19/3
X2 -1
X8 -3 -2 -2
X4 13/3 -2/3 1/3 2/3 -2/3
X7 13/3 -14/3 1/3 -13/3 -5/3
X1 -1
Y -61/3 47/3 2/3 19/3 8/3

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

Задача №8 - к исходным данным задачи №6 добавляется ограничение Х4>=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=-6-(-1x1+0x2+0x3+0x4)

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

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

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

Таблица 2.24

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

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



Таблица 2.25

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

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

Таблица 2.26

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

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



Таблица 2.27

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

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

Таблица 2.28

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

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

Таблица 2.29

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

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

Задача №9 - к исходным данным задачи №6 добавляется ограничение Х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)

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

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

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

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

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

Таблица 2.30

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

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

Таблица 2.31

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

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

Таблица 2.32

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

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

Таблица 2.33

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

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


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