Студопедия

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

КАТЕГОРИИ:

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






Решение задачи методом отсекающих плоскостей (метод Гомори). Приведём решение исходной задачи симплекс-методом, опустив требование целочисленности




Приведём решение исходной задачи симплекс-методом, опустив требование целочисленности. Оно представлено в таблице 2.53.

Таблица 2.53

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

Значение переменной x4 не удовлетворяет требованиям целочисленности. Поэтому вводим дополнительное отсечение, исходя из данной строки.

Ограничения для частично-целочисленных задач по методу Гомори формируются в виде:

где - дробная часть свободного члена базисной переменной,

- коэффициент, рассчитываемый для небазисных переменных.

Для не подчиненных требованию целочисленности коэффициент рассчитывается по формуле:

Для подчиненных требованию целочисленности коэффициент рассчитывается по формуле:

Вычислим отсекающую плоскость и представим ее в форме Таккера:

X9=-1/2-(-3/4*X3-1/2*X5-1/2*X7-3/4*X8)

Добавим в базис таблицы 2.53 полученное ограничение. Результат представлен в таблице 2.54.

Таблица 2.54

БП СЧ 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 -1/2 -3/4 -1/2 -1/2 -3/4
Y -109/8 139/16 9/8 11/8 3/16

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

Таблица 2.55

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X4 -1
X6 131/4 15/2 31/4 -33/4
X2 5/12 2/4 -2/6 -7/12 5/12
X1 59/12 6/4 4/6 11/12 -13/12
X8 2/3 2/3 2/3 -4/3
Y -55/4 17/2 5/4 1/4

Полученное оптимальное решение удовлетворяет требованию целочисленности х4.

 

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



 



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