Учебная работа № 6120. «Курсовая Пример решения методом Баллаша

Выдержка из похожей работы

Отбросив на определенное время условие целочисленности (4), найдем оптимальное решение симплекс-методом,Если окажется, что он удовлетворяет также и условию целочисленности, то это решение является искомым,2,В противном случае нужно выбрать компоненту оптимального решения с наибольшей целой частью (иногда наибольшей дробной частью, иногда другой критерий эффективности отсечения) и по соответствующему уравнению на основе последней симплекстаблицы сформировать ‘правильное отсечение’ на основе неравенства

{Вi опт,} – {Ai m+1} X m+1 — … — {Ain} Xn <= 0,(5)где Х m+1, …, Xn - неосновные переменные,{} означают дробную часть числа, например: {4/3} = 4/3 – 3/3 = 1/3,{-4/3}=– 4/3 – (– 2) = 2/33,В неравенство (5) вводим дополнительную неотрицательную целочисленную переменную Хn+1; преобразовываем (5) в уравнение и включаем в систему ограничений (2),4,Полученную новую задачу решают симплекс-методом,Если найденный новый оптимальный план – целочисленный, то задача ЛЦП решена, Иначе переходят к п,2 алгоритма, Пример решения методом Гомори(1)При условии(2)  (3) – целые(4)Для определения оптимального плана задачи (1) – (4) сначала находим оптимальный план задачи (1) – (3),На основе симплекс-таблицыполучим: продолжениеОптимальный план задачи (1) – (3) не является оптимальным планом задачи (1) – (4), поскольку две компоненты Х1 и Х2 имеют нецелочисленные значения, При этом целая часть больше для компоненты Х1,1, Составим ограничение для переменной Х1 из последней симплекс– таблицы:или{Вi опт,} – {Ai m+1} X m+1 - … - {Ain} Xn <= 0,2,Добавим к системе ограничений задачи (1) – (4),3,Вводим новую дополнительную переменную и решаем симплексметодом (точнее, модифицированным симплекс-методом,т