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