Это понятие используется для построения правильных отсечений на основе следующего утверждения если план не удовлетворяет условию целочисленности, то условие [c.113]
Такое ограничение называют правильным отсечением. В первой геометрической интерпретации правильному отсечению соответствует гиперплоскость, отсекающая от выпуклого многогранного множества допустимых планов D некоторый многогранник, не содержащий целочисленных планов. [c.143]
Таким образом, с точки зрения организации техники вычислений для осуществления правильного отсечения мы должны к системе ограничений нецелочисленной линейной задачи, решаемой на q-к итерации, добавить условие [c.145]
Первый шаг. Находим оптимальное опорное решение i (x х . .., х ) ослабления целочисленной задачи (9.47) — (9.50). Если р окажется целочисленным, то оно — искомое. В противном случае строим правильное отсечение, записываем его в виде [c.221]
Заменим решение исходной целочисленной задачи линейного программирования на многоугольнике решением ряда задач линейного программирования на многоугольниках ( , ( 2, Qa,... Здесь ( = Q. Многоугольники эти таковы, что множество целых точек в них одно и то же. Таким образом, понятно, что если оптимальный план задачи линейного программирования на многоугольнике Qs удовлетворяет условию целочисленности, то он является и оптимальным целочисленным планом исходной задачи. Процесс решения на этом заканчивается. Если же на многоугольнике Qs оптимальный план не удовлетворяет условию целочисленности, то происходит переход к < а+1 путем добавления одного правильного отсечения (на рис. 15 прямая АВ). Это вновь добавленное неравенство гарантирует, что оптимальный план, в котором не выполнялось условие целочисленности, заведомо не будет даже допустимым планом в последующих задачах. Ну, а множества целых точек это неравенство не сужает. Иными словами, правильные отсечения позволяют выбрасывать заведомо ненужные точки многоугольника ограничений, не теряя при этом нужных точек. Такая идея и лежит в основе метода Гомори. Ему удалось предложить алгориф-мический процесс построения правильных отсечений, не использующий ни рисунка, ни каких-либо других интуитивных соображений, что сделало бы его непригодным для решения многомерных задач. Кратко опишем этот алгорифм. [c.112]
В то же время (4.24) не выполняется для любого нецелочисленного базисного плана х. Действительно, небазисные компоненты плана равны нулю х] =0, /gMp(<7))> и (4.24) приобретает вид dJ O <=> 61 = 0, но это противоречит предположению о нецелочисленности плана я, т. к. в базисном плане xi =ai. Все сказанное позволяет утверждать, что ограничение (4.24) задает правильное отсечение. [c.145]
Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану. [c.147]
Задачи с неделимостями. Экстремальные комбинаторные задачи. Задачи с разрывными целевыми функциями. Правильное отсечение. Метод Гомори. Методы ветвей и границ. [c.157]
Какой принцип используется для построения правильного отсечения в методе Гомори [c.157]