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

Содержание

 

Введение                                                                                      

 

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

2. Построение математической модели                                   

3. Текстовый пример (выбор метода решения)                      

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

5. Кодирование модулей                                                           

Заключение

Литература

Приложение 1. Текст модулей  программы

Приложение 2. Иллюстрационный  плакат

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

 

Математическая модель – описание процесса математическими средствами, в которых отражены основные свойства и количественные соотношения реальной действительности. Предметом исследования математической теории исследования операций являются модели процессов оптимизации. Эти модели порождены задачами на условный экстремум. Важнейшей особенностью таких моделей является многовариантность допустимых решений. Задачей этого предмета является выявление структуры множества допустимых значений и разработка эффективных методов нахождения оптимального решения. Обычный перебор всех допустимых решений для нахождения оптимального варианта не годится, так как число возможных вариантов огромно. Классические методы нахождения экстремума здесь также не годятся: 1. Они требуют существования частных производных во всех областях, где существует экстремум. В то время в задачах оптимизации целевая функция достигает экстремума на границе области, где частные производные не существуют. 2. Классические методы применимы для небольшого числа переменных. 3. Для задач на условный экстремум типичными ограничениями, налагаемыми на переменные, являются неравенства, к которым классические методы не применимы.

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

 

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

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

Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.

Настоящая курсовая работа посвящена наиболее распространенному методу решения задачи линейного программирования – симплекс-методу. Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании.

 Симплексный метод решения задач линейного программирования это вычислительная процедура, основанная на принципе последовательного улучшения плана - перехода от одной граничной точки к другой, для которой значение целевой функции становится больше, если в задаче требуется найти максимум (эти операции фиксируются в симплексной таблице). Если учесть, что различных базисных планов конечное число, то появляется только две возможности.

1. Через конечное число шагов задача будет решена или обнаружится отсутствие ее решения.

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

Этот метод был разработан американским математиком Джорджем Данцигом в 1947 году.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Фабрика производит 3 основных типа товара, изделию I требуется 3 единицы сырья А и 1 единица сырья В, оно приносит прибыль в 6 единиц.

Изделию II требуется 4 единицы сырья А и 3 единицы сырья В, оно приносит прибыль в 3 единицы.

Изделию III требуется 1 единица сырья А и 2 единицы сырья В, оно приносит прибыль в 2 единицы.

Доступны 20 единиц сырья А и 10 единиц сырья В. Найти оптимальный план.

 

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

 

 

	I	II	III	Запас
А	3	4	1	20
В	1	3	2	10
Прибыль	6	3	2

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Построение математической модели

Условие задачи можно представить в виде следующей таблицы

Изделие Сырье	I	II	III	Запас
А	3	4	1	20
В	1	3	2	10
Прибыль	6	3	2

План выпуска продукции  из имеющегося сырья имеет вид:      

                 X₁ X₂ X₃

          

 Ограничения сырья:                         

                 3*X₁ + 4*X₂ + X₃ <= 20                                                

                 X₁ + 3*X₂ + 2*X₃ <= 10                                               

                                               

  Суммарная выручка будет иметь вид:

F(X) = 6*x₁ + 3*x₂ + 2x₃  

 _X1 x₂ x₃ >= 0

Где:

X₁ – количество единиц продукции I вида.

X₂ – количество единиц продукции II вида.

X₃ – количество единиц продукции III вида.

3 * X₁ – сырье А, потраченное на изготовление продукции I в количестве  X₁.

4 * X₂ – сырье А, потраченное на изготовление продукции II в количестве  X₂.

1 * X₃ – сырье А, потраченное на изготовление продукции III в количестве  X₃..

1 * X₁ – сырье B, потраченное на изготовление продукции I в количестве  X₁

3 * X₂ – сырье В, потраченное на изготовление продукции II в количестве  X₂.

2 * X₃ – сырье В, потраченное на изготовление продукции III в количестве  X₃.

Задача основная, но не каноническая, так как система  уравнений не является канонической. Ни в одном из уравнений нет базисного неизвестного.

 

 

 

Получим основную задачу ЛП из общей.

Основной называется задача, если все ограничения системы являются уравнениями (равенствами).

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

И полученная основная задача имеет вид:

 

3*x₁+4*x₂+ x₃ + x₄=20

x₁+3*x₂+ 2*x₃ + x₅=10

X_i 0   i=1, 5

 

F(x) = 6*x₁ + 3*x₂ + 2*x₃ + 0*x₄ + 0*x₅          max

 

 

 

 

 

3. Текстовый пример (выбор метода решения)

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

Симплекс-метод - это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач, математические модели которых представляют собой линейные ограничения с линейными целевыми функциями. Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит в следующем:

- умение находить начальный или опорный базисный план;

- наличие признака оптимальности опорного плана;

- умение переходить к не худшему опорному плану.

 

Канонической называется та основная задача, у которой ограничения имеют каноническую форму, т.е. каждое ограничение содержит базисную переменную с коэффициентом «1» и правые части всех ограничений . Кроме того целевая функция выражена только через свободные неизвестные.

Например:

a₁₁x₁+a₁₂x₂+x₃=b₁

a₂₁x₁+a₂₂x₂+x₄=b₂

X_i ,   i=1, 4

F(x) = с_c - с₁х₁ - с₂х₂

Следовательно, мы имеем  почти каноническую задачу.

Особенность канонической задачи в том, что она всегда имеет начальный базисный план. Для его получения достаточно свободные переменные положить =0  (x₁=x₂=0) тогда x₃=b₁ ; x₄=b₂ , тогда значение целевой функции равно с₀ (F(x)=c₀ ), а x=(0,0,b₁,b₂)

 

Решение канонической задачи ЛП будем находить симплекс-методом, с использованием симплекс-таблицы.

Симплекс-метод – представляет собой вычислительную процедуру, основанную на принципе последовательного улучшения плана - перехода от одной граничной точки к другой, у которой значение целевой функции увеличивается, если в задаче требуется найти максимум (эти операции фиксируются в симплексной таблице).

1. Через конечное число  шагов задача будет решена  или обнаружится отсутствие ее  решения.

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

Последняя строка таблицы  называется индексной и заполняется  коэффициентами целевой функции по следующему правилу:

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

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

В х₀ находятся значения базисных неизвестных. Если в задаче л/п система уравнений каноническая, а коэффициенты целевой функции выражены не только через свободные неизвестные, то такая задача называется “почти канонической”. При внесении такой задачи в симплекс таблицу индексная строка подсчитывается по правилу цен.

Правило цен: в верхней части таблицы выписываются все “цены” т.е. коэффициенты при неизвестных целевой функции, а слева от базисных переменных их цены. Тогда нулевой элемент индексной строки равен сумме произведений цен слева на свободные члены “ + ” цена наверху. Остальные элементы равны сумме произведений цен слева на элементы соответствующего столбца “ - ” цена наверху.

 

Алгоритм симплекс метода.

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);