Модель распределения ресурсов
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
| 0 | 4 | 0 | 5 | 5 | 0 | 5,3 | 5,3 | 0 | 5,4 | 5,4 | |||||||
| 1 | 3 | 2,2 | 4,5 | 6,7 | 3,1 | 4,5 | 7,6 | 3,3 | 4,8 | 8,1 | |||||||
| 4 | 2 | 2 | 2,8 | 4,1 | 6,9 | 4,2 | 4,5 | 8,7 | 4,5 | 4,8 | 8,4 | ||||||
| 3 | 1 | 3,1 | 4 | 7,1 | 5,3 | 4,2 | 9,5 | 6,1 | 4,6 | 10,7 | |||||||
| 4 | 0 | 4,3 | 0 | 4,3 | 7,1 | 0 | 7,1 | 7,3 | 0 | 7,3 | |||||||
| 0 | 5 | 0 | 5 | 5 | 0 | 5,3 | 5,3 | ||||||||||
| 1 | 4 | 2,2 | 5,3 | 7,5 | 3,1 | 5,4 | 8,5 | ||||||||||
| 5 | 2 | 3 | 2,8 | 4,5 | 7,3 | 4,2 | 4,8 | 9 | |||||||||
| 3 | 2 | 3,1 | 4,5 | 7,6 | 5,3 | 4,8 | 10,1 | ||||||||||
| 4 | 1 | 4,3 | 4,2 | 8,5 | 7,1 | 4,6 | 11,7 | ||||||||||
| 5 | 0 | 6 | 0 | 6 | 8 | 0 | 8 | ||||||||||
| 0 | 6 | 0 | 5 | 5 | |||||||||||||
| 1 | 5 | 2,2 | 5,3 | 7,5 | |||||||||||||
| 2 | 4 | 2,8 | 5,4 | 8,2 | |||||||||||||
| 6 | 3 | 3 | 3,1 | 4,8 | 7,9 | ||||||||||||
| 4 | 2 | 4,3 | 4,8 | 9,1 | |||||||||||||
| 5 | 1 | 6 | 4,6 | 10,6 | |||||||||||||
| 6 | 0 | 6 | 0 | 6 | |||||||||||||
Таблица 9
|
|
|
|
|
|
|
| 0 | 6 | 0 | 0 | 10,6 | 10,6 |
| 1 | 5 | 1 | 2,1 | 11,7 | 13,8 |
| 2 | 4 | 2 | 3,2 | 10,7 | 13,9 |
| 3 | 3 | 3 | 4,3 | 9,4 | 13,7 |
| 4 | 2 | 4 | 5,1 | 10 | 15,1 |
| 5 | 1 | 5 | 5,1 | 5,4 | 10,5 |
Заключение
В работе было рассмотрено применение динамического программирования для решения задач оптимального распределения ресурсов. Этот метод играет важную роль в решении прикладных задач различных областей науки, что обусловлено его высокой эффективностью. Однако, как и любой математический аппарат, методы динамического программирования нельзя слепо применять для решения той или иной задачи без тщательного предварительного анализа. Практическое применение данных методов требует от исследователя определенного искусства. При этом определяющее значение имеет корректное построение модели и применение подходящих численных процедур.
Список используемых источников
Беллман Р. Динамическое программирование. М.: ИЛ, 1960. 430 с.
Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся ВТУЗов. М.: Наука, 1986. 534 с.
Каллихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. М.: Высшая школа, 1979. 124 с.
Химмельблау Д.М. Прикладное нелинейное программирование. М.: Мир, 1975. 534с.
Приложение 1
Листинг программы для решения задачи оптимального распределения ресурсов с заданными параметрами
#include<iostream.h>
#include<conio.h>
#include<values.h>
//--------------Определяем начальные ресурсы--------------------
const ksi_0 = 6;
//--------------Класс таблицы для вывода------------------------
class Table
{
int tx, ty, c_x, new_y;
public:
Table();
void NewString(double a1, double a2, double a3,
double a4, double a5, double a6, double a7);
void EndOfTable();
};
//-------------Конструктор класса-------------------------------
Table::Table()
{
tx=1, ty=1;
c_x=77;
clrscr();
gotoxy(tx,ty);
cout << "┌";
for (int i=0;i<c_x;i++)
cout << "─";
cout << "┐";
gotoxy(tx+7,ty); cout << "┬";
gotoxy(tx+14,ty); cout << "┬";
gotoxy(tx+19,ty); cout << "┬";
gotoxy(tx+26,ty); cout << "┬";
gotoxy(tx+26,ty); cout << "┬";
gotoxy(tx+40,ty); cout << "┬";
gotoxy(tx+63,ty); cout << "┬";
gotoxy(tx,ty+1); cout << "│";
gotoxy(tx+2,ty+1) ; cout << "ksi1";
gotoxy(tx+7,ty+1); cout << "│";
gotoxy(tx+9,ty+1) ; cout << "eta1";
gotoxy(tx+14,ty+1); cout << "│";
gotoxy(tx+16,ty+1); cout << "x1";
gotoxy(tx+19,ty+1); cout << "│";
gotoxy(tx+21,ty+1); cout << "ksi2";
gotoxy(tx+26,ty+1); cout << "│";
gotoxy(tx+28,ty+1); cout << "f2(x2,eta1)";
gotoxy(tx+40,ty+1); cout << "│";
gotoxy(tx+42,ty+1); cout << "Z3_max(ksi2,eta1+x1)";
gotoxy(tx+63,ty+1); cout << "│";
gotoxy(tx+65,ty+1); cout << "Z2(ksi1,eta1)";
gotoxy(tx+78,ty+1); cout << "│";
gotoxy(tx,ty+2); cout << "├";
for (i=0;i<c_x;i++)
cout << "─";
cout << "┤";
gotoxy(tx+7,ty+2); cout << "┼";
gotoxy(tx+14,ty+2); cout << "┼";
gotoxy(tx+19,ty+2); cout << "┼";
gotoxy(tx+26,ty+2); cout << "┼";
gotoxy(tx+26,ty+2); cout << "┼";
gotoxy(tx+40,ty+2); cout << "┼";
gotoxy(tx+63,ty+2); cout << "┼";
new_y=ty+3;
}
//-------------Определение методов класса таблицы---------------
void Table::NewString(double a1, double a2, double a3,
double a4, double a5, double a6, double a7)
{
gotoxy(tx,new_y);
for(int i=0;i<c_x;i++)
cout << " ";
gotoxy(tx+7,ty+2); cout << "┼";
gotoxy(tx+14,ty+2); cout << "┼";
gotoxy(tx+19,ty+2); cout << "┼";
gotoxy(tx+26,ty+2); cout << "┼";
gotoxy(tx+26,ty+2); cout << "┼";
gotoxy(tx+40,ty+2); cout << "┼";
gotoxy(tx+63,ty+2); cout << "┼";
gotoxy(tx,new_y); cout << "│";
gotoxy(tx+2,new_y) ; cout << a1;
gotoxy(tx+7,new_y); cout << "│";
gotoxy(tx+9,new_y) ; cout << a2;
gotoxy(tx+14,new_y); cout << "│";
gotoxy(tx+16,new_y); cout << a3;
gotoxy(tx+19,new_y); cout << "│";
gotoxy(tx+21,new_y); cout << a4;
gotoxy(tx+26,new_y); cout << "│";
gotoxy(tx+28,new_y); cout << a5;
gotoxy(tx+40,new_y); cout << "│";
gotoxy(tx+42,new_y); cout << a6;
gotoxy(tx+63,new_y); cout << "│";
gotoxy(tx+65,new_y); cout << a7;
gotoxy(tx+78,new_y); cout << "│";
new_y++;
if(new_y>24)
{
gotoxy(tx,new_y); cout << "└";
for (int i=0;i<c_x;i++)
cout << "─";
cout << "┘";
gotoxy(tx+7,ty+2); cout << "┴";
gotoxy(tx+14,ty+2); cout << "┴";
gotoxy(tx+19,ty+2); cout << "┴";
gotoxy(tx+26,ty+2); cout << "┴";
gotoxy(tx+26,ty+2); cout << "┴";
gotoxy(tx+40,ty+2); cout << "┴";
gotoxy(tx+63,ty+2); cout << "┴";
new_y=ty+3;
}
}
void Table::EndOfTable()
{
int i,j;
gotoxy(tx,new_y); cout << "└";
for (i=0;i<c_x;i++)
cout << "─";
cout << "┘";
gotoxy(tx+7,ty+2); cout << "┴";
gotoxy(tx+14,ty+2); cout << "┴";
gotoxy(tx+19,ty+2); cout << "┴";
gotoxy(tx+26,ty+2); cout << "┴";
gotoxy(tx+26,ty+2); cout << "┴";
gotoxy(tx+40,ty+2); cout << "┴";
gotoxy(tx+63,ty+2); cout << "┴";
gotoxy(tx,new_y+1);
for(j=new_y+1;j<26;j++)
{
for(i=tx;i<c_x+4;i++)
{
gotoxy(i,j);
cout << " ";
}
}
gotoxy(1,24);
}
//------------Сообщения-----------------------------------------
void MessageSend(char *MessageForFunc)
{
cout << MessageForFunc << endl;
getch();
}
//----Определения функций, характеризующих выпуск продукции-----
double f3(int arg1, int arg2)
{
if((arg1<0 || arg1>ksi_0) || (arg2<0 || arg2>ksi_0))
return (double)MAXINT;
double Values[ksi_0+1][ksi_0+1]={ 0, 3.4, 3.8, 4.2, 5.0, 5.0, 0,
0, 3.7, 4.1, 4.5, 5.3, 5.3, 0,
0, 3.7, 4.1, 4.5, 5.4, 0, 0,
0, 4.0, 4.5, 4.8, 0, 0, 0,
0, 4.2, 4.8, 0, 0, 0, 0,
0, 4.6, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0 };
return Values[arg2][arg1];
}
double f2(int arg1, int arg2)
{
if((arg1<0 || arg1>ksi_0) || (arg2<0 || arg2>ksi_0))
return (double)MAXINT;
double Values[ksi_0+1][ksi_0+1]={ 0, 2.2, 2.8, 3.1, 4.3, 6, 0,
0, 3.1, 4.2, 5.3, 7.1, 8, 0,
0, 3.3, 4.5, 6.1, 7.3, 0, 0,
0, 3.5, 4.8, 6.7, 0, 0, 0,
0, 5.4, 5.9, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0 };
return Values[arg2][arg1];
}
double f1(int arg1)
{
if(arg1<0 || arg1>ksi_0)
return (double)MAXINT;
double Values[ksi_0+1]={ 0, 2.1, 3.2, 4.3, 5.1, 5.1, 0 };
return Values[arg1];
}
int main(void)
{
clrscr();
Table ob;
int ksi, eta, x, i, j, Indexes[6][5], IndexOfMax = -1, X_opt[3];
double Z_2[6][5], Max=0, MayBeMax=0, Z_max;
for(i=0; i<6; i++)
for(j=0; j<5; j++)
{
Z_2[i][j]=0;
Indexes[i][j]=-1;
}
for(ksi=1; ksi<7; ksi++)
{
for(eta=0; eta<5; eta++)
{
Max = MayBeMax = 0;
for(x=0; x<ksi + 1; x++)
{
if((ksi + eta) > 6)
break;
MayBeMax = f2(x, eta) + f3(ksi - x, x + eta);
if(Max < MayBeMax)
{
Max = MayBeMax;
IndexOfMax = x;
}
ob.NewString(ksi, eta, x, ksi-x, f2(x, eta), f3(ksi - x, x + eta), MayBeMax);
getch();
}
if(Max>0)
{
Z_2[ksi-1][eta] = Max;
Indexes[ksi-1][eta] = IndexOfMax;
}
}
}
ob.EndOfTable();
getch();
Max = MayBeMax = 0;
for(x = 0; x<ksi_0; x++)
{
MayBeMax = f1(x) + Z_2[ksi_0 - 1 - x][x];
if(Max < MayBeMax)
{
Max = MayBeMax;
X_opt[0] = x;
}
}
Z_max = Max;
X_opt[1] = Indexes[ksi_0 - 1 - X_opt[0]][X_opt[0]];
Max = MayBeMax = 0;
for(i=0; i<ksi_0 + 1; i++)
{
MayBeMax = f3(i,X_opt[0]+1);
if(Max < MayBeMax)
{
Max = MayBeMax;
X_opt[2] = i;
}
}
cout << "Максимальный выпуск продукции: " << Z_max << endl;
cout << "достигается при распределении средств: ";
cout << "x1=" << X_opt[0] << ", x2=" << X_opt[1] << ", x3=" << X_opt[2];
getch();
getch();
return 0;
}
Результаты работы программы
┌──┬───┬──┬──┬───────┬────────────┬───────┬
│ksi1│eta1│x1│ksi2│f2(x2,eta1)│Z3_max(ksi2,eta1+x1)│ Z2(ksi1,eta1)│
├───┴───┴──┴──┴───────┴───────────┴───────┴
│ 1 │ 0 │ 0 │ 1 │ 0 │ 3.4 │ 3.4 │
│ 1 │ 0 │ 1 │ 0 │ 2.2 │ 0 │ 2.2 │
│ 1 │ 1 │ 0 │ 1 │ 0 │ 3.7 │ 3.7 │
│ 1 │ 1 │ 1 │ 0 │ 3.1 │ 0 │ 3.1 │
│ 1 │ 2 │ 0 │ 1 │ 0 │ 3.7 │ 3.7 │
│ 1 │ 2 │ 1 │ 0 │ 3.3 │ 0 │ 3.3 │
│ 1 │ 3 │ 0 │ 1 │ 0 │ 4 │ 4 │
│ 1 │ 3 │ 1 │ 0 │ 3.5 │ 0 │ 3.5 │
│ 1 │ 4 │ 0 │ 1 │ 0 │ 4.2 │ 4.2 │
│ 1 │ 4 │ 1 │ 0 │ 5.4 │ 0 │ 5.4 │
│ 2 │ 0 │ 0 │ 2 │ 0 │ 3.8 │ 3.8 │
│ 2 │ 0 │ 1 │ 1 │ 2.2 │ 3.7 │ 5.9 │
│ 2 │ 0 │ 2 │ 0 │ 2.8 │ 0 │ 2.8 │
│ 2 │ 1 │ 0 │ 2