Оптимальний розподіл поїздів на залізниці

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Черкаський національний університет ім.. Б.Хмельницького

Факультет інформаційних технологій та біомедичної кібернетики

Курсова робота

з дисципліни: «Математичні методи дослідження операцій»

на тему: «Оптимальний розподіл поїздів на залізниці»

по спеціальності: 6.080403 - програмне забезпечення АС

УКР.ЧНУ.00701010-01

Виконав

студентка 4 курсу

групи ЗКС-071

Дейнеко І.В.

Керівник

викл. Корепанов А.С.

Черкаси 2010г.



ВСТУП

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

Характерною особливістю дослідження операцій є системний підхід до поставленої проблеми і аналіз. Системний підхід є головним методологічним принципом дослідження операцій. Він полягає в наступному: будь-яке завдання, яке вирішується, повинне розглядатися з точки зору впливу на критерії функціонування системи в цілому. Для дослідження операцій характерним є те, що при вирішенні кожної проблеми можуть виникати нові завдання. Важливою особливістю дослідження операцій є прагнення знайти оптимальне рішення поставленої задачі (принцип "оптимальності").

Проте на практиці таке рішення знайти неможливе по таких причинах як відсутність методів, що дають можливість знайти глобальне оптимальне рішення задачі; обмеженість існуючих ресурсів (наприклад, обмеженість машинного часу ЕОМ), що робить неможливою реалізацію точних методів оптимізації. Доводиться шукати компроміс між ефективністю рішень і витрат на їх пошук. Одна з найважливіших особливостей дослідження операцій - це те, що воно дає інструмент для пошуку таких компромісів.

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

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

1. ПОСТАНОВКА ТЕХНІЧНОГО ЗАВДАННЯ

1.1 Постановка завдання та вимог до програмного продукту

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

Отже під час виконання даної курсової роботи необхідно розробити і реалізувати програмний продукт, який виконує розрахунок оптимального розподілу механізмів по роботах, причому програма не повинна «прив'язуватись» до певної кількості механізмів та робіт, тобто кількість механізмів та робіт задаються користувачем. Отже, на вхід програми мають подаватись початкові дані: кількість механізмів та кількість робіт. Далі користувач задає ресурси часу механізмів, продуктивність їх роботи, об'єм необхідних робіт та матрицю собівартостей. Програма повинна вивести результат - оптимальний розподіл ресурсів механізмів та загальну собівартість робіт.

Розрахунок результатів зводиться до транспортної задачі.

1.2 Вибір мови програмування та середовища розробки

Для виконання завдання курсової роботи було обрано версію C++Builder 2010, що була випущена у серпні 2009. На сьогоднішній день дана реалізація є однією з найновіших.

Для розробки програмних продуктів використовується мова програмування С++. Мова непогано підходить для реалізації завдання, тому будемо використовувати саме її, оскільки основними її перевагами є швидкість роботи програм на С++ (практично не поступається програмам на С, хоча програмісти отримали в свої руки нові можливості і нові засоби), можливість швидко створити інтуїтивно зрозумілий та зручний у використанні інтерфейс, стабільність роботи та порівняно незначні вимоги до ресурсів, що дозволяє повністю виконати всі завдання відповідно поставлених вимог.

1.3 Аналіз поставленого завдання та огляд існуючих аналогів

Формалізація задачі:

Розглянемо поставлену задачу: Знайти оптимальний розподіл трьох взаємозамінних механізмів по чотирьом видам земельних робіт при заданих ресурсах часу кожного механізму 240,160 і 150 год., продуктивності механізмів 30, 55, 18 м³/год., об'ємі виконуваних робіт 5, 2, 3 і 8 тис. м³ і матриці С собівартостей робіт, грн/м³.

Представимо вихідні дані в вигляді таблиці:

	Робота1	Робота2	Робота3	Робота4	Ресурси часу	Продуктивність
Механізм1	2	1	0,5	1,2	240	33
Механізм 2	0,8	1,2	0,9	0,8	160	55
Механізм 3	0,5	1	0,6	0,9	150	18
Об'єм робіт	5000	2000	3000	8000

Приведемо вихідні дані до класичного вигляду транспортної задачі (перемноживши ресурси часу механізмів і продуктивності їх роботи отримаємо наявний запас робіт в м³):

	В1	В2	В3	В4	Запаси
А1	2	1	0,5	1,2	7200
А2	0,8	1,2	0,9	0,8	8800
А3	0,5	1	0,6	0,9	2700
Потреби	5000	2000	3000	8000

Сумарні потреби: 5000+2000+3000+8000=18000.

Сумарні запаси: 7200+8800+2700=18700.

Сумарні запаси більші за сумарні потреби отже задача відкрита.

Математична модель відкритої задачі

Щоб перетворити дану відкриту задачу в закриту додамо ще один пункт споживання (вартості перевезень в даний пункт споживання рівні 0).

Закрита задача:

	В1	В2	В3	В4	В5	Запаси
А1	2	1	0,5	1,2	0	7200
А2	0,8	1,2	0,9	0,8	0	8800
А3	0,5	1	0,6	0,9	0	2700
Потреби	5000	2000	3000	8000	700



Сумарні потреби: 5000+2000+3000+8000+700=18700.

Сумарні запаси: 7200+8800+2700=18700.

Математична модель закритої задачі

Вирішити подібну задачу можна вручну (що займає немало зусиль та часу), з допомогою математичних пакетів (наприклад MathCad, MathLab), побудувавши математичну модель задачі, з допомогою прикладних програм (призначених саме для розв'язання подібних задач) тощо.



2. РЕАЛІЗАЦІЯ ТЕХНІЧНОГО ЗАВДАННЯ

2.1 Основні алгоритми реалізації програмного продукту

2.1.1 Економічна постановка задачі

Запаси деякого однорідного продукту знаходяться на кількох пунктах постачання (базах) i цей продукт потрібно доставити в кілька пунктів споживання (призначення). Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрібно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільними повністю потреби кожного пункту споживання і при цьому сумарна вартість перевезень була б мінімальною (зворотні перевезення виключаються).

2.1.2 Математична постановка задачі

Нехай:

m - кiлькiсть пунктів постачання (баз);

n - кiлькiсть пунктів споживання;

- кiлькiсть одиниць продукту на i -й базі ();

- потреба j -го пункту споживання () в продукті (в тих же одиницях);

- вартість перевезення одиниці продукту з i -ї бази до j -го пункту споживання;

- кiлькiсть одиниць продукту, яку заплановано перевезти з i-ї бази до j-го пункту споживання.

Тоді вартість перевезення продукту дорівнює



i її потрібно мінімізувати, при цьому на змінні накладаються обмеження:

(, ),

, треба повністю задовольнити потреби j-го пункту споживання

, з i-ї бази треба вивезти весь наявний запас продукту

2.1.3 Умови існування розв'язку транспортної задачі

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

то модель такої транспортної задачі називається замкненою. Якщо ж дана умова не виконується, то модель транспортної задачі називається відкритою.

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

(задача була замкненою).

Розв'язання транспортної задачі можна розділити на два етапи: побудову опорного плану і визначення оптимального плану.

2.1.4 Методи побудови опорного плану

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

Для визначення опорного плана транспортної задачі існує кілька методів. Розглянемо три з них: метод північно-західного кута, метод мінімального елемента і метод подвійних відміток. Сутність цих методів полягає в тому, щоб знайти опорний план за кроків, на кожному з яких в таблиці умови задачі заповнюють одну клітинку, яку називають зайнятою. Заповнення однієї з клітинок забезпечує повністю або задоволення потреб у продукті одного з пунктів споживання (того, в стовпчику якого знаходиться дана клітинка), або вивезення продукту з одного з пунктів постачання (з того, в рядку якого знаходиться дана клітинка).

2.1.5 Алгоритм методу мінімального елемента, побудови опорного плану транспортної задачі

1. З таблиці вартостей вибираємо найменшу вартість, і в клітинку в якій вона знаходиться вписуємо менше з чисел (кількості товару на відповідному пункті постачання і необхідної кількості товару на відповідному пункті споживання).

2. Перевіряються пункти споживання і пункти постачання на наявність пунктів з 0-овими потребами і 0-овими запасами. Такі пункти споживання і постачання далі не розглядаються.

3. Якщо не всі потреби задоволено і не всі пункти постачання не мають запасів повертаємося до пункту 1.

4. Опорний план знайдено.

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

На практиці, найчастіше, використовується метод потенціалів.

2.1.6 Алгоритм методу потенціалів, визначення оптимального плану транспортної задачі

1. Знаходимо опорний план. При цьому число заповнених клітинок повинне бути рівним .

2. Знаходимо потенціали і відповідно пунктів постачання і споживання, розв'язавши систему рівнянь

де - тарифи, що стоять у заповнених клітинках таблиці умов транспортної задачі.

3. Для кожної вільної клітинки визначається число . Якщо серед чисел немає додатних, то переходимо до пункту 6.

4. Серед додатних чисел вибирають максимальне, будують для вільної клітинки, якій воно відповідає, цикл перерахунку і проводять зсув за цим циклом.

5. Отриманий опорний план перевіряють на оптимальність, тобто знову повторюють всі дії, починаючи з пункту 2.

6. Оптимальний план знайдено.

розподіл план транспортний алгоритм механізм



2.2 Реалізація основних алгоритмів мовою С++

2.2.1 Перевірка закритості задачі і перетворення відкритої задачі в закриту

//перевірка закритості задачі

float GetSum=0,NedSum=0;

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

GetSum+=GetMas[i];

}

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

