РефератыИнформатика, программированиеРеРешение задач линейного программирования транспортной задачей

Решение задач линейного программирования транспортной задачей

Федеральное агентство по образованию


Федеральное государственное
образовательное учреждение


среднего профессионального
образования


Железногорский горно-металлургический
колледж


КУРСОВАЯ РАБОТА


по дисциплине «Математические методы»


(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
0

>














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
<= 40


Х21 + Х22 + Х23
<= 50


Xij>=0


Ограничение по спросу:


Х11 + Х21 <=
20


Х12 + Х22 <=
30


Х13 + Х23 <=
40


Этапы решения транспортной задачи:


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 0

>















































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


Оценивание ячеек на шаге 3


>










































































1-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 Решение задачи с помощью Microsoft Excel


Программным продуктом, незаменимым в
офисной работе, является электронная таблица 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 Sans
Serif'


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;


procedure
Button1Click(Sender: TObject);


procedure
Button2Click(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] of
Integer;


F : Integer;


implementation


{$R *.DFM}


procedure
TForm1.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) as
TMaskEdit).Text:='';


(TControl(s) as
TMaskEdit).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) as
TMaskEdit).Text:='';


(TControl(s) as
TMaskEdit).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) as
TMaskEdit).Text:='';


(TControl(s) as
TMaskEdit).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;


procedure
TForm1.Button2Click(Sender: TObject);


var


s : String;


i, j : Byte;


ss : TControl;


begin


for i:=0 to
Form1.ComponentCount-1 do


if (Form1.Components[i] is
TMaskEdit) 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((ss
as TMaskEdit).Text);


end


else


if (s[7]='0') then


begin


ss:=(Form1.Components[i]
as TControl);


a[StrToInt(s[8])]:=StrToInt((ss
as TMaskEdit).Text);


end


else


if (s[8]='0') then


begin


ss:=(Form1.Components[i]
as TControl);


b[StrToInt(s[7])]:=StrToInt((ss
as TMaskEdit).Text);


end


end;


s:='';


Memo1.Lines.Add('Начальные данные');


for j:=1 to
SpinEdit1.Value do


begin


for i:=1 to
SpinEdit2.Value do


s:=s+IntToStr(c[i, j])+'
';


s:=s+IntToStr(a[j]);


Memo1.Lines.Add(s);


s:='';


end;


for i:=1 to
SpinEdit2.Value do


s:=s+IntToStr(b[i])+' ';


Memo1.Lines.Add(s);


for i:=1 to
SpinEdit1.Value do


for j:=1 to
SpinEdit2.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 to
SpinEdit1.Value do


begin


for i:=1 to
SpinEdit2.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.Value
do


for j:=1 to
SpinEdit1.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г.

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Решение задач линейного программирования транспортной задачей

Слов:9749
Символов:69672
Размер:136.08 Кб.