Студопедия

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

КАТЕГОРИИ:

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






Решение задачи методом отсекающих плоскостей (метод Гомори)




Для решения целочисленной задачи воспользуется решением линейной задачи без требования целочисленности. Перепишем симплекс-таблицу решённой задачи из пункта 1.3.

Таблица 2.1

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X5 -5 -2
X1 9/2 -1 -1/2
X2 7/4 -2 1/4 -1 1/2
X3 5/4 -1 -1/4 1/2
Y -16

 

На основе этой симплекс-таблицы для базисной переменной x1 (у нее наибольшая дробная часть) строим уравнение отсекающей плоскости по следующей формуле:

где f – дробная часть свободного члена;

fij – дробные части коэффициентов строки.

Представим новое ограничение в форме Куна-Таккера:

x9=-1/2-(-5/16*x3-7/8*x5-5/8*x7-13/16*x8)

Добавляем это ограничение к условиям оптимального решения и решаем новую расширенную задачу симплекс-методом.

Таблица 2.2

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
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
X9 -5/8 -5/16 -7/8 -5/8 -13/16
Y -109/8 139/16 9/8 11/8 3/16

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

Таблица 2.3

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X4 53/13 -6/13 17/13 14/13 -12/13
X6 434/13 48/13 124/13 109/13 -99/13
X2 5/13 9/13 -6/13 -8/13 5/13
X1 -1
X8 10/13 5/13 14/13 10/13 -16/13
Y -179/13 112/13 12/13 16/13 3/13

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

x10=-10/13-(-5/13*x3-1/13*x5-10/13*x7-10/13*x9)

 

Таблица 2.4

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X4 53/13 -6/13 17/13 14/13 -12/13
X6 434/13 48/13 124/13 109/13 -99/13
X2 5/13 9/13 -6/13 -8/13 5/13
X1 -1
X8 10/13 5/13 14/13 10/13 -16/13
X10 -10/13 -5/13 -1/13 -10/13 -10/13
Y -179/13 112/13 12/13 16/13 3/13

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



Таблица 2.5

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X4 7/5 -6/5
X6 15/2 103/10 -99/10
X2 1/2 -1/2 -1 1/2
X1 3/2 11/10 -13/10
X8 6/5 -8/5
X9 1/2 1/10 -13/10
Y -182/13 17/2 9/10 3/10

Полученное решение удовлетворяет поставленным ограничениям и требованиям целочисленности. Решение является оптимальным.

 

Ответ: Y=-14, X=(6;0;0;5;0;41;0;2;1;0).

 



mylektsii.ru - Мои Лекции - 2015-2018 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал