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

Министерство  образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

ОРЕНБУРГСКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

Математический  факультет

Кафедра математического обеспечения информационных систем 
 
 
 
 
 
 
 

Отчет 

по лабораторной работе № 3

по дисциплине «Методы оптимизации»

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

 
 
 
 
 

Оренбург 2010 

Постановка  задачи: 

Найти максимум функции  

При ограничениях 
 

Дана функция:

 
 
 
 
 
 
 
 
 
 
 
 
 

Графический метод:

Точка максимума  является (0;7)

Значение функции в данной точке = (0*(-1)+1*7) = 7  

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

Приведём данную функцию к каноническому виду 
 

Матрица A = 

Б={} 
 
 
 
 

0 x3  2    1.00  -1.00   1.00   0.00   2.00

0 x4  7    2.00   1.00   0.00   1.00   2.00

--------------------------------------------

           -1.00   1.00   0.00   0.00

    -2.00  -1.00   1.00  -1.00  -0.00

--------------------------------------------

-1 x1 -2   -1.00   1.00  -1.00  -0.00  -2.00

0 x4  9    3.00   0.00   1.00   1.00  -2.00

--------------------------------------------

           -2.00   2.00  -1.00   0.00

    -2.00  -1.00   1.00  -1.00  -0.00

--------------------------------------------

1 x2 -2   -1.00   1.00  -1.00  -0.00   9.00

0 x4  9    3.00   0.00   1.00   1.00   9.00

--------------------------------------------

            0.00   0.00   1.00   0.00

     9.00   3.00   0.00   1.00   1.00

-------------------------------------------- 
 

1 x2  7    2.00   1.00   0.00   1.00

0 x3  9    3.00   0.00   1.00   1.00

           -3.00   0.00   0.00  -1.00

        

б.п. {0 7 9 0 }

(.)max = (0;7)

function(.)max = 7 
 
 
 
 
 
 
 
 
 
 
 
 
 

Код программы:

// lab3.cpp : Defines the entry point for the console application.

// 

#include "stdafx.h"

#include <iostream>

using namespace std;

const int n=4;

const int nn=2;

double A[2][n];

double A1[2][n];

int bp[2];

double Y0[2];

double mini;

double delta[n];

double e[n+1];

double C[4];

int bp_[n]; 

int maxi(double mas[n])

{

      double mm=-1000;

      int no;

      for (int i=0;i<n;i++)

      {

            if (mas[i]>mm) {mm=mas[i];no=i;}

      }

      return no;

} 

bool exitt(double mas[n])

{

      for (int i=0;i<n;i++)

      {

            if (mas[i]>0.001) {return 0;}

      }

      return 1;

} 

bool neogr(double mas[nn][n])

{

      int k=0;

      for (int i=0;i<nn;i++)

      {

            k=0;

            for (int j=0;j<n;j++)

            {

                  if (mas[i][j]<1) {k++;}

            }

            if (k==n) return true;

      }

      return false;

}

int bp_free()

{

      for (int i=0;i<n;i++)

      {

            if (bp_[i]==0) return i;

      }

      cout << "konec!!!"<<endl;

      for (int i=0;i<n;i++)

      {bp_[i]=0;}

      return 0;

} 

void update(double mas[nn][n],double mas1[nn][n])

{

      for (int i=0;i<nn;i++)

      for (int j=0;j<n;j++)

      {mas[i][j]=mas1[i][j];}

}

int main()

{

      freopen("input.txt","r",stdin);

      freopen("output.txt","w",stdout); 

      cin >> C[0];

      cin >> C[1];

      C[2]=0;

      C[3]=0; 

      // считали матрицу А

      for (int i=0;i<nn;i++)

      {

            for (int j=0;j<n;j++)

            {cin >> A[i][j];bp_[j]=0;}

            cin >> Y0[i];

      }

      bp[0]=3;

      bp_[2]=0; // помечаем что в 3 были

      bp[1]=4;

      bp_[3]=0; // помечаем что в 4 были 

      int nomer=0;

      // находим минимум

      if (((Y0[0]/A[0][0])>0)&&((Y0[0]/A[0][0])<(Y0[1]/A[1][0]))) {mini=(Y0[0]/A[0][0]);}

      else {mini=(Y0[1]/A[1][0]);nomer=1;} 

      // находим дельта

      for (int i=0;i<n;i++)

      {delta[i]=C[i]-(C[bp[0]-1]*A[0][i]+C[bp[1]-1]*A[1][i]);} 

      int s=maxi(delta); // номер ведущего столбца

      double v_e=A[nomer][s];

      // вычмсление строки ебсилон

      e[0]=Y0[nomer]/v_e; 

      for (int i=0;i<n;i++)

      {

            e[i+1]=A[nomer][i]/v_e;

      }

      // вывод

      for (int i=0;i<nn;i++)

      {

            printf("%2.0f",C[bp[i]-1]);

            cout<<" "<<"x";

            printf("%1i",bp[i]);

            cout<<" ";

            printf("%2.0f",Y0[i]);

            cout<<" ";  

            for (int j=0;j<n;j++)

            printf("%7.2f",A[i][j]);

            printf("%7.2f",mini);

            cout << endl;

      }

      cout<<"--------------------"<<endl;

      cout << "         ";

      for (int j=0;j<n;j++) 

      printf("%7.2f",delta[j]); 

      cout << endl<< "  ";

      for (int j=0;j<n+1;j++)  

      printf("%7.2f",e[j]);