Линейное математическое программирование, страница 20

                                   х_j – целые числа

            6.2. Метод отсечения (метод Гомори)

            На первом шаге метода Гомори условия целочисленности не рассматриваются, т.е. решается “обычная” задача Л.П. Если полученный план целочисленный – задача решена. В противном случае к ограничениям задачи добавляется дополнительное ограничение, которое отсекает нецелочисленное решение. Геометрически добавление дополнительного ограничения означает проведение прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) решений некоторую его часть вместе с оптимальной точкой с нецелыми координатами, но не затрагивает точки с целыми координатами (рис. 6.1).

 

Рис.6.1

Пусть задача линейного программирования имеет конечный оптимум и на последнем шаге её решения симплексным методом получены уравнения, выражающие основные переменные х₁; х₂; х_m через не основные переменные х_m+1; х_m+2;…; х_n оптимального решения.

                                                                    (6.2)

Отсюда оптимальное решение задачи Х* = (β₁, β₂, …, β_i,…,β_m, 0, 0, … 0).

Пусть, в оптимальном решении Х* имеются нецелые компоненты. Тогда среди них выбирается не целая компонента с наибольшей целой частью и по нему формируется отсечение.

Пусть, например эта компонента β_i. Отсечение для і-того уравнения будет иметь вид:

{β_i} – {α_im+1}x_m+1-…-{α_in}x_n                                                           (6.3)

В неравенстве присутствует символ { }, который означает дробную часть числа.

Напомним, как выделяется дробная часть числа.

Целой частью числа b называется наибольшее целое число [b], не превышающее b, а дробной частью числа – наименьшее неотрицательное число {b}, равное разности между этим числом и его целой частью.   {b}=b-[b].

Пример         b =   ;                    {b} =  [2] = ;

b = –;  [b] = – 3.  {b} = – – (–3) =  – + 3 =;

Неравенство (6.3) путём введения дополнительной переменной преобразовывается в уравнение

{β_i} – {α_im+1}х_m+1 – … – {α_in }х_n + х_n+1 = 0,                                                    (6.4)

которое включается в систему ограничений на последнем шаге решения задачи без условия целочисленности.

Пример 6.1.

Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден.ед. Оборудование должно быть размещено на площади не превышающей 60м². Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден.ед, требующие производственную площадь 3м² и обеспечивающие производительность за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден.ед, занимающие площадь 5м² и обеспечивающие производительность за смену 3 т зерна.