NedSum+=NedMas[j];

}

if (GetSum>NedSum) { //якщо запаси більші за потреби

DoMas(C,row_count,col_count+1); //додаємо ще один пункт споживання

InsertToBeck(NedMas,col_count,GetSum-NedSum);

} else if (GetSum<NedSum) { //якщо запаси менші за потреби

DoMas(C,row_count+1,col_count); //додаємо ще один пункт постачання

InsertToBeck(GetMas,row_count,NedSum-GetSum);

} else {

DoMas(C,row_count,col_count);

}

row_count - кількість пунктів постачання;

col_count - кількість пунктів споживання;

GetSum - загальний об'єм запасів;

GetMas - масив запасів;

NedSum - загальний об'єм потреб;

NedMas - масив потреб;

C - масив собівартостей перевезення одиниці продукту.



2.2.2 Реалізація методу мінімального елемента, побудови опорного плану транспортної задачі

void MinElemMethod(int row_count,int col_count,float **C,float *GetMas,float *NedMas,float **PP){

int min_i,min_j,i,j;

while (MasNotEmpty(GetMas,StartRowCount) && MasNotEmpty(NedMas,StartColCount)){

FindMinPricePoz(StartRowCount,StartColCount,C,PP,min_i,min_j);

if (GetMas[min_i]<NedMas[min_j]) {

PP[min_i][min_j]=GetMas[min_i];

NedMas[min_j]-=GetMas[min_i];

GetMas[min_i]=0;

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

if (PP[min_i][j]==0) {

PP[min_i][j]=-1;

}

}

} else if (GetMas[min_i]>NedMas[min_j]) {

PP[min_i][min_j]=NedMas[min_j];

GetMas[min_i]-=NedMas[min_j];

NedMas[min_j]=0;

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

if (PP[i][min_j]==0) {

PP[i][min_j]=-1;

}

}

} else {

PP[min_i][min_j]=NedMas[min_j];

GetMas[min_i] = 0;

NedMas[min_j] = 0;

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

if (PP[i][min_j]==0) {

PP[i][min_j]=-1;

}

}

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

