Разработка программ для решения задач линейного программирования

     министерство  образования и  науки РФ

     Псковский государственный  университет

     Колледж строительства и экономики 
 
 
 
 

     Курсовая  работа по теме 

     «Разработка программ для решения  задач линейного программирования» 

 

     выполнил

     студент гр.420-ПО

                                                                            Лазаревский Сергей Викторович 

     проверил

     Ушарнова  Татьяна Олеговна 
 
 
 
 
 
 

     Псков 2011

 

      

     Содержание

    1. Введение
    2. Спецификация
    3. Техническая задача
    4. Математическая модель
    5. Блок схемы решение задач
    6. Решение задачи вручную
    7. Программный код задачи
    8. Локальная оценка задачи
    9. Заключение

 

     

     Введение

         Главная цель данной курсовой работы, произвести разработку программного продукта  с помощью языков программирования С++, Delphi, Visual Basic. Разработка программного продукта, это процесс создания программы для её продажи. Сложность разработки программного продукта заключается в, удовлетворении требований заказчика к данному программному продукту. Существуют два метода проектирования программного продукта, по степени автоматизации проектных работ и по подходам к организации процесса создания программного продукта. 

 

Спецификация

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

  1. параметры потока (частота обслуживания, вероятность отказа, т.е. вероятность того, что все места в очереди будут заняты).
  2. относительную пропускную способность станции.
  3. абсолютную пропускную способность станции.
  4. вероятность простоя станции.
  5. среднее число машин ожидающих ремонта.
  6. среднее время нахождения в очереди.
  7. среднее время нахождения машины на станции.
 

     Для вычисления характеристики системы обслуживания покупателей в магазине:

  1. среднее время ожидания требования в очереди.
  2. среднее время нахождения покупателей в магазине.
 

     Для  выяснения того, какую продукцию необходимо предприятию производить, что бы получить максимальную прибыль.

 

     

     Техническая задача

     Задача №1.Постановка задачи для вычисления характеристик работы станции технического обслуживания (задача СМО – Марковский процесс системы массового обслуживания). На станцию в случайные моменты времени поступают машины для мелкого ремонта. Станция имеет n технологических линий для ремонта и оборудованную площадку для ожидания, которая вмещает в себя m машин. Требования о ремонте получает отказ, если все места на площадке заняты. На основании статистической обработки наблюдений за потоком машин и временем обслуживания установлено, что поток требований на обслуживание – простейший с интенсивностью λ машин в час, а время обслуживания распределено по показательному закону со средним значением обс.  машины в час.

           Найти характеристики работы  станции:

  1. параметры потока (частота обслуживания, вероятность отказа, т.е. вероятность того, что все места в очереди будут заняты).
  2. относительную пропускную способность станции.
  3. абсолютную пропускную способность станции.
  4. вероятность простоя станции.
  5. среднее число машин ожидающих ремонта.
  6. среднее время нахождения в очереди.
  7. среднее время нахождения машины на станции.
 

     Исходные  данные для решения задачи приведены  в следующей таблице:

Вариант      Λ      n      m       обс.
     6      0,75      2      2      1
 

 

     

     Задача №2.  Постановка задачи для вычисления основных характеристик обслуживания покупателей в магазине (задача СМО). В магазине покупатели появляются в случайные моменты времени, распределённые по экспоненциальному закону с интенсивностью (параметром) λ. В магазине обслуживает один продавец, при этом длительность обслуживания распределена по нормальному закону со средним значением (математическим ожиданием) М дисперсией D. Требуется рассмотреть процесс обслуживания за t часов работы магазина. Найти характеристики системы обслуживания:

  1. среднее время ожидания требования в очереди.
  2. среднее время нахождения покупателей в магазине.

     Исходные  данные для решения задачи приведены  в следующей таблице:

           Вариант      λ      t
           6      12      19
 

     Задача№3. Постановка задачи планирования производства (симплекс метод).

           Предприятие выпускает  десять видов изделий из семи видов  сырья. Запасы сырья по каждому виду определены, а также известно, сколько  и какого сырья нужно для производства каждого изделия. Прибыль от реализации каждого изделия известна. Требуется  составить план выпуска продукции  таким образом, чтобы запасы сырья  были израсходованы полностью, а  суммарная прибыль от её реализации была максимальна.

 

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

          28x1 + 5x2 + 3x3 + 10x4 +18x5 + 14x6 + 12x7 + 5x8 + 9x9 + 18x10 = 1763

         15x1 + 8x2 + 4x3 + 20x4 +15x5 + 16x6 +13x7 + 8x8 + 17x9 + 17x10 =1870

         30x1 + 10x2 + 8x3 +12x4 +13x5 +15x6 + 12x7 + 3x8 + 13x9 + 15x10 =1885

         25x1 +14x2 + 7x3 + 22x4 + 17x5 + 13x6 + 14x7 +5x8 +15x9 + 16x10 =1946

         12x1 + 7x2 + 5x3 +16x4 + 15x5 + 10x6 +16x7 + 4x8 + 12x9 + 18x10 =1591

         6x1 + 3x2 + 9x3 +5x4 +16x5 + 12x6 + 17x7 + 7x8 + 16x9 + 7x10 =1433

         20x1 + 16x2 +6x3 +14x4 + 7x5 + 11x6 + 4x7 + 10x8 + 14x9 + 4x10 =1501

     F(x) = 130x1 + 215x2 + 250x3 + 105x4 + 312x5 + 234x6 + 206x7 + 228x8 + 222x9 + 145x10

 

     

