Студопедия

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

КАТЕГОРИИ:

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






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




.

Задача №1 - исходная задача со снятым требованием целочисленности. Перепишем решение из таблицы 1.12.

Таблица 2.56

БП СЧ 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.57

БП СЧ 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.58

БП СЧ 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.59

БП СЧ 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.60

БП СЧ 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.61

БП СЧ 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

Решение задачи удовлетворяет требованию целочисленности для переменной х4, и значение целевой функции больше, чем найденное до этого оптимально . На данной итерации найдено новое оптимально целочисленное решение.



Задача №3 - к исходным данным задачи №1 добавляется ограничение Х4<=3.

Выразим допустимый базис в форме Таккера:

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=3-(0x1+0x2+0x3+1x4)

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

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

 

Таблица 2.62

БП СЧ 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
Y -2

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

Таблица 2.63

БП СЧ 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
Y -11 -3

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

Таблица 2.64

БП СЧ 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
Y -43/2 83/8 -9/4 1/4 15/8

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

Таблица 2.64

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -3/2 -3/2 -2
X6 103/4 45/8 3/4 -15/8 23/4
X2 3/4 5/8 -1/4 1/8 -1/4
X1 17/4 7/8 1/4 -5/8 1/4
X4
Y -59/4 83/8 1/4 15/8 9/4

Остановка: Решение задачи удовлетворяет требованию целочисленности для переменной х4, но значение целевой функции не больше, чем найденное до этого.

Список задач пуст. Блок-схема решения задачи представлена на рисунке 2.2.

 

Ответ: Y=-55/4, X=(59/12;5/12;0;4;0;131/4;0;2/3;0).

Рисунок 2.2 - Схема решения частично целочисленной задачи методом ветвей и границ.

 



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