if (PP[min_i][j]==0) {

PP[min_i][j]=-1;

}

}

}

}

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

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

if (PP[i][j]==-1) {

PP[i][j]=0;

}

}

}

if (MasNotEmpty(GetMas,StartRowCount)) {

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

PP[i][col_count-1]=GetMas[i];

GetMas[i]=0;

}

} else if (MasNotEmpty(NedMas,StartColCount)) {

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

PP[row_count-1][j]=NedMas[j];

NedMas[i]=0;

}

}

}

row_count - кількість пунктів постачання;

col_count - кількість пунктів споживання;

GetSum - загальний об'єм запасів;

GetMas - масив запасів;

NedSum - загальний об'єм потреб;

NedMas - масив потреб;

C - масив собівартостей перевезення одиниці продукту;

PP - опорний план транспортної задачі.

2.2.3 Реалізація методу потенціалів, визначення оптимального плану транспортної задачі

Основний цикл:

while (maxPotential(row_count,col_count,C,Plan,Alfa_i,Alfa_j,//перевірка опримальності плану

calcMasBeta,calcMasAlfa, //функція повертає максимальне Alfa[i][j]

AlfaMas,AlfaCheckMas, //Alfa_i,Alfa_j - координати максимального Alfa[i][j]

BetaMas,BetaCheckMas,k)>0){

BuildCicle(Plan,row_count,col_count,Alfa_i,Alfa_j); //якщо план не оптимальний будуємо цикл

}

row_count - кількість пунктів постачання;

col_count - кількість пунктів споживання;

C - масив собівартостей перевезення одиниці продукту;

Plan - поточний опорний план транспортної задачі;

Alfa_i, Alfa_j - координати елемента з максимальним потенціалом;

calcMasBeta, calcMasAlfa, AlfaMas, AlfaCheckMas, BetaMas, BetaCheckMas - масиви проміжних даних для знаходження потенціалів і відповідно пунктів постачання і споживання та визначення числа для кожної вільної клітинки;

maxPotential - функція, яка повертає максимальне з чисел ;

BuildCicle - функція побудови циклу.

Функція визначення максимального з чисел та координат початкової вершини циклу:

float maxPotential(int row_count,int col_count,float **C,float **Plan, int &alfa_i, int &alfa_j,

int *&calcMasBeta,int *&calcMasAlfa,

float *AlfaMas,bool *AlfaCheckMas,

float *BetaMas,bool *BetaCheckMas,int k){

int i,j,b_c;

float MaxAlfa,CurrAlfa;

//ні бета ні альфа ще не визначені

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

AlfaCheckMas[i]=false;

}

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

BetaCheckMas[i]=false;

}

b_c=0;

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

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

if (Plan[i][j]!=0) {

calcMasBeta[b_c]=j;

calcMasAlfa[b_c]=i;

b_c++;

}

}

}

AlfaMas[row_count-1]=0;

AlfaCheckMas[row_count-1]=true;

//доки є невирахувані змінні вираховуємо їх

while (CheckMasNotChecked(AlfaCheckMas,row_count)||CheckMasNotChecked(BetaCheckMas,col_count)){

for (b_c = 0; b_c < k; b_c++) {

if (BetaCheckMas[calcMasBeta[b_c]] && !(AlfaCheckMas[calcMasAlfa[b_c]])){

AlfaMas[calcMasAlfa[b_c]]=BetaMas[calcMasBeta[b_c]]-C[calcMasAlfa[b_c]][calcMasBeta[b_c]];

AlfaCheckMas[calcMasAlfa[b_c]]=true;

} else if (!(BetaCheckMas[calcMasBeta[b_c]]) && AlfaCheckMas[calcMasAlfa[b_c]]) {

BetaMas[calcMasBeta[b_c]]=AlfaMas[calcMasAlfa[b_c]]+C[calcMasAlfa[b_c]][calcMasBeta[b_c]];

BetaCheckMas[calcMasBeta[b_c]]=true;

}

}

}

