Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
Большой класс прикладных задач оптимизации сводится к задачам целочисленного линейного программирования. Для решения этих задач широко применяются методы отсечения, предназначенные для решения общей целочисленной задачи, сопоставляя ей некоторую нецелочисленную задачу, по решению которой и позволяет найти решение. Первый методов решения целочисленной задачи линейного программирования отсечением был предложен Гомори и получил название алгоритма Гомори. 1. Постановка задачи Метод Гомори предназначен для решения целочисленных задач линейного программирования. При рассмотрении метода Гомори будем решать данную задачу в канонической форме. 1.1 Каноническая форма Будем рассматривать каноническую задачу целочисленного программирования с n переменными и m условиями, дополненную условием целочисленности: Где c = (c1, c2, … , cn), x = (x1, x2, … , xn) - вектора размерности n, - их скалярное произведение ( ), называемое так же целевой функцией, A - матрица размерности n ? m, b - вектор-столбец размерности m. Так может случиться, что задача (1.1)-(1.3) обладает допустимыми (целочисленными) планами, целевая функция ограничена на допустимом множестве, однако ее максимум не достигается. В связи со сказанным, при обосновании численных алгоритмов решения задач типа (1.1)-(1.3) приходится накладывать различные дополнительные условия. I. Будем считать, что множество X планов задачи (1.1), (1.2) (без условия целочисленности) ограничено, то есть является многогранником. Из этого условия вытекает, что множество X* всех целочисленных планов задачи (1.1)-(1.3) конечно. II. Будем обозначать через Xz выпуклую оболочку множества X*.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
