Метод отсечения (метод Гомори). - раздел Образование, Курс лекций Основные понятия и определения Сначала Задача Решается Без Условия Целочисленности, Если Полученный План Цел...
Сначала задача решается без условия целочисленности, если полученный план целочисленный, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана;
Такое дополнительное отсечение называется правильным отсечением.
Алгоритм решения ЗЛЦП, предложенный Гомори, основан на симплексном методе и использует способ построения правильного отсечения.
Неравенство, сформированное по i-тому уравнению системы ограничения оптимального решения, имеет вид:
βi - αim+1 xm+1-…- αm xn≤0 (1),
где {βi}, { αim+1}, { αm} – не целые компоненты коэффициентов.
Целой частью числа а называется наибольшее число [α], не превосходящее α; дробной частью числа а является числа α =α-[α]. Например для
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ... МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... Г С БОРОВСКИЙ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Метод отсечения (метод Гомори).
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Решение.
X1, X2– число единиц видов изделий соответственно А и В.
№ п/п
Алгоритм
Конкретное соответствие данной задаче
Геометрическая интерпретация решения ЗЛП.
Графический метод решения ЗЛП состоит из следующих этапов:
На координатной плоскости Х1ОХ2 строится область допустимых решений (ОДР). Она представляет собой мно
Выполнить самостоятельно.
В соответствии с индивидуальным заданием №1 решить задачу максимизации с использованием симплексных таблиц. Вариант задания выбирается по номеру зачетной книжки:
-предпоследняя цифра - № с
Алгоритм решения ЗЛЦП
1.Симплексным методом решить задачу без учета условия целочисленности, если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.
Метод множителей Лагранжа.
Другой способ определения условного экстремума осуществляется с построения вспомогательной функции Лагранжа, которая достигает max для тех же х1,х2,…,хn, что и целе
Новости и инфо для студентов