Розв’язання задач дробово-лінійного програмувіння

4.  .

5.  .

6.  .

Розв’язавши задачу симплексним методом, отримаємо такий оптимальний  план: . Враховуючи, що , оптимальним планом початкової задачі буде:

,

причому значення цільової функції (рівень рентабельності виробництва) становить Z = 0,23, тобто 23 %.

 

 ПРАКТИЧНА ЧАСТИНА

 

 

Дана програма призначена для рішення завдання лінійного  програмування симплекс методом.

Для правильного вирішення  система лінійних обмежень повинна  бути приведена до канонічного вигляду.

При запуску програми потрібно ввести кількість рівнянь  обмежень (rows) і найбільший індекс змінної (cols).

Після цього потрібно послідовно ввести коефіцієнти рівнянь (xi) і їх праві частини (b), а також коефіцієнти цільової функції. Якщо якийсь коефіцієнт відсутній, слід ввести нуль.

Для виведення результату потрібно натиснути пробіл. 
Якщо для вирішення завдання були введені додаткові змінні або штучні базиси, то їх потрібно виключити з підсумкового відповіді.

ЗАВДАННЯ. Вирішити завдання дробово-лінійного програмування:

РІШЕННЯ. Зведемо дану задачу до задачі лінійного програмування. Спочатку введемо додаткові змінні, щоб привести задачу до канонічного вигляду:

Позначимо           

Тоді завдання приймає  вигляд:

Вирішимо отриману завдання симплекс-методом. Введемо додаткову  змінну, щоб отримати одиничний базис:

Складаємо симплекс-таблицю.

 

