Постановка и геометрическая интерпретация

Многие задачи линейного программирования, возникающие в экономике и производстве, требуют решений, у которых компоненты целочисленны, то есть xjÎZ, j=1, 2, …, n. Например, когда количество выпускаемой продукции измеряется в целых величинах, скажем, поштучно. Так, количество выпускаемых автомобилей, станков не может быть дробным. Раздел линейного программирования, изучающий методы решения таких задач, называется целочисленным линейным программированием, а задачи с таким условием - задачами целочисленного линейного программирования. В математической модели таких задач появляется дополнительное условие: xjÎZ, j=1, 2, …, n:

c1x1+c2x2+…+cnxn®max(min)

Постановка и геометрическая интерпретация - student2.ru (7.1)

В случае, когда задача имеет только две переменные:

c1x1+c2x2 ® max(min)

Постановка и геометрическая интерпретация - student2.ru (7.2)

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

Постановка и геометрическая интерпретация - student2.ru (7.3)

с целочисленными координатами, в которой достигается экстремум целевой функции задачи. Такие задачи геометрически решаются по следующей схеме:

1. Построить многоугольник решений системы (7.1).

2. В многоугольнике решений, полученном в п.1, отметить точки с целочисленными координатами. Получается область допустимых решений (ОДР) задачи (7.2).

3. Построить линии уровня c1x1+c2x2=a целевой функции задачи.

4. В ОДР задачи (7.2), полученной в п.2, выбрать точку, в которой достигается требуемый экстремум.

5. Вычислить значение функции в найденной точке экстремума.

Пример 1. Решить задачу целочисленного программирования геометрическим способом:

2x1+4x2 ® max(min)

Постановка и геометрическая интерпретация - student2.ru

Решение. Действуем по вышеприведённой схеме:

1. Строим многоугольник решений системы (подробности опускаем) (Рис.4)

Постановка и геометрическая интерпретация - student2.ru

Постановка и геометрическая интерпретация - student2.ru

Рис.4

2. В многоугольнике решений, полученном в п.1, отмечаем точки с целочисленными координатами. Это точки (0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3). Таким образом, ОДР задачи - это множество {(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3)} (Рис.5):

Постановка и геометрическая интерпретация - student2.ru

Рис.6

3. Cтроим линии уровня 2x1+4x2=a целевой функции задачи, ориентируясь на вектор Постановка и геометрическая интерпретация - student2.ru =(1, 2) нормали этих линий, коллинеарный вектору 2 Постановка и геометрическая интерпретация - student2.ru =(2, 4) (Рис.7):

Постановка и геометрическая интерпретация - student2.ru

Рис.7

4. В ОДР задачи, полученной в п.2, выбираем точки, в которых достигаются требуемые экстремумы. Это точки (1, 3) - точка максимума, и (0, 0) - точка минимума.

5. Вычислим значение функции в найденных точках экстремума:

Fmax цел.=F(1, 3)=2×1+4×3=14, Fmin цел.=F(0, 0)=2×0+4×0=0.

Ответ: Xmax цел.=(1, 3), Fmax цел.=14; Xmin цел.=(0, 0), Fmin цел.=0.

Метод Гомори

Ясно, что когда задача целочисленного программирования имеет более двух переменных, её необходимо решать аналитическими методами. Одним из таких методов является метод Гомори. Он заключается в следующем.

1. Задача решается как обычная (симплекс-методом или методом искусственного базиса). Если в результате получилось целочисленное решение, то задача решена. В противном случае идём к шагу 1.

2. Допустим, bi - нецелочисленная компонента решения, полученного на 1-м шаге, Постановка и геометрическая интерпретация - student2.ru , Постановка и геометрическая интерпретация - student2.ru , …, Постановка и геометрическая интерпретация - student2.ru - коэффициенты при свободных переменных Постановка и геометрическая интерпретация - student2.ru , Постановка и геометрическая интерпретация - student2.ru , …, Постановка и геометрическая интерпретация - student2.ru соответствующего ограничения, из которых хотя бы один – не целый. Тогда к ограничениям, полученным в последней симплекс-таблице, добавляется дополнительное ограничение { Постановка и геометрическая интерпретация - student2.ru } Постановка и геометрическая интерпретация - student2.ru +{ Постановка и геометрическая интерпретация - student2.ru } Постановка и геометрическая интерпретация - student2.ru +…+{ Постановка и геометрическая интерпретация - student2.ru } Постановка и геометрическая интерпретация - student2.ru ³{bi}, которое после введения очередной дополнительной переменной примет вид

