Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение задачи методом ветвей и границ 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)