Математическая  модель

     Формулы

A=ƛ*Q 

Q= 

µ= 

Q=  
 
 
 
 
 

 

     

     Блок  схемы решения задачи

     

        

     

     

     

     

     

     

     

       

     

       
 
 

 

     

     

     

     

     

     

     

     

     

       

     

     

       

 

      Расчет вручную

     Задача  №1.Постановка задачи для вычисления характеристик работы станции технического обслуживания (задача СМО – Марковский процесс системы массового обслуживания). На станцию в случайные моменты времени поступают машины для мелкого ремонта. Станция имеет n технологических линий для ремонта и оборудованную площадку для ожидания, которая вмещает в себя m машин. Требования о ремонте получает отказ, если все места на площадке заняты. На основании статистической обработки наблюдений за потоком машин и временем обслуживания установлено, что поток требований на обслуживание – простейший с интенсивностью λ машин в час, а время обслуживания распределено по показательному закону со средним значением обс.  машиныв час.

           Найти характеристики работы  станции:

  • параметры потока (частота обслуживания, вероятность отказа, т.е. вероятность того, что все места в очереди будут заняты).
  • относительную пропускную способность станции.
  • абсолютную пропускную способность станции.
  • вероятность простоя станции.
  • среднее число машин ожидающих ремонта.
  • среднее время нахождения в очереди.
  • среднее время нахождения машины на станции.
     Вариант      Λ      n      m      