{ Постановка и геометрическая интерпретация - student2.ru } Постановка и геометрическая интерпретация - student2.ru +{ Постановка и геометрическая интерпретация - student2.ru } Постановка и геометрическая интерпретация - student2.ru +…+{ Постановка и геометрическая интерпретация - student2.ru } Постановка и геометрическая интерпретация - student2.ru -xn+1={bi}. (1.1)

Здесь {a} - дробная часть числа a, n - количество переменных задачи в последней симплекс-таблице. Идём к пункту 1.

Если нецелочисленных компонент в оптимальном решении, полученном на первом шаге, несколько, то берём ту, у которой дробная часть наибольшая.

Если bi - дробное, а все коэффициенты Постановка и геометрическая интерпретация - student2.ru , Постановка и геометрическая интерпретация - student2.ru , …, Постановка и геометрическая интерпретация - student2.ru при свободных переменных (в последней симплекс-таблице)являются целыми, то задача целочисленного программирования не имеет решения. Ясно, что задача целочисленного программирования решения не будет иметь, если задача решений не имеет вообще.

Пример 2. Решить задачу целочисленного программирования методом Гомори:

2x1+4x2®max

Постановка и геометрическая интерпретация - student2.ru

Решение. Решая первоначальную задачу, как обычную, получим следующие симплекс-таблицы:

Базис Сб Св. чл. q1 q2  
x1 x2 x3 x4  
x3 Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru  
x4 Постановка и геометрическая интерпретация - student2.ru  
Dj -2 -4 Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru  
x3 Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru    
x2 Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru    
Dj Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru -    
x1 Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru      
x2 Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru      
Dj Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru      
                     

Таким образом, X0= Постановка и геометрическая интерпретация - student2.ru - оптимальное решение, то есть нецелочисленных компонент в оптимальном решении, полученном на первом шаге, два. Найдём их дробные части и сравним:

Постановка и геометрическая интерпретация - student2.ru , Постановка и геометрическая интерпретация - student2.ru и Постановка и геометрическая интерпретация - student2.ru

Поэтому составляем дополнительное ограничение по первой компоненте оптимального решения, которой в последней симплекс-таблице соответствует ограничение Постановка и геометрическая интерпретация - student2.ru . Имеем

Постановка и геометрическая интерпретация - student2.ru , Постановка и геометрическая интерпретация - student2.ru .

Поэтому дополнительное ограничение (1.1) в нашем случае принимает вид

Постановка и геометрическая интерпретация - student2.ru .

Полученную задачу снова решаем как обычную:

Базис Сб Св. чл. q3  
x1 x2 x3 x4 x5
x1 Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru  
x2 Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru  
- - Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru -1 Постановка и геометрическая интерпретация - student2.ru  
x1 -1    
x2 Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru    
x3 Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru - Постановка и геометрическая интерпретация - student2.ru    
Dj Постановка и геометрическая интерпретация - student2.ru Постановка и геометрическая интерпретация - student2.ru    

Получили оптимальное решение X0= Постановка и геометрическая интерпретация - student2.ru данной задачи. Но так как исходная задача зависит только от двух переменных x1 и x2, которые принимают в этом решении целочисленные значения, то задача целочисленного программирования решена.

Ответ: Xцел.=(1, 3), Fmax цел.=14.

Метод Гомори - не единственный аналитический метод решения целочисленной задачи. Разработан целый ряд аналитических методов, отличных от данного. В учебной литературе можно найти, например, метод ветвей и границ.

Транспортная задача

Наши рекомендации