Использование табличного симплекс-метода для решения задач линейного программирования для оптимизации экономических задач 2.doc

часто имеет место в  реальной жизни. Примеры таких задач :

    Пример 1. Рассматривается  работа промышленного  предприятия   под  углом

зрения его рентабельности, причём приводится ряд мер с целью повышения  этой

рентабельности. Показатель эффективности - прибыль ( или средняя  прибыль  ),

приносимая предприятием за хозяйственный год.

    Пример 2.  Группа  истребителей  поднимается  в   воздух  для  перехвата

одиночного самолёта противника. Цель операции -  сбить  самолёт.  Показатель

эффективности - вероятность  поражения цели.

    Пример 3.  Ремонтная   мастерская  занимается  обслуживанием   машин;  её

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

Показатель эффективности - среднее число машин, обслуженных  за день.

    Пример 4.   Группа  радиолокационных станций в определённом  районе ведёт

наблюдение за воздушным  пространством.  Задача  группы  -  обнаружить  любой

самолёт, если он появится в районе. Показатель эффективности  -  вероятность

обнаружения любого самолёта, появившегося в районе.

    Пример 5. Предпринемается  ряд мер по повышения  надёжности  электронной

цифровой вычислительной техники ( ЭЦВТ ). Цель операции - уменьшить  частоту

появления неисправностей ( “сбоев” ) ЭЦВТ, или, что  равносильно,  увеличить

средний  промежуток  времени  между  сдоями  (  “наработку  на   отказ”   ).

Показатель эффективности - среднее время безотказной работы ЭЦВТ.

    Пример 6.  Проводится  борьба  за  экономию  средств  при  производстве

определённого   вида   товара.   Показатель   эффективности   -   количество

сыкономленных средств.

    С помощью анализа  модели на чувствительность  определить  параметр,  от

которого  результат  зависит  больше  и  решить,  каким  способом   возможно

увеличение эффективности  и на сколько, а так же многое другое.

 

 

 

                                   - 23 -

 

 

 

                                 ПРИЛОЖЕНИЕ

 

 

 

                                   - 24 -

 

                                 СОДЕРЖАНИЕ

 

 

    ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .  .

. . . . . . . . . . . . . .    25

1. НАЗНАЧЕНИЕ ПРОГРАММЫ. . . . . . . . . . . . . . . . . . . . . . . .  .  .

. .    26

2. УСЛОВИЯ ПРИМЕНЕНИЯ . . . . . . . . . . . . . . . . . . . . . . . . . .  .

. . . .    26

       1.1 Ограничения  и область применения . . . . . . . . . . . . . . .  .

. . . . .     6

       1.2 Требования  к техническим средствам . . . . . . . . . . . . . .  .

. . . . .     7

3. ВХОДНЫЕ И ВЫХОДНЫЕ  ДАННЫЕ . . . . . . . . . . . . . . . . . .  .  .  .  .

5

4. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ . . . . . . . . . . . . . . . . . . . . . .  .  .

.    11

5. ТЕКСТ ИСХОДНОГО МОДУЛЯ . . . . . . . . . . . . . . . . . . . . . . . .  .

. .     11

6. ОПИСАНИЕ ЛОГИКИ СТРУКТУРНОЙ  СХЕМЫ . . . . . . . . . . . .     11

7. ТЕСТОВЫЙ ПРИМЕР. . . . . . . . . . . . . . . . . . . . . . . . . . . .  .

. . . . . . . .     25

 

 

 

                                   - 25 -

 

                                    ВВЕДЕНИЕ

 

    В данной части  пояснительной записки к курсовой  работе  представлена  и

описана программа, релизующая решение систем линейных  неравенств  табличным

методом.

 

 

 

                                   - 26 -

 

                           1. НАЗНАЧЕНИЕ ПРОГРАММЫ

 

    Программа  предусмотрена   для  решения   систем   линейных   неравенств

табличным  методом,   а   так   же   для   попытки   оптимизации   различных