В останній оціночної  рядку є негативні оцінки (дивимось на 
коефіцієнти при М, поки штучний базис не вийде, тому потрібно робити крок симплекс-методом. Вибираємо стовпчик з найменшою оцінкою, а потім дозволяє елемент - по найменшому відношенню вільних членів до коефіцієнтів стовпчика (останній стовпчик). Результат кроку запишемо в таблицю. Аналогічно будемо повторювати кроки.

Отримали рішення

y0 = 1/9

y1 = 2/9

y2 = 2/9

f = 2/3

Тоді, повертаючись до вихідних змінних, отримаємо:

x1 = y1/y0 = 2, x2 = y2/y0 = 2, zmax = 2/3

 

Код

 

#include "Drob.h" //загосовочный файл класса дробей

static int cols;//количество  переменных

static int rows;//количество  уравнений

static int bas[10];//базисные  переменные для каждого уравнения

static CDrob mat[10][30];//Матрица,  содержащая в первой строке  коеффициенты целевой функции, 

//а в последующих коеффициенты уравнеий

             // функция возвпащает номер ведущего столбца

int FindMinus()

{

  CDrob min(0);

int col;

int plus=0;

for (int i=1;i<=cols;i++)

{

if ((mat[rows+1][i+1]>min) || (mat[rows+1][i+1])==min)

plus++;

}

if (plus==cols)

return (0);

for (i=1;i<=cols;i++)

{

if (mat[rows+1][i+1] <= min)

{

min=mat[rows+1][i+1];

col=i;

}

}

return (col);

}

 

//Функция считывает  значения коеффициентов уравнений  в диалоговом режиме

 

void MatInput()

{

for (int i=1;i<=rows;i++)

{

for (int j=2;j<=cols+2;j++)

{

if (j==cols+2)

{

cout << "Enter b"<<i<<" ";

int x;

cin>>x;

mat[i][cols+2]=CDrob(x);

}

else

{

cout << "Enter line "<<i<<" x"<<j-1<<" ";

int x;

cin>>x;

mat[i][j]=CDrob(x);

}

}

}

for (i=1;i<=rows;i++)

mat[i][1]=mat[i][cols+2];

}

 

//Функция считывает  значения коеффициентов целевой  функции в диалоговом режиме

 

void FunctionInput()

{

for(int j=2;j<=cols+1;j++)

{

  cout << "Enter function x"<<j-1<<" ";

  int k;

  cin>>k;

  mat[0][j] = CDrob(k);

}

}

//Функция выводит  результат одной итерации

void Show()

{

int len;

cout<<'\n';

for (int i=0;i<=rows+1;i++)

{

if ((i!=rows+1)&&(i!=0))

cout<<'\n'<<"Basis    "<<bas[i]<<"   ";

else if(i==rows+1)

cout <<'\n'<<"Index string ";

else if(i==0)

cout <<'\n'<<"             ";

for(int j=1;j<=cols+1;j++)

{

if (i==0)

{

if(j!=1)

{

cout.width(5);

cout<<"x"<<j-1;

}

if(j==1)

{

cout.width(6);

cout<<"Plan";

}

}

else

{

len=mat[i][j].GetLength();

cout.width(6-len);

cout << mat[i][j];

}

}

}

}

//Функция расчитывает  значения индексной строки

void SetIS()

{

CDrob Zero(0);

mat[rows+1][1]=Zero;

for(int i=1;i<=rows;i++)

mat[rows+1][1]=mat[rows+1][1] + mat[i][1] * mat[0][bas[i]+1];

for (int j=2;j<=cols+1;j++)

mat[rows+1][j]=Zero;

for (j=2;j<=cols+1;j++)

{

for (int i=1;i<=rows;i++)

{

mat[rows+1][j]=mat[rows+1][j]+mat[i][j]*mat[0][bas[i]+1];

}

mat[rows+1][j]=mat[rows+1][j]-mat[0][j];

}

}

 

//Функция выбирает базисные переменные для каждого уравнения

int SetBas()

{

CDrob Zero(0);

for (int i=1;i<=rows;i++)

{

for (int j=2;j<=cols+1;j++)

{

if (mat[i][j]==1)

{

int null=0;

for (int k=i+1;k<=rows;k++)

{

if (mat[k][j]==Zero)

null++;

}

for (k=i-1;k>=1;k--)

{

if (mat[k][j]==Zero)

null++;

}

if (null==rows-1)

bas[i]=j-1;

}

}

}

for (i=1;i<=rows;i++)

{

if (bas[i] == 0)

return 0;

}

return 1;

}

 

// Функция по  заданному ключевому элементу  преобразует систему

// методом Гаусса-Жордана

void Gauss(int col,int row)

{

for (int i=row+1;i<=rows+1;i++)

{

CDrob min_one(-1);

CDrob mnog=min_one * mat[i][col+1] / mat[row][col+1];

for (int j=1;j<=cols+1;j++)

{

mat[i][j]=mat[i][j]+mat[row][j]*mnog;

}

}

 

for (i=row-1;i>=1;i--)

{

CDrob min_one(-1);

CDrob mnog=min_one * mat[i][col+1] / mat[row][col+1];

for (int j=1;j<=cols+1;j++)

{

mat[i][j]=mat[i][j]+mat[row][j]*mnog;

}

}

CDrob del=mat[row][col+1];

for (int j=1;j<=cols+1;j++)

{

mat[row][j]=mat[row][j]/del;

}

bas[row]=col;

}

// Фукция возвращаяет  номер опорной строки

int FindRow(int col)

{

int k=0;

int row;

CDrob min_row;

for (int i=1;i<=rows;i++)

{

if (mat[i][col+1]>0)

{

k++;

min_row=mat[i][1]/mat[i][col+1];

row = i;

break;

}

}

if (k==0)

{

return 0;

}

for (i=1;i<=rows;i++)

{

if(mat[i][col+1]>0)

{

if (mat[i][1]/mat[i][col+1] < min_row)

{

min_row=mat[i][1]/mat[i][col+1];

row=i;

}

}

}

return row;

}

// Проверка  системы на совместность

void Check_Is_Comp()

{

CDrob Zero(0);

int plus;

for (int j=2;j<=cols+1;j++)

{

if (mat[rows+1][j]<Zero)

{

plus=0;

for (int i=1;i<=rows;i++)

{

if (mat[i][j]>=Zero)

plus++;

}

if (plus==0)

{

cout<<'\n'<<"No optimal plan";

getch();

exit(0);

}

}

}

}

//Функция выводит  результат (оптимальный план и  значение целевой функции)

void ShowResult()

{

CDrob Result[30];

cout<<'\n'<<"x*=(";

for (int i=1;i<=cols;i++)

{

for(int j=1;j<=rows;j++)

{

if (bas[j]==i)

Result[i]=mat[j][1];

}

}

for(i=1;i<=cols;i++)

{

if (i!=cols)

cout<<Result[i]<<',';

else

cout<<Result[i];

}

cout<<')'<<"   f(x*)="<<mat[rows+1][1];

}

// Ввод количества  уравнений и переменных

void SizeInput()

{

system("cls");

cout<<"Enter the number of rows ";

cin>>rows;

cout<<"Enter the number of cols ";

cin>>cols;

}

 

int main()

{

SizeInput();

MatInput();

FunctionInput();

int rez = SetBas(); //если  система уравнений не каноническая, завершаем работу

if (rez == 0)

{

cout<<'\n'<<"System is no canonical";

getch();

exit(0);

}

SetIS();

Show();

for (;;)

{

Check_Is_Comp();

int col=FindMinus();

if (col==0)

{

cout<<'\n'<<'\n'<<"Plan is optimal";

ShowResult();

getch();

exit(0);

}

int row=FindRow(col);

Gauss(col,row);

Show();

}

return 0;

}

 

ВИСНОВОК

 

 

Більшість задач, що досліджуються в математичному програмуванні, зумовлені практичними потребами. Головними показниками економічної ефективності діяльності виробничих систем поряд з абсолютними величинами, такими як прибуток, валова, товарна продукція, є і відносні, наприклад, рівень рентабельності, як відношення прибутку до собівартості застосованих ресурсів чи виробничих фондів тощо.

Отже, якщо як цільову функцію задачі математичного  програмування вибрати максимізацію одного з показників рентабельності, то завжди одержуємо задачу дробово-лінійного програмування. Аналогічні задачі виникають і в інших випадках, коли цільову функцію подають у вигляді відношення величини, яка і в чисельнику, і в знаменнику містить змінні задачі.

Вище наведений прийом розв’язування задачі дробово-лінійного програмування не є оригінальним. Здебільшого, коли розв’язати задачу складно, то її зводять до простішої, для якої існують методи знаходження оптимального плану. Подібний прийом було використано і в задачах цілочислового програмування, і в інших специфічних задачах математичного програмування.

 

 

 

 

 

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

 

 

1. Наконечний С. І., Савіна С. С.   Н-22 Математичне програмування: Навч. посіб. — К.: КНЕУ, 2003. — 452 с.
2. http://fingal.com.ua/content/view/469/76/1/2/
3. Енциклопедія кібернетики в 2 т. / За ред. В. М. Глушкова. — Київ: Головна редакція Української радянської енциклопедії, 1973.