Көпөлшемді СП есептерін екіөлшемді түрге келтіру Симплекс әдісі

СП-дың негізгі есебін қарастырайық

Егер жүйе матрицасының рангі rangA = n –2 = m болса, онда СП есебін екі-өлшемдіге келтіруге болады. Бұл жағдайда есептің базистік белгісіздерінің саны (n – 2) , ал еркін белгісізерінің саны екіге тең болады. Егер x₁, x₂, …, x_{n – 2} – базистік белгісіздер болса, онда оларды еркін x_{n – 1} , x_n белгісіздер арқылы былайша өрнектейміз:

СП есебіндегі белгісіздердің теріс еместігін ескере отырып және мақсат f(x) функциядағы базистік x₁, x₂, …, x_{n – 2} белгісіздерді (3.2) жүйе арқылы еркін x_{n -1}, x_n белгісіздерге айырбастасақ, онда екіөл-шемді СП есебін аламыз

Базистік белгісіздерді анықтап, оларды бөліп жазамыз:

x₃ = 14 – 2x₁ – x₂;

x₄ = 8 – x₂;

x₅ = –4 + x₁ + x₂;

x₆ = 6 – 2x₁ + 3x₂;

Мақсат f(x) функцияны еркін x₁, x₂ белгісіздер арқылы өрнектейміз: f(x) = 4x₁ + x₂ .

Нәтижеде сызықтық программалаудың екіөлшемді есебін аламыз:

СП дың есебін геометриялық тәсілмен шешеміз. Ол үшін, шектеулерді теңдеулер жүйесі түрінде жазып, шешімдер жиынын геометриялық түрде анықтаймыз.

x₂ = 8 (2),

x₁ + x₂ = 4 (3),

2x₁ – 3x₂ = 6 (4).

Есепті геометриялық тәсілмен шешіп, мынадай жауапты аламыз.

f_max = f(M₄) = 26; x₁ = 6; x₂ = 2.

f_min = f(M₁) = 4; x₁ = 0; x₂ = 4.

Есептің қалған жауаптарын жүйе бойынша анықтаймыз.

f_max = 26; X_оптим = (x₁, x₂, x₃, x₄, x₅, x₆) = (6, 2, 0, 6, 4, 0);

f_min = 4; X_оптим = (x₁, x₂, x₃, x₄, x₅, x₆) = (0, 4, 10, 4, 0, 18);