экономических, социальных и  т. д. проблем.

    Метод, описанный  в программе, может применяться  на  государственных  и

частных предприятиях для  улучшения эффективности производства.

 

 

 

                                   - 27 -

 

                            2. УСЛОВИЯ ПРИМЕНЕНИЯ

 

                        1.1 Ограничения и область применения

 

    Из  программных  средств  требуется   операционная   система   MS   DOS

    версии 5.0, программная  Среда NORTON  COMMANDER,  язык  программирования

Borland Pascal 7.0 . Кроме того  НГМД должен  содержать  файлы   в  директории

KURSOVIK:

    1. Файл входных  данных - KURS97.DAT

    2. Программный  файл - KURS97.EXE

 

 

                       1.2 Требования к техническим средствам

 

    IBM PC или IBM PC - совместимый  компьютер с дисководом 3.25”   ёмкостью

1.2 Мб.

 

 

 

                                   - 28 -

 

                        3. ВХОДНЫЕ И ВЫХОДНЫЕ ДАННЫЕ

 

    Входные и выходные  данные заносятся в файлы KURS97.DAT   и   KURS97.RES

соответственно.   Входные  данные  записываются  в   определённом   порядке.

Выходные данные записываются в виде симплекс-таблиц.

 

 

 

                                   - 29 -

 

                         4. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

 

    Входные данные  вносятся в файл KURS 97.DAT в следующей  очерёдности :

    сначача вводятся  коэффициенты при неизвестных  в целевой функции,  затем

   вводятся  элементы  вектора ограничений,  а потом -  элементы  матрицы

ограничений по столбцам.

    Результаты вычислений  вы найдёте в файле KURS 97.REZ.

 

 

 

                                   - 30 -

 

                          5. ТЕКСТ ИСХОДНОГО МОДУЛЯ

 

    Полный текст программы KURS97.PAS выглядит следующим образом :

    . program Kurs97;

 

    uses crt;

 

    const

      n = 2;

      m = 3;

      Epsilon = 0.000001;

 

    var

      VectorA              : array [1..m, 0..m+n] of real;

      TargetVector         : array [1..m+n]       of real;

      SimplexVector        : array [0..m+n]       of real;

      DigitOfBasisVector   : array [1..m]         of real;

      BasisVector          : array [1..m]         of integer;

 

      IndexOfEnterVector  : integer;

      IndexOfOutputString : integer;

      MinimumBuffer       : real;

 

      key   : char;

      FileOfOutput : text;

 

    { Описание процедур }

 

    procedure ReadDates; { считывание  данных из файла }

    var

      DateFile : text;

 

      procedure ReadDatesTargetVector; { считывание данных целевого вектора

}

      var i : integer;

      begin

        for i:=1 to n do Readln(DateFile, TargetVector[i]);

      end;

 

      procedure ReadDatesVectorA;  {  считывание  вектора  А   и  заполнение

единицами диагонали}

      var i,j : integer;

      begin

        for j:=0 to n do

          for i:=1 to m do

            Readln(DateFile, VectorA[i, j]);

        i:=1;

        for j:=n+1 to n+m do

 

 

 

                                   - 31 -

 

 

        begin

          VectorA[i, j]:=1;

          inc(i)

        end;

      end;

 

      procedure ReadDatesBasisVector;

      var i : integer;

      begin

        for i:=1 to m do BasisVector[i]:=n+i;

      end;

 

    begin

      Assign(DateFile, 'kurs97.dat');

      Reset(DateFile);

      ReadDatesTargetVector;

      ReadDatesVectorA;

      ReadDatesBasisVector;

      Close(DateFile);

    end;

 

    procedure CountSimplexVector; { расчет симплек-вектора }

    var

      i,j      : integer;

      Summa    : real;

      Simplex  : real;

    begin

      SimplexVector[0]:=0;

      for i:=1 to m do

                       SimplexVector[0]:=SimplexVector[0]                 +

