/>Федеральное агентство по образованию
Федеральное государственноеобразовательное учреждение
среднего профессиональногообразования
Железногорский горно-металлургическийколледж
КУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
(230105.51)
Решение задач линейногопрограммирования транспортной задачей
Выполнил студент гр. ПО-08
А.В. Гудов
Проверил преподаватель:
Н.А. Панасенко
2010 г.
Содержание
Введение
1. Характеристика класса задач
1.1 Общий вид решения и обобщение транспортной задачи
2. Содержательная постановка задачи
3. Математическая постановка задачи
4. Решение задачи
4.1 Математическое решение задачи
4.2 Решение задачи с помощью программы MS Excel
4.3 Листинг программы
4.4 Руководство пользователя
5. Анализ результатов
Заключение
Список используемой литературы
Введение
Под названием “транспортная задача”объединяется широкий круг задач с единой математической моделью. Данные задачиотносятся к задачам линейного программирования и могут быть решены симплекснымметодом. Однако матрица системы ограничений транспортной задачи настолькосвоеобразна, что для ее решения разработаны специальные методы. Эти методы, каки симплексный метод, позволяют найти начальное опорное решение, а затем,улучшая его, получить оптимальное решение.Распределительныезадачи связаны с распределением ресурсов по работам, которые необходимовыполнить. Задачи этого класса возникают тогда, когда имеющихся в наличииресурсов не хватает для выполнения каждой работы наиболее эффективным образом.Поэтому целью решения задачи, является отыскания такого распределения ресурсовпо работам, при котором либо минимизируются общие затраты, связанные свыполнением работ, либо максимизируется получаемый в результате общий доход.Основной целью задачиявляется минимизировать затраты на транспортировку продукции потребителям.
1. Характеристика класса задач1.1 Общий вид решения и обобщениетранспортной задачи
Пустьтребуется перевезти груз из пункта А1, А2,…, Аnв пункты В1, В2,…, Вn.
а11,а12,…, аnk-стоимость перевозки из пункта Аi в пункт Вj.
А1=100;А2=200; А3=150; В1=80; В2=90; В3=120; В4=160.
Распределитьпродукцию так со склада, чтобы затраты были минимальные.
Построим начальную таблицу длязаполнения ячеек:
Таблица 1
Начальная таблица для заполненияячеек 4 7 7 1 100 80 20 12 3 8 8 200 70 120 10 8 10 16 5 150 150 80 90 120 160
Прежде чем начать заполнение ячеек,необходимо проверить условие:
Сумма запаса и сумма потребления былиравны:
100+200+150=80+90+120+160; 450=450.
Принцип заполнения ячеек состоит втом, чтобы в выбранную ячейку заносилось минимальное число из стоящих напротивячеек с параметрами, например: для заполнения ячейки 1-А берутся значения 80 и 100: min= (80;100). Затем меньшее числовычитается из обеих ячеек-значений.
После заполнения необходимо найтицелевую функцию:
Z=80*4+20*7+70*3+120*8+10*8+150*5=3180
Получение начального опорного плана
— метод северо-западного угла
— метод наименьшей стоимости
I. Метод наименьшей стоимости:
· Определим ячейку с наименьшейстоимостью;
· Распределим как можно больше единиц вэту ячейку и вычеркнем строку или столбец, который исчерпан;
· Найдем ячейку с наименьшей стоимостьюиз оставшихся;
· Повторим пункт 2 и 3 пока все единицыне будут распределены.
Таблица 2
Определение ячеек методом наименьшейстоимости. 4 7 7 1 100 100 12 3 8 8 200 90 110 8 10 16 5 150 80 10 60 80 90 120 160
Находим целевую функцию:
100*1+90*3+110*8+80*8+10*16+60*5=2350
Получили начальное решение.
II. Проверка решения на оптимальность:
— метод по камням
— метод Modi.
Проверка на оптимальность заключаетсяв оценке пустых ячеек, используя так называемый цикл.
Метод по камням:
Камни – заполненные ячейки
· Поставим знак «+», в ячейку которуюоцениваем;
· Двигаясь горизонтально иливертикально к заполненной ячейке(при этом можем пропустить заполненную илипустую ячейку которая, разрешит следующий переход к заполненной ячейке),поставим знак «-»;
· Изменяем направление и перемещаемся кдругой заполненной ячейке, выбираем ту разрешит следующий переход, ставим в неезнак «+»;
· Процесс перемещения в заполненнойячейке и чередование знаков продолжаем пока не вернемся к первоначальной.
Таблица 3
Оценивание ячеек1-А 1А+4 -8 3А 3D+5 -1 1D 1-C 1C+7 -1 1D 3D+5 -16 3C -5
Оценка пустых ячеек методами возможнапри условии: число заполненных ячеек равна сумме строк и столбцов и -1:
k=R+L-1
Значение оценки показывает на сколькосократятся(увеличатся) затраты на перевозку единиц продукции если в эту ячейкупереместить значение.
Выбираем из оценок наибольшее помодулю отрицательное значение. Из отрицательных выбираем наименьшее и вычитаемего из всех ячеек пути.
Таблица 4
Изменение начальной таблицы 4 7 7 1 100 10 90 12 3 8 8 200 90 110 8 10 16 5 150 80 70 80 90 120 160
Таким образом, производим решение,находя новое оптимальное решение пока все оценки пустых ячеек будут содержатьтолько положительные значения и нули.
Метод MODI (модифицированное распределение).
Оценка пустых ячеек вычислениеминдексных значений строки и столбца.
Этот метод состоит из шагов:
1) Сделать начальное распределение(интуитивный подход), проверить матрицу на полноценность, в случаенеобходимости провести корректировку.
2) Получить номер индекса для каждойстроки и столбца. Делая это используя только заполненные ячейки. Всегда есть покрайней мере одна заполненная ячейка в каждом столбце и строке.
а) начинаем, назначая ноль в первойстроке
б) определить индекс столбца длялюбой заполненной ячейки в строке 1, используя следующие соотношения:
индекс столбца = U;
индекс строки = V;
затраты ячейки = С;
U = C-V
в) Каждое новое значение столбцапозволит вычислить по крайней мере 1 новое значение строки и наоборот.Продолжайте эту процедуру пока все строки и столбцы будут заполнены индексами.
3) Получить оценки для пустых ячеек
W – оценка ячейки
W = C- (U+V)
1 – C: W = 7-(0+9) = -2
2 – A: W = 4-(1+3)= 0
4) Получение наилучшего решения
Наличие отрицательных ячеексвидетельствует о том, что возможно лучшее решение и наоборот, еслиотрицательных ячеек нет, то было найдено оптимальное решение.
2. Содержательная постановка задачи
Частным случаем задачи линейногопрограммирования является транспортная задача. Проблема транспортировкивключает поиск низко затратных схем распределения товарных запасов от многихисточников до многих мест назначения.
Отгрузочными пунктами (поставщиками)являются фабрики, склады, отделы, из которых отправляются товары. Местомназначения также могут быть фабрики, склады, отделы, которые получают товары.
Информация необходимая дляиспользования модели включает следущее:
— список отправных пунктов ипропускная способность каждого (количество поставок за определенный период);
— список мест назначения и ихпоказатели спроса;
— стоимость транспортировки единицыпродукции от каждого отправленного пункта до каждого места назначения. Этаинформация сводится в транспортную таблицу.
3. Математическая постановка задачи
Пусть Xij — количество груза перевозимого изпункта i в пункт j.
А1=40; А2=50; В1=20; В2=30; В3=40;
/>/>3 5 7
С = 4 6 10
Таблица 5
Начальные параметры B1 B2 B3 A1 3 5 7 40 A2 4 6 10 50 20 30 40
Целевая функция имеет вид:
/>
Ограничение по запасам:
/>
Х11 + Х12 + Х13
Х21 + Х22 + Х23
Xij>=0
Ограничение по спросу:
Х11 + Х21
Х12 + Х22
Х13 + Х23
Этапы решения транспортной задачи:
1) Получение начальногорешения
2) Проверка решенийна оптимальность
3) Усовершенствованиенесовершенных решений
Интуитивный подход.
Проверка на оптимальность и пересмотрнесовершенных решений предусматривает анализ каждой пустой ячейки. Этовыполняется так: одна единица перемещается в пустую ячейку и рассматриваетсявлияние этого перемещения на стоимость. Если стоимость увеличилась, то этозначит, что использование ячейки увеличило бы общие затраты. Если стоимостьосталась не изменой, это значит альтернативный план с той же общей стоимостью.Если анализ показывает уменьшение – это значит возможно лучшее решение.
Таблица 6
Заполнение ячеек B1 B2 B3 A1 3 5 7 20 20 40 A2 4 6 10 50 10 40 20 30 40
Целевая функция:
Z=3*20+5*20+6*10+10*40=60+100+60+400=620
4. Решение задачи
4.1 Математическое решение задачи
Условие задачи:
Три предприятия данногоэкономического района могут производить однородную продукцию, в количествахсоответственно равных А1, А2 и А3 единиц. Эта продукция должна быть поставлена5-и потребителям в количествах, соответственно равных В1, В2, В3, В4 и В5единиц. Затраты связанные с производством и доставкой продукции, задаютсяматрицей С.
А1=180; А2=350; А3=20
В1=110; В2=90; В3=120; В4=80; В5=150
Таблица 7
Индексы матрицы В1 В2 В3 В4 В5 А1 7 12 4 6 5 А2 1 8 6 5 3 А3 6 13 8 7 4
Таблица 8
Первоначальное заполнение ячеек 7 12 4 6 5 180 110 70 1 8 6 5 3 350 20 120 80 130 6 13 8 7 4 20 20 110 90 120 80 150
Найдем целевую функцию:
Z=110*7+70*12+20*8+120*6+80*5+130*3+20*4=3360
Таблица 9
Первое оценивание ячеек1-С 1-D 1-E 2-A +4 -12 +6 -12 +5 -12 +1 -7 +8 -6 +8 -5 +8 -3 +12 -8 -6 -3 -2 3-A 3-B 3-C 3-D +6 -7 +13 -8 +8 -6 +7 -5 +12 -8 +3 -4 +3 -4 +3 -4 +6 -5 +4 +1 +1 +3 -4 +3
Таблица 10
Редактирование таблицы от оцененнойячейки 7 12 4 6 5 180 110 70 1 8 6 5 3 350 90 50 80 130 6 13 8 7 4 20 20 110 90 120 80 150
Повторим для результата нахождениецелевой функции с новыми параметрами:
Z=110*7+70*4+90*8+50*6+80*5+130*3+20*4=2940
Таблица 11
Второй шаг оценки ячеек1-B 1-D 1-E 2-A +12 -4 +6 -4 +5 -4 +1 -7 +6 -8 +6 -5 +6 -3 +4 -6 6 3 4 -8 3-A 3-B 3-C 3-D +6 -7 +13 -8 +8 -6 +7 -5 +4 -6 +3 -4 +3 -4 +3 -4 +3 -4 +4 +1 +1 -4
Таблица 12
Шаг третий 7 12 4 6 5 180 60 120 1 8 6 5 3 350 50 90 80 130 6 13 8 7 4 20 20 110 90 120 80 150
Находим целевую функцию
Z=60*7+120*4+50+90*8+80*5+130*3+20*4=2540
Таблица 13
Оценивание ячеек на шаге 31-B 1-D 1-E 2-A +12 -7 +6 -7 +5 -7 +6 -1 +1 -8 +1 -5 +1 -3 +7 -4 -2 -5 -4 8 3-C 3-A 3-B 3-D +8 -4 +6 -1 +13 -8 +7 -5 +7 -1 +3 -4 +3 -4 +3 -4 +3 -4 +4 +4 +1 +7
Таблица 14
Четвертый шаг 7 12 4 6 5 180 120 60 1 8 6 5 3 350 110 90 20 130 6 13 8 7 4 20 20 110 90 120 80 150
Z=120*4+60*6+110+90*8+20*5+130*3+20*4=2240
Таблица 15
Оценивание ячеек на 4 шаге1-A 1-B 1-E 2-C +7 -6 +12 -8 +5 -6 +6 -5 +5 -1 +5 -6 +5 -3 +6 -4 5 3 1 3 3-C 3-A 3-B 3-D +8 -4 +6 -1 +13 -8 +7 -5 +6 -5 +3 -4 +3 -4 +3 -4 +3 -4 +4 +4 +1 +4
4.2 Решение задачи с помощью MicrosoftExcel
Программным продуктом, незаменимым вофисной работе, является электронная таблица Microsoft Excel. При помощи этогопродукта можно анализировать большие массивы данных. В Excel можно использоватьболее 400 математических, статистических, финансовых и других специализированныхфункций, связывать различные таблицы между собой, выбирать произвольные форматыпредставления данных, создавать иерархические структуры. Воистину безграничныметоды графического представления данных: помимо нескольких десятков встроенныхтипов диаграмм, можно создавать свои, настраиваемые типы, помогающие наглядноотразить тематику диаграммы. Те, кто только осваивает работу с Excel, подостоинству оценят помощь «мастеров» — вспомогательных программ,помогающих при создании диаграмм.
/>
Рисунок 1. Создание общей таблицы
/>
Рисунок 2. Поиск решения
/>
Рисунок 3. Добавление ограничений
/>
Рисунок 4. Вывод целевой функции
4.3 Листинг программы
program PTransport;
uses
Forms,
UTransport in 'UTransport.pas' {Form1};
{$R *.RES}
begin
Application.Initialize;
Application.CreateForm(TForm1,Form1);
Application.Run;
end.
object Form1: TForm1
Left = 192
Top = 107
Width = 522
Height = 332
Caption = 'Транспортная задача 1.0 Beta'
Color = clBtnFace
Font.Charset =DEFAULT_CHARSET
Font.Color = clWindowText
Font.Height = -11
Font.Name = 'MS SansSerif'
Font.Style = []
OldCreateOrder = False
PixelsPerInch = 96
TextHeight = 13
object Label1: TLabel
Left = 8
Top = 8
Width = 36
Height = 13
Caption = 'Строки'
end
object Label2: TLabel
Left = 72
Top = 8
Width = 44
Height = 13
Caption = 'Столбцы'
end
object SpinEdit1:TSpinEdit
Left = 8
Top = 24
Width = 49
Height = 22
MaxValue = 10
MinValue = 2
TabOrder = 0
Value = 2
end
object SpinEdit2:TSpinEdit
Left = 72
Top = 24
Width = 49
Height = 22
MaxValue = 10
MinValue = 2
TabOrder = 1
Value = 2
end
object Button1: TButton
Left = 48
Top = 56
Width = 75
Height = 25
Caption = 'Создать'
TabOrder = 2
OnClick = Button1Click
end
object Button2: TButton
Left = 144
Top = 16
Width = 50
Height = 25
Caption = 'Ввод'
TabOrder = 3
Visible = False
OnClick = Button2Click
end
object Memo1: TMemo
Left = 144
Top = 56
Width = 185
Height = 177
ReadOnly = True
TabOrder = 4
Visible = False
end
end
unit UTransport;
interface
uses
Windows, Messages,SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, Spin, Mask;
type
TForm1 = class(TForm)
SpinEdit1: TSpinEdit;
SpinEdit2: TSpinEdit;
Label1: TLabel;
Label2: TLabel;
Button1: TButton;
Button2: TButton;
Memo1: TMemo;
procedureButton1Click(Sender: TObject);
procedureButton2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
c, x: Array [1..10,1..10] of Integer;
a, b: Array [1..10] ofInteger;
F: Integer;
implementation
{$R *.DFM}
procedureTForm1.Button1Click(Sender: TObject);
var
i, i1, j1, j: Byte;
s: TControl;
begin
Label1.Hide;
Label2.Hide;
SpinEdit1.Hide;
SpinEdit2.Hide;
Button1.Hide;
Button2.Show;
i:=SpinEdit2.Value;
j:=SpinEdit1.Value;
for i1:=1 to i do
for j1:=1 to j do
begin
s:=TMaskEdit.Create(Form1);
s.Width:=25;
s.Left:=i1*25;
s.Top:=j1*21;
s.Name:='Matrix'+IntToStr(j1)+IntToStr(i1);
(TControl(s) asTMaskEdit).Text:='';
(TControl(s) asTMaskEdit).EditMask:='999;0; ';
Form1.InsertControl(s);
end;
for i1:=1 to j do
begin
s:=TMaskEdit.Create(Form1);
s.Width:=25;
s.Left:=i*25+35;
s.Top:=i1*21;
s.Name:='Matrix'+'0'+IntToStr(i1);
(TControl(s) asTMaskEdit).Text:='';
(TControl(s) asTMaskEdit).EditMask:='999;0; ';
Form1.InsertControl(s);
end;
for j1:=1 to i do
begin
s:=TMaskEdit.Create(Form1);
s.Width:=25;
s.Left:=j1*25;
s.Top:=j*21+31;
s.Name:='Matrix'+IntToStr(j1)+'0';
(TControl(s) asTMaskEdit).Text:='';
(TControl(s) asTMaskEdit).EditMask:='999;0; ';
Form1.InsertControl(s);
end;
Button2.Left:=i*25+25-Button2.Width;
Button2.Top:=j*21+62;
Memo1.Show;
Memo1.Left:=i*25+75;
Memo1.Top:=21;
end;
procedureTForm1.Button2Click(Sender: TObject);
var
s: String;
i, j: Byte;
ss: TControl;
begin
for i:=0 toForm1.ComponentCount-1 do
if (Form1.Components[i] isTMaskEdit) then
begin
s:=Form1.Components[i].Name;
if (s[7]'0') and(s[8]'0') then
begin
ss:=(Form1.Components[i]as TControl);
c[StrToInt(s[8]),StrToInt(s[7])]:=StrToInt((ssas TMaskEdit).Text);
end
else
if (s[7]='0') then
begin
ss:=(Form1.Components[i]as TControl);
a[StrToInt(s[8])]:=StrToInt((ssas TMaskEdit).Text);
end
else
if (s[8]='0') then
begin
ss:=(Form1.Components[i]as TControl);
b[StrToInt(s[7])]:=StrToInt((ssas TMaskEdit).Text);
end
end;
s:='';
Memo1.Lines.Add('Начальные данные');
for j:=1 toSpinEdit1.Value do
begin
for i:=1 toSpinEdit2.Value do
s:=s+IntToStr(c[i, j])+'';
s:=s+IntToStr(a[j]);
Memo1.Lines.Add(s);
s:='';
end;
for i:=1 toSpinEdit2.Value do
s:=s+IntToStr(b[i])+' ';
Memo1.Lines.Add(s);
for i:=1 toSpinEdit1.Value do
for j:=1 toSpinEdit2.Value do
x[i,j]:=-1;
i:=1;
j:=1;
Repeat
if a[i]>b[j] then
begin
x[j,i]:=b[j];
a[i]:=a[i]-b[j];
b[j]:=0;
Inc(j);
end
else
begin
x[j,i]:=a[i];
b[j]:=b[j]-a[i];
a[i]:=0;
Inc(i);
end;
Until(i>SpinEdit1.Value) and (j>=SpinEdit2.Value);
Memo1.Lines.Add('');
s:='';
for j:=1 toSpinEdit1.Value do
begin
for i:=1 toSpinEdit2.Value do
if x[i,j]>=0 then
s:=s+IntToStr(x[i, j])+' '
else
s:=s+'0 ';
Memo1.Lines.Add(s);
s:='';
end;
for i:=1 to SpinEdit2.Valuedo
for j:=1 toSpinEdit1.Value do
if x[i,j]>0 then
F:=F+x[i,j]*c[i,j];
Memo1.Lines.Add('Результат: '+IntToStr(F));
end;
end.
4.4 Руководствопользователя
Пуск
Запуск из средыPascal производится нажатием клавишCtrl+F9, аиз Norton Commander нажатием клавиши Enterна файлеInform.exe.
Ввод данных
Ввод данных производится только с цифровой клавиатуры. Цифрыот 0 до 9.
Просмотр результатов.
После ввода цифры (нужного пункта в меню) выводится требуемыйрезультат и после просмотра результата нужно нажать Enter. Затем вновь появитсяменю на экране.
Выход из программы
Выход из программы в среде Pascal и после запуска PTransport.exe файла производится0-ым пунктом меню.
5. Анализ результатов
При решении задачи были полученырезультаты удовлетворяющие условию:
Решая задачу математически, получилизначения: 7 12 4 6 5 180 120 60 1 8 6 5 3 350 110 90 20 130 6 13 8 7 4 20 20 110 90 120 80 150
Z=120*4+60*6+110+90*8+20*5+130*3+20*4=2240
При решении задачи в программе Excel получили значения:
/>
В программе, созданной для решениязадачи, получили тот же результат.
Соответственно можно сделать вывод,что задача была решена правильно.
Заключение
В курсовойработе изложены основные подходы и методы решения транспортной задачи,являющейся одной из наиболее распространенных задач линейного программирования.Решение данной задачи позволяет разработать наиболее рациональные пути и способытранспортирования товаров, устранить чрезмерно дальние, встречные, повторныеперевозки. Все это сокращает время продвижения товаров, уменьшает затратыпредприятий и фирм, связанные с осуществлением процессов снабжения сырьем,материалами, топливом, оборудованием и т.д.
В данной курсовой работе поставленазадача: минимизировать затраты на транспортировку продукции потребителям. Привыполнении курсовой работы были использованы знания по предметам:«Математические методы», «Пакеты прикладных программ». Решение было проведено спомощью пакетов прикладных программ Microsoft Excel и Microsoft Word. Результаты ручного просчёта сравнивались срезультатами, полученными в Microsoft Excel.
Курсовая работа выполнена в полномобъёме в соответствии с требованиями ГОСТ.
Список использованной литературы:
1. Е.Г. Гольштейн, Д.Б. Юдин «Задачи линейного программирования транспортного типа», Москва, 1993.
2. И.Л. Акулич, В.Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2000.
3. www.fmi.asf.ru
4. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование”, Минск, Вышейшая школа, 2001г.
5. Боборыкин В.А. Математические методы решения транспортныхзадач. Л.: СЗПИ, 1986
6. Геронимус Б.А. Экономико-математические методы впланировании наавтомобильном транспорте. М.: Транспорт, 1982
7. Кузнецов Ю.Н., Кузубов В.И., Волощснко А. Б.Математическоепрограммирование. М.: Высшая школа, 1980
8. Красс М.С., Чупрынов Б.П. ”Основыматематики и ее приложения в экономическом образовании”, Издательство “Дело”,Москва 2001г.
9. В.И. Ермаков “Общий курс высшей математикидля экономистов”, Москва, Инфра-М, 2000г.
10. ЕреминИ.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программированияМ.; Наука, 1976г.
11.Карманов В.Г. Математическое программирование. – М.; Наука, 1986г.
12. МоисеевН.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г.