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

                      return false;

}

}

}

}

 

 

return flag;

}

 

 

 

BOOL DataDlg::DestroyWindow()

{

for (int i = 0; i < Statics.GetSize(); i ++ )

{

CStatic * temp = Statics.GetAt(i);

if(temp->m_hWnd != NULL)

{

temp->DestroyWindow();

delete temp;

}  

}

 

for (int i = 0; i< Cells.GetSize(); i ++ )

{

Cell * c = Cells.GetAt(i);

for (int j = 0; j < c -> Edits.GetSize(); j ++ )

{

CEdit * temp = c->Edits.GetAt(j);

if(temp->m_hWnd != NULL)

{

  temp->DestroyWindow();

  delete temp;

    }

}

}

Statics.RemoveAll();

Cells.RemoveAll();

 

return CDialog::DestroyWindow();

}

 

 

void DataDlg::OnBnClickedOk()

{

if ( ! FillMatrix()) return; //если не все поля заполнены, выводим сообщение ошибки и ждем пока заполнит

 

int i = 0;

//

for (; i < Cells.GetSize(); i ++)

{    

  

for (int j = 0; j < Cells.GetAt(i)->Edits.GetSize(); j ++)

{

CString str;

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j);     

 temp->GetWindowText(str);

 

 //заполним матрицу эффективности и вектор дистанций

 int val = StringToInt(str); 

 if (i == 0)

{

distVector.push_back(val);

 continue;

}   

effMatrix[i-1][j] = val;   

 

}

 

} 

if ((distVector[1] - distVector[0])<=0)

{

MessageBox(L"Неправильные данные ресурсов", L"Ошибка", MB_ICONERROR | MB_OK);

return;

}

CDialog::OnOK();

}

 

courseWorkDlg.cpp

//условная оптимизация,  формируем мартицу выхода (максимум  функции цели)

void Ccourse_workDlg::BuildOutMatrix(int **Matrix,std::vector<int> ResVect)

{  

//выделаем память для матрицы

outMatrix = new Item*[QtObj];

for (int i = 0;i < QtObj; i ++) outMatrix[i] = new Item[QtRes];

//инициализируем матрицу

for (int i = 0; i < QtObj; i++)

{

for(int j = 0; j< QtRes; j++)

{

//для первого  предприятия

if (i == 0)

{

Item cell;

cell.Value = Matrix[i][j];

cell.MaxIndex = ResVect[j];

cell.Index = j;

outMatrix[i][j] = cell; 

Flag = true;

continue;

}

 

Item temp;

int step = j;

 

Item maxItem; 

        maxItem.Value = -1;

        maxItem.MaxIndex = -1;

// уравнение Беллмана

for(int k = 0; k < j + 1; k++)

{    

temp.Value = Matrix[i][k] + outMatrix[i-1][step].Value;

temp.MaxIndex = ResVect[k];

temp.Index = j;

--step;

//ищем максимальный  элемент

if(maxItem.Value == -1 || maxItem.Value <= temp.Value) maxItem = temp;

 

}

outMatrix[i][j] = maxItem;

 

}  

 

} 

}

 

void Ccourse_workDlg::FreeMem(int **Matrix)

{

for(int i = 0; i<QtObj;i++) delete [] Matrix[i];

delete [] Matrix;

}

 

void Ccourse_workDlg::OnBnClickedButton1()

{

DataDlg InputData;

int step;

static bool data = false, report = false;  

 

CSpinButtonCtrl* Spin1 = (CSpinButtonCtrl*)GetDlgItem(IDC_SPIN1);

CSpinButtonCtrl* Spin2 = (CSpinButtonCtrl*)GetDlgItem(IDC_SPIN2);

QtObj= Spin1->GetPos();

QtRes= Spin2->GetPos();

 

if (!data)

{

InputData.Row = QtObj;

InputData.Column = QtRes;

//покажем диалог  для ввода данных

if (InputData.DoModal() == IDOK)

    {

//условная оптимизация  (формируем матрицу максимума  функции цели)   

step = InputData.distVector[1] - InputData.distVector[0];

BuildOutMatrix(InputData.effMatrix,InputData.distVector);

//освобождаем память

FreeMem(InputData.effMatrix);

 

//безусловная оптимизация  (формируем вектор результат)

resVector.reserve(QtObj); //резервируем память для вектора результатов

 

int j = InputData.distVector[QtRes-1]/step;

int start_step = InputData.distVector[QtRes-1];

for(int i = QtObj - 1; i >= 0; i--)

{

if(start_step == 0) break;

Result res;

res.Facility = i + 1;

res.Recource = outMatrix[i][j].MaxIndex;

 

int val = outMatrix[i][j].Value;

resVector.push_back(res);

//

 

j = (start_step - res.Recource) / step;

start_step -= res.Recource;

}

 

   data = true;

    }

 

 

}

GetDlgItem(IDC_SPIN1)->EnableWindow(0);

GetDlgItem(IDC_SPIN2)->EnableWindow(0);

m_but.EnableWindow(0);

 

Report reportDlg;

if (data)

{

reportDlg.Count = resVector.size();  

 

for(int i = 0; i< resVector.size(); i++)

{

reportDlg.object[i] = resVector[i].Facility;

reportDlg.resource[i] = resVector[i].Recource;

}

if(reportDlg.DoModal() == IDOK)

{

CDialogEx::OnCancel();

 

}

}

 

}

 

