Симплекс-метод

 

      Ищем  в данной строке (y₂) отрицательный элемент a_ij, если такого элемента нет, то данная система уравнений не совместна. При отсутствии отрицательных элементов в строке вся правая часть соответствующего уравнения может быть только отрицательной, а это противоречит условиям не отрицательных переменных.

      Если  такой элемент есть, то выбираем столбец, в котором он находиться в качестве разрешающего. Далее необходимо найти сам разрешающий элемент. Для рассмотрения берем в данном столбце только те элементы, которые  имеют одинаковый знак со свободным  членом. Находим отношения свободного члена и элемента в той же строке и среди полученных отношений  берем min по модулю, таким образом находиться разрешающая строка. 

Блок –  схема алгоритма.

 
 

Нет

Да

Да

Нет

Начало                                                          
 
 
 
 
 
 
 
 

Ввод  количества ограничений, количества элементов, коэффициентов при Х, целевой  функции.

Ввести  дополнительные переменные и перевести  их в основные переменные.

Базисное  р-ие допустимо? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Целевую функцию нельзя больше увеличить  или уменьшить.

Вывести на экран: кол-во итераций, зн-ие целевой  ф-ции и зн-ия получившихся Х-сов.

Конецwц

Рассмотреть коэффициенты при Х, найти номер  уравнения где он находится и  перевести в основные.

Найти новую  каноническую форму и изменить базис.

Занести промежуточные результаты в массив.

Найти max отриц. коэффициент и номер ур-ия, где он находится и перевести в основные переменные.

Найти новую  каноническую форму и изменить базис.

Промежуточные результаты сохранить в массиве.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Пример  решения задачи с использованием симплекс-метода.

 

      Даны  данные: из которых составляется система  уравнений вида: 

         

      Целевая функция этой системы уравнений  стремится в максимум, и имеет  вид: 

        

      Базисное  решение является допустимым, так  как в правой части неравенств не содержатся отрицательные значения.

      В данной системе 3 – уравнения с 3 – неизвестными, принимают за основные X₄, X_5, X₆ – переменных.

      После этого выражают основные переменные (добавочные) через неосновные, и  находят базисное решение соответствующее.

      Вводим  добавочные неотрицательные переменные (которые еще называют «неосновные»), и сводим систему неравенств к  эквивалентной системе уравнений. 

            

      Так как в полученной системе уравнений  нет отрицательных свободных  членов, то базисное решение является допустимым (0; 0; 0; 60; 100; 36).

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

      Х₂: {60/1; 100/1; 36/1} переводим Х₂ в основные переменные: из третьего уравнения, так как 36/1=36 наименьший коэффициент. 

 

      Подставим в целевую функцию =>Х₂:

     Рассмотрим  полученную систему уравнений и  целевую функцию: 

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

      Переходим к новому базисному решению {0; 5; 0; 0; 20; 50}. Из не основных переменных, входящих в линейную форму (уравнения) с положительным  коэффициентом выбираем ту, которой  соответствует наибольший коэффициент  и переводит ступени в основные.

      Рассмотрим  переменную Х₁ {10; 10; 17}. Выразим из первого уравнения переменную Х₁: 

      

        

      Рассмотрим  полученную систему уравнений и  целевую функцию: 

        

      Если  отыскивается максимум линейной формы, и в ступени выражений нет  основных переменных с положительным  знаком, то критерий оптимальности  выполнен и полученное базисное решение  служит оптимальным (задача решена), но в примере еще есть одна переменная с положительным знаком (Х₃).

      Переходим к новому базисному решению {10; 0; 0; 0; 40; 20}. Из не основных переменных, входящих в линейную форму с положительным  коэффициентом выбираем Х₃, которой соответствует наибольший коэффициент (5) и переводит ступени в основные.

      Рассмотрим  переменную Х₃ {0; 8; 20}. Выразим из второго уравнения переменную Х₃: 

 
 
 

      Рассмотрим  полученную систему уравнений и  целевую функцию: 

        

      Отыскивается  максимум линейной формы, так как  в ступени выражений нет основных переменных с положительным знаком – критерий оптимальности выполнен и полученное базисное решение служит оптимальным (задача решена).

      То  есть при Х₁=10; Х₂=0; X₃=8 максимальное значение функции равно 80 (Lmax=80). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 

Program Simplex_Metod;

Uses crt; 

label

  POVZNAC, NACH; 

var

  Fo, FunctPr, B, H, Hnew, C, Cnew, CPr, Cprnew, FX: array[1..30]       of real;

  X, Xnew: array[1..30,1..30] of real;

  BS, Bvsp,ZNAC: array[1..30]       of string[3];

  MIN, I1, I, J, Kx, Ky, Kit, NachKell, NachY, K_st: integer;

  PriznacY, KLstr, KLst, ErrCode, Dop_X: integer;

  P, P1, Mo, F0, Epsilon, Z, CHLEN: real;

  VSP, S, PrOper: string;

  F: text;

  DPx, DPy, MinMax, Kell, SNom: integer; 

Function MakeIndex (V:integer; S:char): string;

var

  M,Z: string;

begin

  STR(V,M);

  Z:=S+M;

  MakeIndex:=Z;

end; 

Procedure enter;

var

  BUF  :string;

  NEXT :boolean;

begin

  clrscr;

  repeat

    write ('Введите количество уравнений:    ');

    readln (SNom);

    if (SNom > 10) or (SNom <=0) then

    begin

      writeln ('Введите число 1 до 10: ');

      readln;

    end

    else NEXT:=True;

  until NEXT;

  repeat

    NEXT:=False;

    write ('Количество элементов:              ');

    readln (Kell);

    if (Kell > 10) or (Kell <=0) then

    begin

      writeln (Введите число от 1 до 10: ');

      readln;

    end

    else NEXT:=True;

  until NEXT;

  NachKell:=Kell;

  DPx:=Kell+1;

  DPy:=1;

  Epsilon:=0.00001;

  for I:=1 to SNom do

  begin

    for J:=1 to Kell do

    begin

      write  ('Введите ',J,'-й элемент ',I,'-го уравнения:    ');

      readln (Xnew [I,J]);

    end;

    repeat

      write  ('Введите знак:     ');

      readln (ZNAC [I]);

      if (ZNAC [I] <> '>=') and (ZNAC [I] <> '=') and (ZNAC [I] <> '<=') then

      begin

        write ('Неправильно задан знак!');

        readln;

      end;

      if (ZNAC [I] = '=') or (ZNAC [I] = '>=') then PriznacY:=1;

    until (ZNAC [I] = '>=') or (ZNAC [I] = '=') or (ZNAC [I] = '<=');

   write ('Введите свободный член:   ');

    read (B[I]);

  end;

  write ('Введите свободный член целевой функции:    ');

  readln (CHLEN);

  for J:=1 to Kell do

  begin

    write ('Введите ',J,'-й коэффициент целевой функции:  ');

    read (FX[J]);

  end;

  readln;

  write ('Целевая функция стремится к максимуму (Д/Н):   ');

  readln (BUF);

  if (BUF='Д') or (PrOper='Д') then MinMax:=1

                               else MinMax:=2;

  write ('Целочисленное решение (Д/Н):   ');

  readln (PrOper);

  if (PrOper='Д') or (PrOper='Д') then PrOper:='Д'

                                 else PrOper:='Н';

end; 

procedure DOP_PER;

begin

  if ZNAC[I1]='=' then

  begin

    Kell:=Kell+1;