Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение задачи методом ветвей и границ 1 страница
|
|
Согласно методу для каждой целочисленной переменной возможно задать верхнюю и нижнюю границу, в пределах которых содержится ее оптимальное значение. В данном случае нижняя граница равна 
. На практике верхний предел не вводят в виде дополнительного ограничения, а учитывают его в процессе решения не явно, то есть к исходным ограничения на практике добавляется ограничение, которое определяется самим методом.
Задача №1 - ослабленная задача. Данная задача решена в пункте 1.3. Добавим задачу в основной список. Решение:
Таблица 2.6
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
| X4 | 7/2 | -3/4 | 1/2 | 1/2 | -3/4 | ||||
| X6 | 229/8 | 21/16 | 23/8 | 29/8 | -99/16 | ||||
| X2 | 5/8 | 13/16 | -1/8 | -3/8 | 5/16 | ||||
| X1 | 35/8 | 11/16 | 1/8 | 3/8 | -13/16 | ||||
| Y | -109/8 | 139/16 | 9/8 | 11/8 | 3/16 |
Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи. Для образования порожденных задач выберем переменную Х4.
Задача №2 - к исходным данным задачи №1 добавляется ограничение Х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)
Целевая функция в форме Таккера:
Y=0-(4x1+5x2+17x3-2x4)
Таблица 2.7
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 |
| X5 | -2 | -2 | ||||||||
| X6 | -2 | -3 | -5 | |||||||
| X7 | -11 | -1 | -5 | -4 | -1 | |||||
| X8 | -10 | -2 | -2 | -3 | ||||||
| X9 | -4 | -1 | ||||||||
| Y | -2 |
Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7.
Таблица 2.8
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 |
| 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 | ||||||||
| Y | -11 | -3 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X8.
Таблица 2.9
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 |
| 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 | ||||||||
| Y | -43/2 | 83/8 | -9/4 | 1/4 | 15/8 |
Используем двойственный симплекс-метод. Вводим в базис X4, выводим из базиса X9.
Таблица 2.10
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 |
| 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 | |||||||||
| Y | -25/2 | 83/8 | 1/4 | 15/8 | -9/4 |
Используем двойственный симплекс-метод. Вводим в базис X8, выводим из базиса X5
Таблица 2.11
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 |
| 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 | |||||||||
| Y | -55/4 | 17/2 | 5/4 | 3/2 | 1/4 |
Решение оптимально. Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи. Для образования порожденных задач выберем переменную Х2.
Задача №4 - к исходным данным задачи №2 добавляется ограничение Х2> =1.
Выразим допустимый базис в форме Таккера:
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)
Целевая функция в форме Таккера:
Y=0-(4x1+5x2+17x3-2x4)
Таблица 2.12
| БП | СЧ | 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 | -1 | -1 | |||||||||
| Y | -2 |
Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7.
Таблица 2.13
| БП | СЧ | 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 | 6/5 | 1/5 | 4/5 | 1/5 | -1/5 | ||||||
| Y | -11 | -3 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X8.
Таблица 2.14
| БП | СЧ | 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 | 1/2 | 5/8 | 1/4 | -1/4 | 1/8 | ||||||
| Y | -43/2 | 83/8 | -9/4 | 1/4 | 15/8 |
Используем двойственный симплекс-метод. Вводим в базис X4, выводим из базиса X9.
Таблица 2.15
| БП | СЧ | 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.16
| БП | СЧ | 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 | -7/12 | 2/4 | 1/12 | -1/6 | 5/12 | ||||||
| Y | -55/4 | 17/2 | 5/4 | 3/2 | 1/4 |
Используем двойственный симплекс-метод. Вводим в базис X7, выводим из базиса X10.
Таблица 2.17
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |
| 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 | ||||||
| Y | -19 |
Решение оптимально. Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи. Для образования порожденных задач выберем переменную Х1.
Задача №6 - к исходным данным задачи №4 добавляется ограничение Х1> =6.
Выразим допустимый базис в форме Таккера:
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)
Целевая функция в форме Таккера:
Y=0-(4x1+5x2+17x3-2x4)
Таблица 2.18
| БП | СЧ | 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 | -6 | -1 | ||||||||||
| Y | -2 |
Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7.
Таблица 2.19
| БП | СЧ | 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 | -6 | -1 | ||||||||||
| Y | -11 | -3 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X11.
Таблица 2.20
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 |
| 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 | |||||||||||
| Y | -29 | -3 |
Используем двойственный симплекс-метод. Вводим в базис X4, выводим из базиса X9.
Таблица 2.21
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 |
| 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 | |||||||||||
| Y | -17 | -3 |
Используем двойственный симплекс-метод. Вводим в базис X7, выводим из базиса X10.