Решение транспортных задач венгерским методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?оритм венгреского метода был реализован программно в среде C++ Builder. С помощью разработанной программы был проведен анализ модели на чувствительность. В ходе этого анализа выяснилось, что затраты на перевозку товара, которые оптимально составили 87974 евро в месяц, можно уменьшить на 3520 евро, если в самом затратном пункте производства уменьшить объем выпускаемого продукта на 2200 кг, а в наименее затратном настолько же увеличить. При этом общая стоимость транспортных расходов составит 84454 евро в месяц.
Реализованная программа имеет удобный и простой интерфейс, наглядно представляет решение задачи венгерским методом и может быть использована для дальнейших расчетов стоимостей перевозок и построения оптимальных планов.
Библиографический список
1. Балашевич В.А. Основы математического программирования [Текст] / В.А. Балашевич. - Минск.: Высш школа, 1985. - 174с.
. Зайченко Ю.П. Исследование операций [Текст] / Ю.П. Зайченко - М.: Высш. школа, 1979. - 156с.
. Карлусов В.Ю. Методические указания к практическим занятиям по диiиплине Исследование операций и методы оптимизации для студентов специальности 7.080401 - Компьютеризированные системы обработки информации и управления [Текст] / В.Ю. Карлусов, Л.П. Старобинская - Севастополь: Изд-во СевГТУ, 1997. - 26с.
. Карлусов В.Ю. Методические указания к вы-полнению лабораторных и контрольных работ для студентов дневной и заочной форм обучения специальности 7.080401 - Информационные управляющие системы и технологии [Текст] / В.Ю. Карлусов, Л.П. Старобинская - Севастополь: Изд-во СевГТУ, 1998. - 61с.
ПРИЛОЖЕНИЕ А
Описание интерфейса программы
Интерфейс программы очень простой и удобный для пользования. На рисунках 1 и 2 преведенны элементы интерфейса до решения поставленной задачи и после соотвественно.
Рисунок 1 - Интерфейс программы до выполнения
Весь интерфейс состоит из 9 кнопок. Стрелочки предназначены для увеличения размерности исходной матрицы. Кнопки Файл->Cохранить и Файл->Oткрыть сохраняют и загружают таблицы соответственно. Кнопка Файл->Новый очищает матрицы стоимостей, потребления и запаса.
Рисунок 2 - Интерфейс программы после выполнения
После нажатия кнопки Решить появляются вкладки в которых отображается каждый этап (шаг) решения транспортной задачи.
Приложение Б
Текст программы
//---------------------------------------------------------------------------
#include
#include
#include
#include
#pragma hdrstop
#include "Main.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma link "Spin"
#pragma link "IWImageList"
#pragma link "cspin"
#pragma resource "*.dfm"*Form1;MyFName="";Cn,Cm;**C;**C0;**CS;Pm;*P;Zn;*Z;Dn,Dm;**D;OPrz=0;OPtr=0;Xn,Xm;**X;Nn,Nm;**N;posl;pstr;*Sheet;*Grid;*GrX;* LabelC;* LabelX;Fn;*F;Gm;*G;*GridF;L;Lstr;Cep[50][7][8];nomer=0;NKor=0;NIter=0;
//Конструктор формы
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//Вывод подсказки//При создании формы
void __fastcall TForm1::FormCreate(TObject *Sender)
{
StoimPer->Cells[0][0]="Ai";
for (int j=1; jColCount; j++)
{
StoimPer->Cells[j][0]="B"+IntToStr(j);
}
for (int i=1;iRowCount; i++)
{
StoimPer->Cells[0][i]="A"+IntToStr(i);
}
Potr->Cells[0][0]="Потр";
Zapas->Cells[0][0]="Запас";
}
//При вводе в ячейку таблицы__fastcall TForm1::TabKeyPress(TObject *Sender, wchar_t &Key)
{
Set Dig;
TStringGrid* Tab=(TStringGrid *)Sender;
Dig<<'0'<<'1'<<'2'<<'3'<<'4'<<'5'<<'6'<<'7'<<'8'<<'9'<<'\b'<<','<<'.'<<VK_RETURN;
if(!Dig.Contains(Key)){
Key=0;
Beep();
}
}
//При нажатии клавиши "Решить"
void __fastcall TForm1::ReshutClick(TObject *Sender)
{
nomer=0;
//Создание матрицы C
Cn=StoimPer->RowCount-1;
Cm=StoimPer->ColCount-1;
for(int i=0;i<50;i++)
for(int j=0;j<Cn;j++)
for(int z=0;z<Cm;z++)
Cep[i][j][z]=0;
C=new int*[Cn];
C0=new int*[Cn];
CS=new int*[Cn];
for (int i=0; i<Cn; i++){
C[i]=new int[Cm];
C0[i]=new int[Cm];
CS[i]=new int[Cm];
}
for(int i=1;iRowCount;i++)
for(int j=1;jColCount;j++)
{
if(StoimPer->Cells[j][i]==""){
MessageDlg(L"Введите данные в таблицу стоимости перевозки.", mtConfirmation,
TMsgDlgButtons() << mbOK, 0);
return;
}
else{
C[i-1][j-1]=(int)(StoimPer->Cells[j][i].ToDouble()*100);
C0[i-1][j-1]=(int)(StoimPer->Cells[j][i].ToDouble()*100);
}
}
//Создание матрицы потребностей
Pm=Potr->ColCount-1;
P=new int[Pm];
for(int i=1;iColCount;i++)
{
if(Potr->Cells[i][0]=="")
{
MessageDlg(L"Введите данные в таблицу потребления.", mtConfirmation,
TMsgDlgButtons() << mbOK, 0);
return;
}
else
P[i-1]=(int)(Potr->Cells[i][0].ToDouble()*100);
}
//Создание матрицы запасов
Zn=Zapas->RowCount-1;
Z=new int[Zn];
for(int i=1;iRowCount;i++)
{
if(Zapas->Cells[0][i]=="")
{
MessageDlg(L"Введите данные в таблицу запасов.", mtConfirmation,
TMsgDlgButtons() << mbOK, 0);
return;
}
else
Z[i-1]=(int)(Zapas->Cells[0][i].ToDouble()*100);
}
for(int i=0;iRowCount;i++)
for(int j=0;jColCount;j++)
Ogran->Cells[j][i]="10000";
Dn=Ogran->RowCount;
Dm=Ogran->ColCount;
D=new int*[Dn];
for (int i=0; i<Dn; i++)
D[i]=new int[Dm];
for(int i=0;i<Dn;i++)
for(int j=0;j<Dm;j++)
D[i][j]=(int)(Ogran->Cells[j][i].ToDouble()*100);
//Инициализыция невязок
OPrz=0;
OPtr=0;
for(int i=0;i<Zn;i++)
OPrz+=Z[i];
for(int i=0;i<Pm;i++)
OPtr+=P[i];
if(OPrz!=OPtr){
MessageDlg(L"Задача не удавлетворяет условию баланса.", mtConfirmation,
TMsgDlgButtons() << mbOK, 0);
return;
}
if(PageControl->PageCount>2){
NIter=0;
for(int i=PageControl->PageCount-1;i>=2;i--)
PageControl->Pages[i]->~TTabSheet();
}
//Создание С штрих
for(int j=0;j<Cm;j++)
{
int min=C[0][j];
for(int i=1;i<Cn;i++){
if(C[i][j]<min)
min=C[i][j];
}
for(int i=0;i<Cn;i++){
C[i][j]-=min;
CS[i][j]=C[i][j];
}
}
//Создание C0
for(int i=0;i<Cn;i++){
int min=C[i][0];
for(int j=1;j<Cm;j++)