Аналитический метод решения

В качестве аналитического метода наиболее распространен метод Гомори, который используется для случая n независимых переменных.

Алгоритм решения по этому методу складывается из следующих этапов:

1. Решают задачу симплекс-методом без учета условий целочисленности.

2. Пусть на последнем шаге получены уравнения.

 

где x₁ –x_m – базисные переменные,

x_m+1 –x_n – свободные переменные,

x, …, β,...,γ – свободные члены.

Оптимальное решение будет

В оптимальном решении из нецелых решений выбирают решение с наименьшей целой частью (пусть это будет ). Формулируют правильное отсечение по формуле:

{- _m+1} x _m+1+…+{- _n} x _n { },

где { _i} – дробная часть числа _i, например,{3 }= , {-3 }= .

3. Правильное отсечение приводят к каноническому виду введением дополнительной неотрицательной целочисленной переменной х _n+1 по формуле:

{- _m+1}x_m+1+…+{- _n}x_n-x_n+1={ }

и включают новое уравнение в исходную систему ограничений.

4. Решают задачу симплекс-методом. Если не получается целочисленного значения, то вновь возвращаются к пункту 2.

 

1 этап. Исходную ЭММ приводят к каноническому виду посредством введения переменных x₃ и x₄, которые выбираются в качестве базисных. Преобразовывают задачу к задаче на min.

max f ()=2 x ₁+4 x ₂,

2 x ₁+ x ₂+ x ₃= ,

x ₁+3 x ₂+ x ₄=10,

 

x _j 0, x ₁ и x ₂ целые.

min f ()= - 2 x ₁ - 4 x ₂,

f ()+2 x ₁+4 x ₂=0.

Решают пример обычным способом.

Таблица 4.1

Исходная таблица

Базисные переменные	Свободные члены	x 1	x 2	x 3	x 4
x 3	19/3
x 4
f ()

 

Таблица 4.2