//освобождаем ресурсы

BOOL Ccourse_workDlg::DestroyWindow()

{

DataDlg InputData;

if(Flag)

{

for(int i = 0; i< QtObj; i++) delete [] outMatrix[i];

         delete [] outMatrix;

}

 

 

if (! InputData.distVector.empty()) InputData.distVector.~vector<int>();

if (! resVector.empty()) resVector.~vector<Result>();

 

return CDialogEx::DestroyWindow();

}

 

 

 

 

 

 

Report.cpp

Вывод отчета

BOOL Report::OnInitDialog()

{

CDialog::OnInitDialog();

 

   // object = new int[Count];

//resource = new int [Count];

Ccourse_workDlg workDlg;

 

CSize sz(80,60);

 

CRect WindowRect;

GetWindowRect(&WindowRect);

ScreenToClient(&WindowRect);

 

int TableWidth = sz.cx * 2;

if (TableWidth < WindowRect.Width())

{

//ищем стартовую точку

    int x = (WindowRect.Width() - TableWidth) / 2;

int y = 30;

 

//рисуем шапку

CRect rect1 (CPoint(x,y),sz);

CStatic *st = new CStatic();

st->Create(L"№ объекта", WS_CHILD|WS_VISIBLE|SS_CENTER|WS_BORDER,rect1,this);

Statics.Add(st);

 

CRect rect2 (CPoint(x + sz.cx,y),sz);

CStatic *st1 = new CStatic();

st1->Create(L"Ресурсы", WS_CHILD|WS_VISIBLE|SS_CENTER|WS_BORDER,rect2,this);

Statics.Add(st1);

 

//

y += sz.cy;

CRect rct (CPoint(x,y),sz);

int cnt = Count;

for(int i = 0; i < Count; i ++)

{

CString str;

str.Format(L"%d",object[i]);

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

{

CStatic * stat = new CStatic();

 

 

stat->Create(str,WS_CHILD|WS_VISIBLE|SS_CENTER|WS_BORDER,rct,this);

Statics.Add(stat);

 

rct.MoveToX(x + sz.cx);

str = " ";

str.Format(L"%d",resource[i]);

 

 

}

y += sz.cy;

rct.MoveToXY(CPoint(x,y));

}

 

int a = 0;

}

 

return TRUE;  // return TRUE unless you set the focus to a control

// Исключение: страница  свойств OCX должна возвращать  значение FALSE

}

 

Очистка ресурсов

BOOL Report::DestroyWindow()

{

for (int i = 0; i < Statics.GetSize(); i ++ )

{

CStatic * temp = Statics.GetAt(i);

if(temp->m_hWnd != NULL)

{

temp->DestroyWindow();

delete temp;

}  

}

Statics.RemoveAll();

 

return CDialog::DestroyWindow();

}

 

Заключение

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

F_N(x₀) = (z₁(x₀, u₁) + F_N-1(x₁)), (9)

где F_N(x₀), F_N-1(x₁) – соответственно условно-оптимальные значения функции цели на всех N этапах, N-1 этапах; z_i(x_i-1, u_i) – значение функции цели на i-том этапе.

Последнее выражение называется рекуррентным уравнением Беллмана. Отчетливо просматривается  их рекуррентный характер, т. е. для  нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Кузнецов, А.В. Высшая математика. Математическое программирование / А.В. Кузнецов – Минск: Вышэйшая школа, 1994. – 288с.
2. Кузнецов, Ю.Н. Математическое программирование. / Ю.Н. Кузнецов –Москва: Высшая школа, 1976. –203с.
3. Вентцель, Е.С. Элементы динамического программирования. / Е.С. Вентцель – М.: Наука, 1987. – 198с.
4. Карманов, В.Т. Математическое программирование. / В.Т Карманов. – М.:Наука, 1986. – 253с.
5. Аоки, М. Введение в методы оптимизации. / М. Аоки – М.: Наука, 1977. – 146с.
6. Калихман, И.Л. Динамическое программирование в примерах и задачах / И. Л. Калихман – М.: Высшая школа, 1979. – 125с.
7. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. / Р.Беллман, С.Дрейфус – М.: Наука, 1965. – 234с.