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