Программа расчета оптимального распределения ресурсов

1. Записываем данную каноническую задачу минимизации в исходную симплексную таблицу и анализируем знаки индексной строки, не считая элемента C₀
2. Если все элементы индексной строки отрицательные, то базисный план является оптимальным  и задача решена.
3. Если в индексной строке содержится положительный элемент, над которым в таблице нет ни одного положительного, то целевая функция не ограничена сверху на множестве планов задачи и задача решения не имеет.
4. Если над каждым положительным элементом индексной строки имеется в таблице хотя бы один положительный, то следует перейти к новой симплексной таблице содержащей каноническую задачу, базисный план которой будет не хуже предыдущего.
5. Если возникнут ситуации пунктов 2 или 3, то процесс решения задачи завершается, если же возникнет пункт 4, то процесс продолжается.

 

Представление канонической задачи в виде симплекс- таблицы.

Первые строки таблицы, после заголовка, содержат коэффициенты расширенной матрицы канонической системы.

Слева - значения базисных переменных

Последняя строка таблицы  называется индексной, и заполняется  по правилу цен.

 

 

 

 

Таблица 1.

Базис	X0	X1	X2	X3	X4	X5
X4	20	3	4	1	1	0
X5	10	1	3	2	0	1
F	0	-6	-3	-2	0	0

В данном случае неизвестное, вводимое в базис- X₁ , а выводимое из базиса- X₄ . Ключевой будет являться строка, соответствующая ключевому элементу. ( В данном случае 1-я строка)

 

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

1.  В исходной таблице выделяем ключевой столбец, содержащий свободное неизвестное, вводимое в базис.

2.  В ключевом столбце выбираем ключевой элемент являющийся знаменателем ключевого отношения. Ключевой элемент указывает на то неизвестное, которое выводится из базиса.

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

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

 Ключевой  элемент указывает на то неизвестное, которое выводится из базиса.

4.  Строку соответствующую введенному в базис неизвестному называют ключевой. Ее элементы равны частным от деления всех элементов соответствующей строки исходной таблицы на ключевой элемент.

5.  Все остальные элементы новой таблицы вычисляем единообразно по правилу двух перпендикуляров.

 

 

Правило двух перпендикуляров:

Каждый элемент новой таблицы кроме элементов ключевой строки равен разности между соответствующим элементом исходной таблицы и произведением элементов, оказавшихся в основании перпендикуляров, опущенных “мысленно” из данного элемента исходной таблицы на ключевой столбец и ключевую строку.

 

Таблица 2.

Базис	X0	X1	X2	X3	X4	X5
X1	6,65	1	1,35	0,3	0,3	0
X5	3,3	0	1,65	1,7	-0,3	1
F	40	0	5	0	2	0

 

В индексной строке таблицы 2 нет отрицательных элементов. Следовательно, план является оптимальным.

Х*=(6.65, 0, 0, 0, 3.35)

F(x)*=40 ед. – есть максимальное значение целевой функции.

 

 

 

 

 

 

 

 

 

 

4. Разработка проекта  программы

                                             

                                                                   

 

 

Алгоритм 1. Вывод математической модели. 

 

Алгоритм 2. Ввод данных задачи.

 

 

 

Алгоритм 3. Правило цен.

 

 

Алгоритм 4. Осуществление симплекс-метода. 

 

Алгоритм 5. Создание массивов для  симплекс-метода. 

Алгоритм 6. Главная программа.

5.Кодирование на языке С++

Среди множества языков программирования С++ занимает особое место. Он достаточно прост, лаконичен и исключительно эффективен. Язык С++ создан профессионалами для профессионалов и является расширением языка С для поддержки объектно-ориентированной парадигмы программирования.

C++ — чрезвычайно мощный язык, содержащий средства создания эффективных программ практически любого назначения, от низкоуровневых утилит и драйверов до сложных программных комплексов самого различного назначения.

При создании C++ Бьёрн Страуструп стремился сохранить совместимость с языком C. Множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико — отчасти благодаря тому, что синтаксис C++ был основан на синтаксисе C.

Достоинства языка C++

1. Эффективность. Язык спроектирован так, чтобы дать программисту максимальный контроль над всеми аспектами структуры и порядка исполнения программы
2. Имеется возможность работы на низком уровне с памятью, адресами
3. Высокая совместимость с языком C, позволяющая использовать весь существующий C-код
4. Поддерживаются различные стили и технологии программирования, включая традиционное директивное программирование, ООП, обобщённое программирование, метапрограммирование (шаблоны, макросы)
5. Предсказуемое выполнение программ является важным достоинством для построения систем реального времени
6. Пользовательские функции-операторы позволяют кратко и ёмко записывать выражения над пользовательскими типами в естественной алгебраической форме

Недостатки языка С++

1. Многие конструкции С++ позволяют делать то же самое, что и конструкции Си, также присутствующие в С++.
2. Синтаксис, унаследованный от C, неудобен.
3. Язык содержит слишком много возможностей, они могут быть опасны.
4. Наоборот, язык не содержит некоторых возможностей.
5. Языку присущи проблемы производительности.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

Была проведена следующая  работа:  решена симплекс-методом, написана программа по алгоритму симплекс-метода на языке С++,  проведена ее проверка и отладка. Программа работает корректно,  и мы получили желаемый результат.

 

Результатом программы  является окончательный оптимальный  план:

X = (6.65, 0, 0, 0, 3.35)

 

Максимальное значение целевой функции равно:

