Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение задачи методом отсекающих плоскостей
|
|
Максимизировать целевую функцию
При ограничениях:
и целые.
Для решения этой полностью целочисленной задачи воспользуемся методом Гомори. Решаем исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:
| Таблица 2.1.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 |
Значения целевой функции и переменных: 
На основе этой симплексной таблицы для базисной переменной 
, у которой наибольшая дробная часть, строим уравнение отсекающей плоскости.
Вводим новую свободную переменную: 
Выражаем новое ограничение в форме Куна-Таккера: 
Добавляем это ограничение к условиям оптимального решения и решаем новую расширенную задачу симплекс методом.
| Таблица 2.1.2 | ||||||||||
| БП | СЧ | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| 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 | ||||||
| x9 | -3/4 | -1/4 | -1/2 | |||||||
| Y | -16 |
| Таблица 2.1.3 | ||||||||||
| БП | СЧ | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| x5 | 7/2 | -5 | -1/2 | -2 | ||||||
| x1 | 9/2 | -1 | -1/2 | |||||||
| x2 | -2 | -1 | ||||||||
| x3 | ½ | -1 | -1/2 | |||||||
| x8 | 3/2 | 1/2 | -2 | |||||||
| Y | -35/2 | 1/2 |
Требование целочисленности не выполнено. Составляем следующее уравнение отсекающей плоскости. Т.к. дробные части у всех нецелых значений базисных переменных равны, выберем любую, например 
.
Аналогично: 
.
Теперь решаем новую расширенную задачу.
| Таблица 2.1.4 | |||||||||||
| БП | СЧ | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 |
| x5 | 7/2 | -5 | -1/2 | -2 | |||||||
| x1 | 9/2 | -1 | -1/2 | ||||||||
| x2 | -2 | -1 | |||||||||
| x3 | ½ | -1 | -1/2 | ||||||||
| x8 | 3/2 | 1/2 | -2 | ||||||||
| x10 | -1/2 | -1/2 | |||||||||
| Y | -35/2 | 1/2 |
| Таблица 2.1.5 | |||||||||||
| БП | СЧ | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 |
| x5 | -5 | -2 | -1 | ||||||||
| x1 | -1 | -1 | |||||||||
| x2 | -2 | -1 | |||||||||
| x3 | -1 | -1 | |||||||||
| x8 | -2 | ||||||||||
| x6 | -2 | ||||||||||
| Y | -18 |
Полученное оптимальное решение удовлетворяет поставленным ограничениям и требованиям целочисленности.
Ответ: 
.