Курсовая работа: Методы отсечения

Следуя общей схеме методов отсечения, решим (£, C) – задачу (11, 12, 14), соответствующую (£^ц , C) – задаче (11–14). Пусть x(£, C) – ее оптимальное решение. Проанализируем координаты x(£, C) на целочисленность. Если все координаты вектора x(£, C) целые, то x(£, C) = x(£^ц , C). Если хотя бы одна координата, пусть x_i , будет нецелой, поступим следующим образом.

Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы запишем разложение x_i по небазисным переменным x_i , jÎN

(16)

Так как x_i – нецелая величина, обозначим ближайшее целое число, не превосходящее x_i , через [x_i ] и определим дробную часть: {x_i }= x_i - [x_i ]. Очевидно, (x_i )>0.

Покажем, что по i-и строке симплексной таблицы (£, C) – задачи (в которой стоит нецелая координата решения) можно определить дополнительное линейное ограничение, обладающее свойствами правильности.

Теорема. Пусть - допустимое решение (£^ц , C) – задачи, тогда соотношения

, (17)

, - целое,

определяют правильное отсечение.

Доказательство.

Запишем выражение (16) в виде:

Используя для этого выражения формулу (17), получим:

или

На основании предположений теоремы о допустимости решения

(£^ц , C) – задачи x_i – целое. Величины [x_io ], - целые по определению, следовательно, z_i – тоже целое.

Итак, z_i определенное формулой (17), целое. Докажем что . Доказательство будем вести от противного. Пусть .-

Это значит, что . По определению дробной части . По условию теоремы x – допустимое решение (£^ц , C) – задачи, поэтому . Следовательно,

Тогда должно выполняться:

Итак, из предположения отрицательности z_i , сразу же получаем т.е. z_i – нецелое. Поскольку ранее было показано, что z_i , определенное формулой (17), является целым, то тем самым мы пришли к противоречию. Следовательно, предположение, что z_i < 0, неверное. Теорема доказана.

Следствие. Любое оптимальное решение x(£, C) (£, C) – з адачи, не являющееся допустимым решением (£^ц , C) – задачи, не удовлетворяет условию правильного отсечения (17).

Доказательство. Пусть х (£, C) – оптимальное решение (£, C) – задачи, x_{i 0} – дробное.

Покажем, что х (£, C) не удовлетворяет условию отсечения. Поскольку план оптимален, все небазисные переменные x_i , для jÎN равны нулю. Поэтому . Учитывая это, подставим x_io в формулу (17):

z_i ( x (£, C ))= – { x_{i 0} }+0<0 ,

что противоречит условию неотрицательности z_i . Следствие доказано.