F(X) = 40

 

Это значит, что для  получения выгоды размером в 40 единиц заводу нужно создать 6,65 единиц продукции I. В этом случае мы получаем максимальную прибыль и не расходуем ресурс завода, превышающий запасы завода. Остаток ресурса B при этом плане равен 3,35, а ресурс А израсходован полностью.

 

 

 

 

 

 

 

 

 

Литература

 

1. Васильев А.Н.

“Самоучитель С++ с  примерами и задачами” 2010г., Санкт-Петербург

2. Лунгу К. Н.

Линейное программирование. Руководство к решению задач. - М.:ФИЗМАТЛИТ, 2005.

3. Собственный конспект по математическим методам

 

 

 

 

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1

Текст модулей программы

 

#include<iostream>

#include<stdio.h>

#include<conio.h>

using namespace std;

int i,j; int m1,m2; int n1,n2; int s; int k; int me;

 

//---------------------------------------------------------------------------

//-------------------------Вывод мат.модели--------------------------

//---------------------------------------------------------------------------

void Model(int a, int b, float **x, int c1, int c2, int c3)

{

cout<<"__________________________________________\n";

x[0][4]=1;

x[1][5]=1;

cout<<"Main model\n";

for(i=0;i<2;i++)

{

for(j=1;j<6;j++)

{

cout<<x[i][j]<<"x"<<j;

if (j<5) cout<<" + ";

}

cout<<" = "<<x[i][0]<<"\n";}

cout<<"F(x)= "<<c1<<"x1 + "<<c2<<"x2 + "<<c3<<"x3 -> max\n";

}

 

 

//----------------------------------------------------------------------------

//-------------------------------Ввод данных----------------------------

//----------------------------------------------------------------------------

void Entershmit(int a, int b, float **x, int c1, int c2, int c3)

{

for(i=0;i<2;i++)

{

for(j=1;j<4;j++)

{

cout<<"Enter koeficient x"<<j<<" "<<i+1<<"-ogo ogr. ";

cin>>x[i][j];

}

cout<<"Enter result "<<i+1<<"-ogo ogr. ";

cin>>x[i][0];

}

cout<<"__________________________________________\n";

cout<<"Math model\n";

for(i=0;i<2;i++)

{

for(j=1;j<4;j++)

{

cout<<x[i][j]<<"x"<<j;

if (j<3) cout<<" + ";

}

cout<<" <= "<<x[i][0]<<"\n";}

cout<<"F(x)= "<<c1<<"x1 + "<<c2<<"x2 + "<<c3<<"x3 -> max\n";

m1=4; m2=5; n1=4; n2=5;

}

 

//----------------------------------------------------------------------------

//------------------------------Правило цен-----------------------------

//----------------------------------------------------------------------------

void Priceshmidt(float **x, int c1, int c2, int c3)

{  getch();

x[2][0]= 0;

x[2][1]=(-1)*c1;

x[2][2]=(-1)*c2;

x[2][3]=(-1)*c3;

x[2][4]= 0;

cout<<"\n";

cout<<"__________________________________________\n";

cout<<"Table 1\n";

cout<<"__________________________________________\n";

cout<<"\n";

for (i=0; i < 3; i++) {

for (j = 0; j < 6; j++) {

printf("%5.1f",x[i][j]);

}

    cout<<"\n";

}

}

 

//---------------------------------------------------------------------------

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

//---------------------------------------------------------------------------

void Perpenshmidt(float **x)

{getch();

  float min; int i; int j;

   min=x[2][1];

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

  

{

if (x[2][i]<=min) {min=x[2][i]; k=i;

   }

   }

   cout<<"\n";

   cout<<"__________________________________________\n";

   cout<<"\n";

   cout<<"Main column: "<<k+1;

   cout<<"\n";

   min=x[0][0]/x[0][k];

s=0;

me=x[0][k];

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

{

if ((x[j][0]/x[j][k])<min) {s=j; min=x[j][0]/x[j][k]; me=x[j][k];

if (j==0) { m1=k; n1=m1; }

}

    }

   cout<<"Main stroke: "<<s+1;

   cout<<"\n";

   cout<<"Main element: "<<me;

   getch();

}

 

  //---------------------------------------------------------------------------

//---------------------------Массив  для симплекс метода-----------

 //---------------------------------------------------------------------------

float** MassiveEffect(float **x)

{  int i; int j; float temp;

float** d=new float*[3];

d[i]=new float[6];

//------Копирование матрицы-------

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

{

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

{

d[i][j]=x[i][j];

}

}

cout<<"\n";

//--Преобразование ключевой  строки---

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

{

d[s][j]=float (d[s][j]/me);

}

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

{

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

{

if ((i!=s) && (j!=m1) && (j!=m2)) {

d[i][j]=x[i][j]-x[i][k]*d[s][j];

}

}

for (i = 0; i < 3; i++) {

  temp=d[i][k];

  for (j = 0; j < 6; j++) {

   if (i!=s) {

   d[i][j]=d[i][j]-temp*d[s][j];

  

   }

}

cout<<"\n";

cout<<"__________________________________________\n";

cout<<"Table 2\n";

cout<<"__________________________________________\n";

cout<<"\n";

for (i=0; i < 3; i++) {

for (j = 0; j < 6; j++) {

printf("%5.1f",d[i][j]);

}

cout<<"\n";

 

   }

    }

cout<<"\n";

cout<<"Targeting function = "<<d[2][0];

return(d);