обс.
     6      0,75      2      2      1
 

     Λ=0,75 авто/ч

     n=2 линий для ремонта

     tобс=1 ч

     m=2 авто

     µ=1/1=1 авто/ч

     q=1/1=1

     p0=(1+1+12/2!)-1=(2+1/2)-1=(5/2)-1=2/5=0,2 (20%)

     Pотк=(12/2!)*0,2=((1*0,2(/2)=0,1(10%)

     Q=1-0,1=0,9 (90%) (относительная пропускная способность станции обслуживания)

     А=0,9 (абсолютная пропускная способность станции обслуживания)

     =0,9/1=0,9 (среднее число занятых линий для ремонта)

     Ответ: станция обслуживания простаивает 20% времени, вероятность отказа обслуживания заявки 10%  времени, среднее число обслуженных заявок в час 0,9 заявок, что составляет 90%, среднее число занятых линий обслуживания 0.9, т.е каждая из линий обслуживания будет занята обслуживанием заявок в среднем лишь 45%. 

 

 

     Задача 2. Постановка задачи для вычисления основных характеристик обслуживания покупателей в магазине (задача СМО). В магазине покупатели появляются в случайные моменты времени, распределённые по экспоненциальному закону с интенсивностью (параметром) λ. В магазине обслуживает один продавец, при этом длительность обслуживания распределена по нормальному закону со средним значением (математическим ожиданием) М дисперсией D. Требуется рассмотреть процесс обслуживания за t часов работы магазина. Найти характеристики системы обслуживания:

  • среднее время ожидания требования в очереди.
  • среднее время нахождения покупателей в магазине.

     Исходные  данные для решения задачи приведены  в следующей таблице:

           Вариант      λ      t
           6      12      19
 

     Λ=12чел/ч

     tобс=19 ч

     µ=1/19=0,053 чел/ч

     р0=0,053/(0,053+12)=0.004

     q=12/0.053=226.415

     Lсист=226.415/(1-226.415)=-(226.415/225.415)=-1,004*(-1)=1,004

     Lобсл=1-0.004=0,996

     Lоч=1.004-0.996=0.008

     Точ=(1/12)*0.008=0.0007

     Тсист=(1/12)*1.004=0.083

     Ответ: в среднем в магазине находится  1.004 покупателей, из них 0.008 покупателя в очереди

 

     Программныйкодзадачи

     Задача №1 

     unit Unit1; 

     interface 

     uses

       Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

       Dialogs, StdCtrls; 

     type

       TForm1 = class(TForm)

         GroupBox1: TGroupBox;

         Label1: TLabel;

         Edit1: TEdit;

         Label2: TLabel;

         Edit2: TEdit;

         Label3: TLabel;

         Edit3: TEdit;

         Label4: TLabel;

         Edit4: TEdit;

         GroupBox2: TGroupBox;

         Label5: TLabel;

         Edit5: TEdit;

         Label6: TLabel;

         Edit6: TEdit;

         Label7: TLabel;

         Edit7: TEdit;

         Label8: TLabel;

         Edit8: TEdit;

         Label9: TLabel;

         Label10: TLabel;

         Edit9: TEdit;

         Edit10: TEdit;

         Button1: TButton;

         Button2: TButton;

         Button3: TButton;

         Label11: TLabel;

         Edit11: TEdit;

         Label12: TLabel;

         Edit12: TEdit;

         procedure Button2Click(Sender: TObject);

         procedure Button3Click(Sender: TObject);

         procedure Button1Click(Sender: TObject);

       private

         { Private declarations }

       public

         { Public declarations }

       end; 

     var

       Form1: TForm1; 

     implementation 

     {$R *.dfm} 

     procedure TForm1.Button2Click(Sender: TObject);

     begin

     Edit1.Clear;

     Edit2.Clear;

     Edit3.Clear;

     Edit4.Clear;

     Edit5.Clear;

     Edit6.Clear;

     Edit7.Clear;

     Edit8.Clear;

     Edit9.Clear;

     Edit10.Clear;

     Edit11.Clear;

     Edit12.Clear;

     end; 

     procedure TForm1.Button3Click(Sender: TObject);

     begin

     Form1.Hide

     end; 

     procedure TForm1.Button1Click(Sender: TObject);

     var

     n,m,lmbd,och,mf,ku,alf,ochp,kuf,srst,sroch,voch,vst,vrpr,w:real;

     l,x:integer;

     begin

     n:=StrToFloat(Edit1.Text);

     m:=StrToFloat(Edit2.Text);

     lmbd:=StrToFloat(Edit3.Text);

     och:=StrToFloat(Edit4.Text);

     mf:=1/och;

     ku:=mf/(lmbd+mf);

       Edit6.Text:=floattostr(ku); //относительнаяпропускнаяспособность

     alf:=lmbd*ku;

       Edit11.Text:=floattostr(alf); //Абсолютнаяпропускнаяспособность

     ochp:=lmbd/(lmbd+mf);

       Edit5.Text:=floattostr(ochp); //вероятностьотказа

     kuf:=lmbd/mf; //пределная интенсивность

     n:=x;

     for l:=2 to x do

     w:=1;

     w:=w*l;

     vrpr:=1/(1+kuf+Exp(ku*ln(w))/w);

     Edit7.Text:=floattostr(vrpr); //вероятность простоя

     srst:=kuf/(1-kuf);

       Edit12.Text:=floattostr(abs(srst)); //средее число машин на станции

     sroch:=kuf*kuf/(1-kuf);

       Edit8.text:=floattostr(abs(sroch)); //среднее число машин в очереди

     voch:=(1/lmbd)*sroch;

       Edit9.text:=floattostr(abs(voch)); //среднее время нахождения в очереди

     vst:=(1/lmbd)*srst;

       Edit10.text:=floattostr(abs(vst)); //среднее время нахождения на станции

     end;

     end. 

     

 
 

 

     Задача №2 

     Private Sub Command1_Click()

     p = Val(Text1.Text) / Val(Text2.Text)

     ls = p / (1 - p)

     loh = p * p / (1 - p)

     ts = 1 / Val(Text1.Text) * ls

     toh = 1 / Val(Text1.Text) * loh

     Text3.Text = FormatNumber(Abs(ts), 3)

     Text4.Text = FormatNumber(Abs(toh), 3)

     End Sub 
 

     Private Sub Command2_Click()

     Text1.Text = ""

     Text2.Text = ""

     Text3.Text = ""

     Text4.Text = ""

     End Sub

       

Задача №3 

     #include <vcl.h>

     #pragma hdrstop 

     #include "SIM.h"

     #pragma package(smart_init)

     #pragma resource "*.dfm"

     TForm1 *Form1;

     long double A[7][11];

     long double Fx[10]; 

     __fastcall TForm1::TForm1(TComponent* Owner)

         : TForm(Owner)

     {

     }

     void Calcul()

     {

         int i,j,k,l;

         for(i=3;i<10;i++)

             {

                 for(j=0;j<11;j++)

                     {

                         if (i==j) j++;

                         A[i-3][j]=A[i-3][j]/=A[i-3][i];

                     }

                 A[i-3][i]=1;

                 for(k=0;k<7;k++)

                     {

                         if(k==i-3)

                             {

                                 k++;

                                 if(k==7) break;

                             }

                         for(l=0;l<11;l++)

                             {

                                 if(l==i) l++;

                                 A[k][l]-=A[i-3][l]*A[k][i];

                             }

                         A[k][i]=0;

                     }

             }

     } 
 

     void __fastcall TForm1::BitBtn1Click(TObject *Sender)

     {

         A[0][0]=StrToFloat(Edit1->Text);

         A[1][0]=StrToFloat(Edit2->Text);

         A[2][0]=StrToFloat(Edit3->Text);

         A[3][0]=StrToFloat(Edit4->Text);

         A[4][0]=StrToFloat(Edit5->Text);

         A[5][0]=StrToFloat(Edit6->Text);

         A[6][0]=StrToFloat(Edit7->Text);

         A[0][1]=StrToFloat(Edit8->Text);

         A[1][1]=StrToFloat(Edit9->Text);

         A[2][1]=StrToFloat(Edit10->Text);

         A[3][1]=StrToFloat(Edit11->Text);

         A[4][1]=StrToFloat(Edit12->Text);

         A[5][1]=StrToFloat(Edit13->Text);

         A[6][1]=StrToFloat(Edit14->Text);

         A[0][2]=StrToFloat(Edit15->Text);

         A[1][2]=StrToFloat(Edit16->Text);

         A[2][2]=StrToFloat(Edit17->Text);

         A[3][2]=StrToFloat(Edit18->Text);

         A[4][2]=StrToFloat(Edit19->Text);

         A[5][2]=StrToFloat(Edit20->Text);

         A[6][2]=StrToFloat(Edit21->Text);

         A[0][3]=StrToFloat(Edit22->Text);

         A[1][3]=StrToFloat(Edit23->Text);

         A[2][3]=StrToFloat(Edit24->Text);

         A[3][3]=StrToFloat(Edit25->Text);

         A[4][3]=StrToFloat(Edit26->Text);

         A[5][3]=StrToFloat(Edit27->Text);

         A[6][3]=StrToFloat(Edit28->Text);

         A[0][4]=StrToFloat(Edit29->Text);

         A[1][4]=StrToFloat(Edit30->Text);

         A[2][4]=StrToFloat(Edit31->Text);

         A[3][4]=StrToFloat(Edit32->Text);

         A[4][4]=StrToFloat(Edit33->Text);

         A[5][4]=StrToFloat(Edit34->Text);

         A[6][4]=StrToFloat(Edit35->Text);

         A[0][5]=StrToFloat(Edit36->Text);

         A[1][5]=StrToFloat(Edit37->Text);

         A[2][5]=StrToFloat(Edit38->Text);

         A[3][5]=StrToFloat(Edit39->Text);

         A[4][5]=StrToFloat(Edit40->Text);

         A[5][5]=StrToFloat(Edit41->Text);

         A[6][5]=StrToFloat(Edit42->Text);

         A[0][6]=StrToFloat(Edit43->Text);

         A[1][6]=StrToFloat(Edit44->Text);

         A[2][6]=StrToFloat(Edit45->Text);

         A[3][6]=StrToFloat(Edit46->Text);

         A[4][6]=StrToFloat(Edit47->Text);

         A[5][6]=StrToFloat(Edit48->Text);

         A[6][6]=StrToFloat(Edit49->Text);

         A[0][7]=StrToFloat(Edit50->Text);

         A[1][7]=StrToFloat(Edit51->Text);

         A[2][7]=StrToFloat(Edit52->Text);

         A[3][7]=StrToFloat(Edit53->Text);

         A[4][7]=StrToFloat(Edit54->Text);

         A[5][7]=StrToFloat(Edit55->Text);

         A[6][7]=StrToFloat(Edit56->Text);

Разработка программ для решения задач линейного программирования