309875 (Решение задач линейного программирования транспортной задачей), страница 2
Описание файла
Документ из архива "Решение задач линейного программирования транспортной задачей", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "309875"
Текст 2 страницы из документа "309875"
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
Этапы решения транспортной задачи:
-
Получение начального решения
-
Проверка решений на оптимальность
-
Усовершенствование несовершенных решений
Интуитивный подход.
Проверка на оптимальность и пересмотр несовершенных решений предусматривает анализ каждой пустой ячейки. Это выполняется так: одна единица перемещается в пустую ячейку и рассматривается влияние этого перемещения на стоимость. Если стоимость увеличилась, то это значит, что использование ячейки увеличило бы общие затраты. Если стоимость осталась не изменой, это значит альтернативный план с той же общей стоимостью. Если анализ показывает уменьшение – это значит возможно лучшее решение.
Таблица 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г.