Студопедия

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

КАТЕГОРИИ:

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






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




Максимизировать целевую функцию

При ограничениях:

и целые.

Для решения этой полностью целочисленной задачи воспользуемся методом Гомори. Решаем исходную задачу линейного программирования. Ее решение приведено в пункте 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

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

Ответ: .


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