//розраховуємо максимальне Alfa[i][j]

b_c=0;

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

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

if (Plan[i][j]==0) {

calcMasBeta[b_c]=j;

calcMasAlfa[b_c]=i;

b_c+=1;

}

}

}

MaxAlfa=BetaMas[calcMasBeta[0]]-AlfaMas[calcMasAlfa[0]]-C[calcMasAlfa[0]][calcMasBeta[0]];

alfa_i=calcMasAlfa[0];

alfa_j=calcMasBeta[0];

for (i = 1; i < b_c; i++) {

CurrAlfa=BetaMas[calcMasBeta[i]]-AlfaMas[calcMasAlfa[i]]-C[calcMasAlfa[i]][calcMasBeta[i]];

if (CurrAlfa>MaxAlfa) {

MaxAlfa=CurrAlfa;

alfa_i=calcMasAlfa[i];

alfa_j=calcMasBeta[i];

}

}

return MaxAlfa;

}

row_count - кількість пунктів постачання;

col_count - кількість пунктів споживання;

C - масив собівартостей перевезення одиниці продукту;

Plan - поточний опорний план транспортної задачі;

Alfa_i, Alfa_j - координати елемента з максимальним потенціалом;

calcMasBeta - масив операндів системи рівнянь ;

calcMasAlfa - масив операндів системи рівнянь ;

AlfaMas - масив потенціалів ;

AlfaCheckMas - індикатор визначеності потенціала ;

BetaMas - масив потенціалів ;

BetaCheckMas - індикатор визначеності потенціала ;

Функція побудови циклу:

void BuildCicle(float **Plan,int row_count,int col_coun,int Alfa_i,int Alfa_j){

int i,j,buf,ai,aj;

bool g;

g=true;

for (i = 1; g && ((Alfa_i+i < row_count)||(Alfa_i-i >= 0)); i++) {

for (j = 0; g && ((Alfa_j+j < col_coun)||(Alfa_j-j >= 0)); j++) {

if (Plan[Alfa_i-i][Alfa_j]!=0 && Plan[Alfa_i][Alfa_j+j]!=0 && Plan[Alfa_i-i][Alfa_j+j]!=0) {//i- j+

ai=0-i;

aj=j;

g=false;

} else if (Plan[Alfa_i+i][Alfa_j]!=0 && Plan[Alfa_i][Alfa_j+j]!=0 && Plan[Alfa_i+i][Alfa_j+j]!=0) {//i+ j+

ai=i;

aj=j;

g=false;

} else if (Plan[Alfa_i+i][Alfa_j]!=0 && Plan[Alfa_i][Alfa_j-j]!=0 && Plan[Alfa_i+i][Alfa_j-j]!=0) {//i+ j-

ai=i;

aj=0-j;

g=false;

} else if (Plan[Alfa_i-i][Alfa_j]!=0 && Plan[Alfa_i][Alfa_j-j]!=0 && Plan[Alfa_i-i][Alfa_j-j]!=0) {//i- j+

ai=0-i;

aj=0-j;

g=false;

}

}

}

if (Plan[Alfa_i+ai][Alfa_j]<Plan[Alfa_i][Alfa_j+aj]) {

buf=Plan[Alfa_i+ai][Alfa_j];

} else {

buf=Plan[Alfa_i][Alfa_j+aj];

}

Plan[Alfa_i][Alfa_j]+=buf;

Plan[Alfa_i+ai][Alfa_j+aj]+=buf;

Plan[Alfa_i][Alfa_j+aj]-=buf;

Plan[Alfa_i+ai][Alfa_j]-=buf;

}

row_count - кількість пунктів постачання;

