![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Рассмотрим пример. Методом Гоморинайти максимальное значение функции
Методом Гомори найти максимальное значение функции F = 3x1 + 2x2 (4) при условиях
x1-x2+x4=6, (5) -3x1+x2+x5=9,
xj ≥ 0 (j=1, 5), (6) xj – целые (j=1, 2). Решение. Для определения оптимального плана сначала решим задачу без учета целочисленности переменных. Как видно из табл. 3, найденный оптимальный план Х = (19/2; 7/2; 0; 0; 34) задачи не удовлетворяет условию целочисленности задачи, поскольку две компоненты х1 и х2 имеют нецелочисленные значения. При этом дробные части этих чисел равны между собой. Поэтому для одной из этих переменных составляется дополнительное ограничение. Составим, например, такое ограничение для переменной х2. Из симплекс-таблицы (табл. 3) имеем X2+ (1/2) x3 – (1/2) x4= 7/2
Таким образом, к системе ограничений задачи (5) – (6) добавляем неравенство
f (1) x2 + f (1/2) x3 -f (-1/2) x4 ≥ f (7/2), или (1/2) x3 + (1/2) x4 ≥ 1/2, т.е. x3+x4≥ 1. Таблица 3
Продолжим решение задачи двойственным симплекс-методом (Таблица 4) Из табл. 4 видно, что исходная задача целочисленного программирования имеет оптимальный план X* = (9; 4; 0; 1; 32). При этом плане значение целевой функции равно Fmax, = 35. Таблица 4
Контрольные вопросы и упражнения
а) z = 3x1 + 3x2→ max
3x1+2x2 ≥ 36 x2 ≤ 13 x1, x2 ≥ 0 (целые)
б) z = x1 + x2→ max
x2 ≤ 2 x1, x2 ≥ 0 (целые) в) z = x1 → max
3x1 – 8x2 +x4 = 24 x1, x2 ≥ 0 (целые)
|