DigitOfBasisVector[i]*VectorA[i, 0];

      for j:=1 to m+n do

      begin

        Summa:=0;

        for i:=1 to m do  Summa:=Summa  +  DigitOfBasisVector[i]*VectorA[i,

j];

        SimplexVector[j]:=Summa - TargetVector[j];

        if abs(SimplexVector[j]) <= Epsilon then SimplexVector[j]:=0;

      end;

    end;

 

    function GetEnterVector : integer; { поиск вводимого вектора }

    var

      i   : integer;

      Min : real;

    begin

      GetEnterVector:=1;

      Min:=SimplexVector[1];

      for i:=2 to m+n do

        if Min > SimplexVector[i]

          then

 

 

 

                                   - 32 -

 

        begin

            GetEnterVector:=i;

            Min:=SimplexVector[i];

          end;

    end;

 

    function GetOutputString : integer; { поиск выводимой строки }

    var

      i   : integer;

      Temp : real;

    begin

      GetOutputString:=1;

      if VectorA[1, IndexOfEnterVector] > 0 then  MinimumBuffer:=VectorA[1,

0] / VectorA[1, IndexOfEnterVector];

      for i:=2 to m do

      begin

        Temp:=VectorA[i, 0] / VectorA[i, IndexOfEnterVector];

        if Temp > 0 then

        if MinimumBuffer >= Temp then

        begin

          MinimumBuffer:=Temp;

          GetOutputString:=i;

        end;

      end;

    end;

 

    procedure  ReCountOutputString;  {  пересчет  коэффициентов   выводимой

строки }

    var

      i,j     : integer;

      Buffer  : real;

 

      procedure ReCountDigitOfBasisVector;

      begin

 

DigitOfBasisVector[IndexOfOutputString]:=TargetVector[IndexOfEnterVector];

      end;

 

      procedure ReCountBasisVector;

      begin

        BasisVector[IndexOfOutputString]:=IndexOfEnterVector;

      end;

 

    begin

      ReCountDigitOfBasisVector;

      ReCountBasisVector;

      Buffer:=VectorA[IndexOfOutputString, IndexOfEnterVector];

      for i:=0 to m+n do

      begin

        VectorA[IndexOfOutputString, i]:=VectorA[IndexOfOutputString, i]  /

