Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Метод отсечения (метод Гомори).
Сначала задача решается без условия целочисленности, если полученный план целочисленный, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами: - оно должно быть линейным; - должно отсекать найденный нецелочисленный план; - не должно отсекать ни одного целочисленного плана;
Такое дополнительное отсечение называется правильным отсечением. Алгоритм решения ЗЛЦП, предложенный Гомори, основан на симплексном методе и использует способ построения правильного отсечения. Неравенство, сформированное по i-тому уравнению системы ограничения оптимального решения, имеет вид: βi - αim+1 xm+1-…- αm xn≤0 (1), где {βi}, { αim+1}, { αm} – не целые компоненты коэффициентов. Целой частью числа а называется наибольшее число [α], не превосходящее α; дробной частью числа а является числа α =α-[α]. Например для α =2⅓; [α]=2, α =2⅓ -2=1/3,для
α = -2⅓; [α]= -3, α = -2⅓-(-3)=2/3 Алгоритм решения ЗЛЦП 1.Симплексным методом решить задачу без учета условия целочисленности, если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.
2.Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и сформировать правильное отсечение.
3.Неравенство, определяющее правильное отсечение введением дополнительной, неотрицательной целочисленной переменной, преобразовать в равносильное уравнение и включить его в систему ограничений.
4.Полученную расширенную задачу решить симплексным методом, если оптимальный план будет целочисленным, то задача ЛЦП решена, в противном случае вернуться к пункту 2 алгоритма.
Пример: При решении некоторой оптимизационной задачи симплексным методом получено некоторое базисное решение: х1= 2 – 1 х4 + 4 х5 3 3 3 х2=8 – х5 х3=18+х4+х5 Z=25 1 – 2 x4 – 1 x5 3 3 3
X=(2; 8; 18; 0; 0) Z=25 1 3 3 Это базисное решение оптимизировано. Однако решение Х не удовлетворяет условию целочисленности, т.к. по первому уравнению с переменной x1=2/3-1/3x4+4/3x5 , получившей нецелочисленное значение в оптимальном решении(2/3). Составляем правильное отсечение, в виде дополнительного ограничения.
2/3 + 1/3 х4– 4/3 х5≤0 (1) Обращаем внимание на то, что берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при не основных переменных х4 и х5 – с противоположными знаками. Так как дробные части: 2/3 = 0+2/3 =2/3
1/3 = 0+1/3 =1/3
-4/3 = -2+2/3 =2/3, тогда последнее неравенство в соответствии c (1) запишется в виде: 2/3+1/3х4-2/3х5≤0 (2)–правильное отсечение.
Введя дополнительную целочисленную переменную х6 ≥ 0, получим равносильное неравенству (2),уравнение:
2/3+1/3х4-2/3х5 +х6=0 Включаем это уравнение в систему ограничений, после чего повторяем алгоритм решения задачи симплексным методом, применительно к расширенной задаче. Дополнительное уравнение вводится в систему, полученную на последнем шаге решения задачи(без условия целочисленности).
|
|||||
Последнее изменение этой страницы: 2017-02-17; просмотров: 210; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.131.110.169 (0.004 с.) |