col_count - кількість пунктів споживання;

Plan - поточний опорний план транспортної задачі;

Alfa_i, Alfa_j - координати елемента з максимальним потенціалом;

ai,aj - зміщення відносно координат елемента з максимальним потенціалом протилежної вершини циклу.



3. ОПИС СТВОРЕНОГО ПРОГРАМНОГО ПРОДУКТУ

3.1 Випробування програмного продукту на тестовому прикладі

Розглянемо приклад наведений у завданні:

Побудуємо початковий опорний план даного прикладу методом мінімального елемента:

Початкова таблиця

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		7200
А2	0,8		1,2		0,9		0,8		0		8800
А3	0,5		1		0,6		0,9		0		2700
Потреби	5000	2000	3000	8000	700

Крок 1

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		4200
						3000
А2	0,8		1,2		0,9		0,8		0		8800
А3	0,5		1		0,6		0,9		0		2700
Потреби	5000	2000	0	8000	700

Крок 2

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		4200
						3000
А2	0,8		1,2		0,9		0,8		0		8800
А3	0,5		1		0,6		0,9		0		0
		2700
Потреби	2300	2000	0	8000	700

Крок 3

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		4200
						3000
А2	0,8		1,2		0,9		0,8		0		6500
		2300
А3	0,5		1		0,6		0,9		0		0
		2700
Потреби	0	2000	0	8000	700

Крок 4

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		4200
						3000
А2	0,8		1,2		0,9		0,8		0		0
		2300						6500
А3	0,5		1		0,6		0,9		0		0
		2700
Потреби	0	2000	0	1500	700

Крок 5

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		2200
				2000		3000
А2	0,8		1,2		0,9		0,8		0		0
		2300						6500
А3	0,5		1		0,6		0,9		0		0
		2700
Потреби	0	0	0	1500	700

Крок 6

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		700
				2000		3000		1500
А2	0,8		1,2		0,9		0,8		0		0
		2300						6500
А3	0,5		1		0,6		0,9		0		0
		2700
Потреби	0	0	0	0	700

Крок 7

	В1	В2	В3	В4	B5	Запаси
А1	2		1		0,5		1,2		0		0
				2000		3000		1500		700
А2	0,8		1,2		0,9		0,8		0		0
		2300						6500
А3	0,5		1		0,6		0,9		0		0
		2700
Потреби	0	0	0	0	0

Застосуємо метод потенціалів до отриманого початкового опорного плану:

	В1	В2	В3	В4	B5
А1	2		1		0,5		1,2		0
				2000		3000		1500		700
А2	0,8		1,2		0,9		0,8		0
		2300						6500
А3	0,5		1		0,6		0,9		0
		2700

;

;

;

;

;

;

;

;

Всі даний опорний план є оптимальним. Оскільки нам необхідно мати приклад для перевірки правильності роботи всіх функцій програмного продукту, а у вказаному в завданні прикладі оптимальний план отримується при побудові опорного плану (без побудови циклу), розглянемо приклад, розв'язання якого вибраними методами вимагає побудови циклу.

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

	Робота1	Робота2	Робота3	Ресурси часу	Продуктивність
Механізм1	7	5	13	23	10
Механізм 2	16	9	10	22	10
Механізм 3	4	12	7	21	10
Об'єм робіт	280	180	120

Приведемо вихідні дані до класичного вигляду транспортної задачі (перемноживши ресурси часу механізмів і продуктивності їх роботи отримаємо наявний запас робіт в м³):

	В1	В2	В3	Запаси
А1	7	5	13	230
А2	16	9	10	220
А3	4	12	7	210
Потреби	280	180	120

Сумарні потреби: 280+180+120=580.

Сумарні запаси: 230+220+210=660.

Сумарні запаси більші за сумарні потреби отже задача відкрита.

Щоб перетворити дану відкриту задачу в закриту додамо ще один пункт споживання (вартості перевезень в даний пункт споживання рівні 0).

