Студопедия

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

КАТЕГОРИИ:

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






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




Таблица 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-(-1*X1-2*X2+0*X3+0*X4)

x6=-9-(-2*X1+0*X2+0*X3+2*X4)

x7=-5-(-1*X1-1*X2+1*X3+2*X4)

x8=-2-(-1*X1+0*X2+2*X3-1*X4)

x9=-5-(-1*X1+0*X2+0*X3+0*X4)

x10=-2-(0*X1-1*X2+0*X3+0*X4)

x11=-2-(0*X1+0*X2-1*X3+0*X4)

x12=-6-(-1*X1+0*X2+0*X3+0*X4)

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

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

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

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


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