Нахождение оптимального плана транспортной задачи распределительным методом
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
стого элемента:
Контур a13:
,3; 2,3; 2,1; 1,1
Контур a14:
,4; 2,4; 2,1; 1,1
Контур a22:
,2; 2,1; 1,1; 1,2
Контур a31:
,1; 1,1; 1,2; 3,2
Контур a33:
,3; 3,2; 1,2; 1,1; 2,1; 2,3
Контур a34:
,4; 3,2; 1,2; 1,1; 2,1; 2,4
Проведем оценку контуров.
Контур a13: С1=8+ (-4) +3+ (-6) =1
Контур a14: С2=7+ (-2) +3+ (-6) =2
Контур a22: С3=6+ (-3) +6+ (-5) =4
Контур a31: С4=7
Контур a33: С5=0
Контур a34: С6=6+ (-1) +5+ (-6) +3+ (-2) =5
Оценка контуров положительна, значит решение законченно и оптимальный план найден (Таблица 5).
Таблица 5 - Оптимальный план
86142641288101464
Решение произведенное в программе:
Рисунок 7 - Ввод данных
Рисунок 8 - Опорный план
Рисунок 9 - Оптимальный план
Было протестировано еще множество примеров, решения которых также совпадали с решениями в ручную. Также было решено эту задачу с опорным планом "Северо-западного" угла, решение представлено на рисунке 10 и 11.
Рисунок 10 - Опорный план "Северо-западным" методом
Рисунок 11 - Оптимальный план на основе опорного плана методом "Северо-западного угла"
Заключение
Цель курсовой работы заключалась в составление оптимального плана транспортной задачи распределительным методом.
Все цели которые были поставлены в курсовом проекте были выполнены.
Была построена математическая модель транспортной задачи, после чего разработан алгоритм решения. На основе выше перечисленных целей была создана программа для решения транспортной задачи распределительным методом. В итоге были решены множество задач программой, ответ которой совпадал с заранее подготовленным решением.
Таким образом, цель курсового проекта была полностью достигнута, а сам курсовой проект выполнен.
Список использованных источников
1.">
2.">
3.">
.">
5.Агальцов В.П., Математические методы в программировании: учебник / В.П. Агальцов, И.В. Вальдайская. - М. ИД "Форум": ИНФА-М, 206. - 224с.
.Стандарт предприятия (колледжа). Требования по выполнению и оформлению дипломных и курсовых проектов (работ). СТП-УГК-5. ФГОУ СПО УГК им.И. И. Ползунова, 2005г. - 42с.
Приложение А
Код программы
unit Unit1;
interface, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Grids, ComCtrls, Buttons, Spin;= array [1.100,1.100] of integer;= class (TForm): TStringGrid;: TGroupBox;: TLabel;: TLabel;: TLabel;: TComboBox;: TButton;: TSpinEdit;: TSpinEdit;: TButton;Button1Click (Sender: TObject);ComboBox1KeyPress (Sender: TObject; var Key: Char);FormCreate (Sender: TObject);StringGrid1DrawCell (Sender: TObject; ACol, ARow: Integer;: TRect; State: TGridDrawState);StringGrid1KeyPress (Sender: TObject; var Key: Char);StringGrid1GetEditText (Sender: TObject; ACol, ARow: Integer;Value: String);SpinEdit1Change (Sender: TObject);SpinEdit2Change (Sender: TObject);SpinEdit1KeyPress (Sender: TObject; var Key: Char);SpinEdit2KeyPress (Sender: TObject; var Key: Char);Button2Click (Sender: TObject);opor_plan (ColCount,RowCount: integer); // опорный план
procedure raspred_metod (mas12: arr); // органазация распределительного метода
function sum_pot (StringGrid: TStringGrid): integer; // сумма потребителейsum_proiz (StringGrid: TStringGrid): integer; // сумма производителейFindPath (i,j: integer); // нахождение путиLookHorizontaly (u, v, u1, v1: integer): boolean; // проверяем есть ли в строке ячейка которую можно взять в контурAddElement (u,v: integer); // добавляем индексы элемента в путь контура LookVerticaly (u, v, u1, v1: integer): boolean; // проверяем есть ли в столбце ячейка которую можно взять в контурproced (); // процедура для нахождение отрицательного значения по сумме контураpereraspred (i: integer); // осуществляется построение следующего опорного плана
{ Private declarations }
{ Public declarations };n=100;: TForm1;,koef2,mas: arr; // массивы коэффициентов размерностью 100x100: integer; // большое чилсо: array of integer; // массив пути: array of array of integer; // массив контура,qwe,kp: integer;: string;Unit2;
{$R *. dfm}TForm1. Button1Click (Sender: TObject);,j,rc,cc: integer;: bool;: =false;: =StringGrid1. RowCount-1; // строки: =StringGrid1. ColCount-1; // столбцы
// проверка таблицы стоимостиi: =1 to cc do
for j: =1 to rc do(StringGrid1. Cells [i,j] =) or (StringGrid1. Cells [i,j] =0) then k: =true;
// проверка на сбалансированность программыk<>true then
beginsum_pot (StringGrid1) =sum_proiz (StringGrid1) then_plan (StringGrid1. ColCount,StringGrid1. RowCount)ShowMessage (Задача не сбалансирована, приведите ее к сбалансированному виду);ShowMessage (Заполните пустые клетки или уберите нули);
end;TForm1.comboBox1KeyPress (Sender: TObject; var Key: Char);: =#0;;TForm1. FormCreate (Sender: TObject);: integer;: =999999;. Cells [0,0]: =Матрица;. ColCount: =SpinEdit1. Value+2; // задаем количество столбцов = 2. RowCount: =SpinEdit2. Value+2; // задаем количество строк = 2i: =1 to StringGrid1. ColCount-2 do
StringGrid1. Cells [i,0]: =A+IntToStr (i);
for i: =1 to StringGrid1. RowCount-2 do
StringGrid1. Cells [0, i]: =B+IntToStr (i);
StringGrid1. Cells [StringGrid1. ColCount-1,0]: =Производители;. Cells [0,StringGrid1. RowCount-1]: =Потребители;. Cells [StringGrid1. ColCount-1,StringGrid1. RowCount-1]: =A;;TForm1. AddElement (u, v: integer); // добавляем индексы элемента в путь контура
begin: =kp+1;[qwe]: =u;: =qwe+1;[kp]: =v;;TForm1. FindPath (i, j: integer); // нахождение пути: =-1;: =0;(i,j);not LookHorizontaly (i, j, i, j) then(Невозможно найти контур для: +IntToStr (i) + +IntToStr (j));;TForm1. LookHorizontaly (u, v, u1, v1: integer): boolean; // проверяем // есть ли в строке ячейка которую можно взять в контур,cc: integer;: =false;: =StringGrid1. colCount;i: =0 to cc do(i0) theni=v1 then(u, i); // добавление элементов: =true; // возвращаем true;LookVerticaly (u, i, u1, v1) then(u, i);: =True;;;;TForm1. LookVerticaly (u, v, u1, v1: integer): boolean; // проверяем // есть ли в стобце ячейка которую можно взять в контур
var,rc: integer;: =false;: =StringGrid1. rowCount;i: =0 to rc do(i0) thenLookHorizontaly (i, v, u1, v1) then(i,v);: =True;;;TForm1. opor_plan (ColCount, RowCount: integer); // опорный план,l, q, i, j, sum, rc, cc,min,k,p,x: integer;, fund: array [1. n] of integer; // массивы потребителей и производителей: arr;: =0;: =0;: =StringGrid1. RowCount-2; // строки: =StringGrid1. ColCount-2; // стобцыi: =1 to rc doj: =1 to cc do[i,j]: =StrToIntDef (StringGrid1. Cells [j, i],