Закрита задача:

	В1	В2	В3	B4	Запаси
А1	7	5	13	0	230
А2	16	9	10	0	220
А3	4	12	7	0	210
Потреби	280	180	120	80

Сумарні потреби: 280+180+120+80=660.

Сумарні запаси: 230+220+210=660.

Побудуємо початковий опорний план даного прикладу методом мінімального елемента:

Початкова таблиця

	В1	В2	В3	В4	Запаси
А1	7		5		13		0		230
А2	16		9		10		0		220
А3	4		12		7		0		210
Потреби	280	180	120	80

Крок 1

	В1	В2	В3	В4	Запаси
А1	7		5		13		0		230
А2	16		9		10		0		220
А3	4		12		7		0		0
		210
Потреби	70	180	120	80



Крок 2

	В1	В2	В3	В4	Запаси
А1	7		5		13		0		50
				180
А2	16		9		10		0		220
А3	4		12		7		0		0
		210
Потреби	70	0	120	80

Крок 3

	В1	В2	В3	В4	Запаси
А1	7		5		13		0		0
		50		180
А2	16		9		10		0		220
А3	4		12		7		0		0
		210
Потреби	20	0	120	80

Крок 4

	В1	В2	В3	В4	Запаси
А1	7		5		13		0		0
		50		180
А2	16		9		10		0		100
						120
А3	4		12		7		0		0
		210
Потреби	20	0	0	80

Крок 5

	В1	В2	В3	В4	Запаси
А1	7		5		13		0		0
		50		180
А2	16		9		10		0		80
		20				120
А3	4		12		7		0		0
		210
Потреби	0	0	0	80

Крок 6

	В1	В2	В3	В4	Запаси
А1	7		5		13		0		0
		50		180
А2	16		9		10		0		0
		20				120		80
А3	4		12		7		0		0
		210
Потреби	0	0	0	0

Застосуємо метод потенціалів до отриманого початкового опорного плану:

	В1	В2	В3	В4
А1	7 +		5	-	13		0
		50		180
А2	16		9		10		0
	-	20		+		120		80
А3	4		12		7		0
		210

;

;

;

;

;

;

Максимальним є ;

	В1	В2	В3	В4
А1	7		5		13		0
		70		160
А2	16		9		10		0
				20		120		80
А3	4		12		7		0
		210

;

;

;

;

;

;

Всі даний план є оптимальним.

Загальна ціна = 7*70+5*160+9*20+10*120+4*210 = 3510



Порівняємо обрахунки з проміжними даними програми при виконанні даної задачі:

Рис. 1. Проміжні дані після побудови опорного плану



Рис. 2. Проміжні дані після визначення першого максимального

Аналіз проміжних даних:

С - масив собівартостей.

Масив С не змінюється під час виконання програми і в даному випадку являє собою матрицю

Plan - поточний план.

Plan після побудови опорного плану (див. Рис. 1.) являє собою матрицю



що повністю відповідає даним отриманим на цьому ж етапі при ручному прорахунку задачі.

Plan змінюється тільки під час побудови циклу.

AlfaMas і BetaMas - масиви, які містять, відповідно, і вирахувані з системи рівнянь

.

Під час визначення першого максимального (див. Рис. 2.) дані масиви мали вигляд

Рис. 3. Проміжні дані після побудови першого циклу

MaxAlfa - максимальне під час визначення першого максимального (див. Рис. 2.) мало значення 5.

Значення масивів AlfaMas і BetaMas, а також MaxAlfa є ідентичними відповідним значенням на цьому ж етапі обрахунків, під час ручних обрахунків.

Позиція максимального також відповідає даним ручних обрахунків.

Після побудови першого циклу

Рис. 4.Результат роботи програм при тестових даних

Собівартість робіт при тестових даних становить 3510грн., що дорівнює результуючому значенню при ручному обрахунку.

