Курсовая работа: Применение симплекс-метода

.

.

4/3

.

1/3

Из таблицы видно что минимум функции z равен -7 (при х₁ = 3, х₂ = 2).

Если выбрать переменную х4, то получим то же самое решение.

Для продолжения решения необходимо изменить ограничения, это позволит изменить положение точки А, а так же избежать вырожденности. Для это возьмем некоторую переменную ε – малая величина (т.к. ограничения в точке А не будут выполняться одновременно, см. рисунок 2).

Получим следующее:

2х₁ – х₂ ≤ 4+ ε

x₁ – 2x₂ ≤ 2+ ε² .

В окончательное решение будет входить ε. Затем ε следует обратить в 0.

Если вырожденности нет, то симплекс-методом задача линейного программирования решается за конечное число шагов (при условии что решение существует).

Таким образом, функция z убывает на каждом шаге. Поскольку имеется не более (n/m) допустимых решений, минимум будет равен не более чем за (n/m) итераций.

Листинг программы

{ Reshenie zadachi lin prog-ya modifiz simplex-metodom }

Program Simpl_ST;

uses crt;

label 500, 1800, 1900, 2000, Zikl,{} 2500, 1960;

const M1_K = 30; M2_K = 30; P_K = 30; M_K = 30;

var i, j, k, zz, GC, EC, LC, N, MM, M, MK, N1, P, M1, M2, N0: integer;

A: array[1..M2_K,0..P_K] of integer;

B: array[1..M2_K,0..M1_K] of integer;

BS: array[1..M_K] of integer;

V: array[1..M2_K] of integer;

NB, SL, C: array[1..P_K] of integer;

PB, PA, L, ML, NI, SS: integer;

Zero, NILL, MIN, RT, DF: real;

S, PV, R: integer;