Buffer;

      end;

    end;

 

 

 

                                   - 33 -

 

 

    procedure ReCountVectorA;

    var i,j  : integer;

    begin

      for j:=0 to m+n do

      begin

        for i:=1 to m do

        begin

          if i <> IndexOfOutputString then

            if j <> IndexOfEnterVector

                then   VectorA[i,   j]:=VectorA[i,    j]    -    VectorA[i,

IndexOfEnterVector]*VectorA[IndexOfOutputString, j];

        end;

      end;

      for i:=1 to m do

        if i <> IndexOfOutputString then VectorA[i, IndexOfEnterVector]:=0;

    end;

 

    function AllIsPositiv : boolean;

    var i : integer;

    begin

      AllIsPositiv:=True;

      for i:=1 to m+n do

        if SimplexVector[i] < 0 then AllIsPositiv:=False;

    end;

 

    function ToStr(const D : real) : string;

    var S : string;

    begin

      str(D:6:2, S);

      ToStr:=' ' + S + ' ';

    end;

 

    procedure WriteMatrixs;

 

      procedure WriteTargetMatrix;

      var i : integer;

      begin

        writeln('                   +---------------------------------------

--------------+');

        write  ('                   ¦ Target ¦');

        for i:=1 to n+m do write(ToStr(TargetVector[i]),'¦');  writeln;

      end;

 

      procedure WriteMatrixA;

      var i,j  : integer;

      begin

        writeln(' +-----------------+--------+--------+--------+--------+---

-----+--------¦');

        writeln(' ¦ Basis  ¦ D.Basis¦   A 0  ¦   A 1  ¦   A 2  ¦   A  3   ¦

A 4  ¦   A 5  ¦');

        writeln(' +--------+--------+--------+--------+--------+--------+---

-----+--------¦');

        for i:=1 to m do

 

 

 

                                   - 34 -

 

 

       begin

                  write('         ¦           A          ',BasisVector[i],'

¦',ToStr(DigitOfBasisVector[i]),'¦');

          for j:=0 to m+n do write(ToStr(VectorA[i, j]),'¦');  writeln;

          if i = m then writeln(' +--------+--------+--------+--------+-----

---+--------+--------+--------¦')

                   else writeln(' +--------+--------+--------+--------+-----

---+--------+--------+--------¦');

        end;

      end;

 

      procedure WriteMatrixSimplex;

      var i : integer;

      begin

        write('          ¦ Simplex¦');

        for i:=0 to m+n do write(ToStr(SimplexVector[i]),'¦'); writeln;

        writeln('          +------------------------------------------------

--------------+');

      end;

 

    begin

      clrscr;

      WriteTargetMatrix;

      WriteMatrixA;

      WriteMatrixSimplex;

    end;

 

    procedure WriteMatrixsInFile;

 

      procedure WriteTargetMatrix;

      var i : integer;

      begin

        writeln(FileOfOutput, '                   +-------------------------

----------------------------+');

        write  (FileOfOutput, '                   ¦ Target ¦');

        for i:=1 to n+m do write(FileOfOutput, ToStr(TargetVector[i]),'¦');

writeln(FileOfOutput);

      end;

 

      procedure WriteMatrixA;

      var i,j  : integer;

      begin

        writeln(FileOfOutput, ' +-----------------+--------+--------+-------

-+--------+--------+--------¦');

        writeln(FileOfOutput, ' ¦ Basis  ¦ D.Basis¦   A 0  ¦   A 1  ¦   A 2

 ¦   A 3  ¦   A 4  ¦   A 5  ¦');

        writeln(FileOfOutput, ' +--------+--------+--------+--------+-------

-+--------+--------+--------¦');

        for i:=1 to m do

        begin

              write(FileOfOutput,     '     ¦      A     ',BasisVector[i],'

¦',ToStr(DigitOfBasisVector[i]),'¦');

          for j:=0 to m+n do write(FileOfOutput, ToStr(VectorA[i, j]),'¦');

writeln(FileOfOutput);

          if i = m then writeln(FileOfOutput, ' +--------+--------+--------

+--------+--------+--------+--------+--------¦')

                   else writeln(FileOfOutput, ' +--------+--------+--------

+--------+--------+--------+--------+--------¦');

        end;

      end;

 

 

 

                                   - 35 -

 

 

      procedure WriteMatrixSimplex;

      var i : integer;

      begin

        write(FileOfOutput, '          ¦ Simplex¦');

            for      i:=0      to      m+n      do      write(FileOfOutput,

ToStr(SimplexVector[i]),'¦'); writeln(FileOfOutput);

        writeln(FileOfOutput, '          +----------------------------------

----------------------------+');

      end;

 

    begin

      clrscr;

      WriteTargetMatrix;

      WriteMatrixA;

      WriteMatrixSimplex;

    end;

 

    { Головная программа  }

    BEGIN

      ClrScr;

      ReadDates;

      Assign(FileOfOutput, 'kurs97.res');

      Rewrite(FileOfOutput);

      CountSimplexVector;

      WriteMatrixs;

      while not AllIsPositiv do

      begin

        IndexOfEnterVector:=GetEnterVector;

        IndexOfOutputString:=GetOutputString;

        ReCountOutputString;

        ReCountVectorA;

        CountSimplexVector;

        WriteMatrixsInFile;

        WriteMatrixs;

        if key=#0 then key:=readkey; key:=#0;

      end;

      Close(FileOfOutput);

    END.

 

 

 

                                   - 36 -

 

                    6. ОПИСАНИЕ ЛОГИКИ СТРУКТУРНОЙ СХЕМЫ

 

    В программе  реализованны следующие процедуры  :

    1. Процедура ReadDates - считывает данные из файла.

    2.  Процедура  ReadDatesTargetVector  -  считывает   коэффициенты   при

неизвестных в целевой  функции из файла.