3.2 Інструкція користувача

Для запуску програмного продукту необхідно двічі натиснути лівою кнопкою миші (далі ЛКМ) на файлі «Project1.exe», після чого на екрані монітора з'явиться вікно програми (див. Рис. 5.).

Рис. 5. Вікно програми після запуску

Головне меню (див. Рис. 6.) програми має таку структуру:

· Параметри;

o Нові;

o Завантажити;

o Зберегти;

· Розрахунок;

· Інформація.

Рис. 6. Головне меню

При натисненні ЛКМ на пункті головного меню «Нові» програма переходить в початковий стан.

При натисненні ЛКМ на пункті головного меню «Завантажити» на екран монітора виводиться форма завантаження параметрів з файлу (див. Рис. 7.).

Рис. 7. Вікно відкриття збережених параметрів

Щоб завантажити параметри з файлу необхідно, за допомогою форми завантаження параметрів, вибрати файл розрахункових даних, і натиснути ЛКМ на кнопці «Відкрити».

При натисненні ЛКМ на пункті головного меню «Зберегти» на екран монітора виводиться форма збереження параметрів в файл (див. Рис. 8.).

Рис. 8. Вікно збереження параметрів

Щоб зберегти параметри в файл необхідно, за допомогою форми збереження параметрів, задати ім'я файлу розрахункових даних та його розташування, після чого натиснути ЛКМ на кнопці «Зберегти».

При натисненні ЛКМ на пункті головного меню «Розрахунок» відбудеться розрахунок оптимального розподілу заданої кількості взаємозамінних механізмів по заданій кількості видів земляних робіт при заданих ресурсах часу та продуктивності кожного механізму.

Результати розрахунків виводяться на вкладниці «Результати».

При натисненні ЛКМ на пункті головного меню «Інформація» на екран монітора виводиться форма з відомостями про даний програмний продукт .

- кнопка додавання механізму (якщо вкладника «Механізми» активна) чи типу роботи (якщо вкладника «Роботи» активна).

- кнопка видалення механізму (якщо вкладника «Механізми» активна) чи типу роботи (якщо вкладника «Роботи» активна).

ВИСНОВКИ

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

Для реалізації даної задачі було використано (реалізовано) алгоритм методу мінімального елемента побудови опорного плану транспортної задачі та алгоритм методу потенціалів, визначення оптимального плану транспортної задачі.

Поставлені завдання є повністю виконаними.

- Користувач самостійно задає кількість механізмів та видів робіт;

- Користувач має доступ лише до тих полів, які він вводить самостійно як початкові дані;

- Результат подається у вигляді таблиці оптимального розподілу ресурсів механізмів.

- Обчислюється загальна собівартість робіт для оптимального розподілу ресурсів механізмів.

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

Програма не потребує спеціально встановленого програмного забезпечення, лише копіювання на комп'ютер користувача. Інтерфейс програми простий, зручний для користувача та інтуїтивно зрозумілий.

Програмний продукт є вільним для копіювання та розповсюдження, тому може широко застосовуватись. Програму протестовано та перевірено.



СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Методы оптимизации в примерах и задачах: Учеб. пособие/А.В.Пантелеев, Т.А.Летова. - 2-е изд., - М.: высш. шк., 2005. - 544 с.

2. Костюкова О.И. Исследование операций: Учеб. Пособие для студ. Спец. 310304 «Информатика» всех форм обучения.- Мн.: БГУИР, 22003. - 94 с.

3. Конюховский П.В. Математические методы исследования операций в экономике - СПб: Питер, 2000. - 208с.

4. Банди Б. Методы оптимизации. Вводный курс: Пер с англ.- М.: Радио и связь, 1998. - 128 с.

5. Грешилов А.А.Прикладные задачи математического программирования: Учебное пособие. - М.: Изд-во МГТУ, 1990. - 189 с.

Размещено на Allbest.ru