Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Транспортная задача. Многоэтапная транспортная задача

1.1 Методы решения двухэтапных (многоэтапных) транспортных задач

1.1.1 Метод Ордена - Машa

1.1.2 Поочерёдный метод

1.1.3 Обратно - Поочередный метод

1.2 Методы нахождения опорного плана транспортной

задачи

1.3 Метод потенциалов

2. Решение практической задачи

3. Спецификация программы «RTZMP»

Заключение

Список литературы

Приложение А Листинг программы «RTZMP

Введение

Я выбрал эту тему курсовой работы, потому что каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

Актуальность выбранной тематики курсовой работы заключается в том, что к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

Целью данной работы является рассмотрение двухэтапной транспортной задачи и метода потенциалов как метода ее решения.

Для реализации данной цели в работе необходимо решить следующие задачи:

- рассмотреть двухэтапную транспортную задачу, общую постановку, цели, задачи;

- изучить основные типы, виды моделей;

- охарактеризовать методы решения транспортной задачи;

- проанализировать метод потенциалов как метод решения транспортной задачи.

1. Транспортная задача. Многоэтапная транспортная задача

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

(1)

т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой (2) :

(2)

Суммарное количество продукта, направляемого из каждого пункта отправения во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что (3)

, i 1, …, m; (3)

Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие (4) полного удовлетворения спроса:

, j 1, …, n; (4)

Объемы перевозок (5) - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:

x_ij0, i =1, ..., m; j =1, ..., n; (5)

Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.

Определение 1.

Всякое неотрицательное решение системы линейных уравнений (6)

, j 1, …, n и , i 1, …, m, (6)

определяемое матрицей X=(x_ij)(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.

Определение 2.

План X*=(x*_ij)(i 1, …, m; j 1, ..., n), при котором функция (7)

(7)

принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с баз потребителям .

Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно a=a+a+…a ,а общее количество имеющегося в наличии груза- a.

Заказы каждого из потребителей (потребности) обозначим соответственно, а общее количество b=b+b+…b потребностей -;

Тогда при условии (a=b) мы имеем - закрытую модель.

A при условии (ab) - открытую модель транспортной задачи.

Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза (a> b) либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a < b).

Двухэтапные транспортные задачи являются обычными транспортными задачами, но транспортировка проходит не напрямую, а через промежуточные пункты. Встречаются не только двухэтапные, но и трех, четырех и более -этапные задачи. Такого рода задачи необходимы для грузов, которые требуют спец. условий, например сыры, колбасы, молока и другие грузы которые требуют несколько промежуточных пунктов или складов. Так же в этой задаче грузом может являться любой другой продукт или вещь.

Двухэтапные транспортные задачи являются вариантом обычной транспортной задачи, но в её решении приводятся некоторые другие методы.

1.1 Методы решения двухэтапных (многоэтапных) транспортных

задач

1.1.1 Метод Ордена - Маша

Этот метод придумали американский ученый П.Орден и Советский математик С.Маш в одно время, но на разных континентах. Суть метода заключается в том, что строится четырехблочная таблица с фиктивной диагональю и пустым блоком, в этой таблице сразу располагается перемещение продукции через промежуточные пункты, что невозможно в любых других методах, этот метод дает наилучший результат перевозок, но выполняется он лишь при условии (8):

 ; (8)

Где:

- Поставщик;

-Оптовые базы;

- Потребитель;

1.1.2 Поочерёдный метод

Данный метод очень прост, но приносит низкие результаты. Он может использоваться при любых условиях задачи. Суть данного метода в том, что все этапы в задаче решаются по очереди, как обычные транспортные задачи,

А затем грузоперевозки из каждого этапа складываются и образуют общий грузооборот. У данного метода крайне низкий критерий оптимальности.

1.1.3 Обратно - поочередный метод

Этот метод является очень похожим на Поочередный метод. В данном методе тоже происходит разделение на этапы и сложение всех грузооборотов, но решаются они с конца, а не с начала. Он эффективнее Поочередного метода при условии (9):

; (9)

И приносят такой же результат, как и Поочередный метод, при условии (10)

; (10)

Где:

- Поставщик;

-Оптовые базы;

- Потребитель;

1.2 Методы нахождения опорного плана транспортной задачи

Метод наименьшей стоимости

При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них.

Метод аппроксимации Фогеля

При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.

Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).

Диагональный метод, или метод северо-западного угла

При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок.

Метод минимального элемента.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел и . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

1.3 Метод потенциалов

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj.

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

2. Решение практической задачи

По заказу 5 потребителей (А,Б,В,Г,Д) на 4 предприятиях-изготовителях (1,2,3,4) производится продукция. В процессе доставки к потребителям продукция может хранится на 3 оптовых базах(а1,а2,а3). Организация снабжения потребителей продукции осуществляется по схеме:

Изготовитель (изг.)Оптовая База (ОБ)Потребитель (потр.).

То есть, вся изготовленная продукция от ИЗГ. сначала складируется на ОБ, и только потом поставляется к ПОТР.

Необходимо:

Выбрать способ оптимальной организации снабжения ПОТР. продукцией ИЗГ, (Выбрать оптимальный план перевозок).

Найти F. Где F - суммарные затраты на перевозки [руб].

Ежемесячный спрос на продукцию: [шт.],емкость ОБ:[шт.],тарифы:[руб/шт.] за доставку продукции с ОБ к ПОТР. приведены в таблице 1.

Таблица 1 .

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1						300
	2						420
	3						730
Спрос	480	750	360	200	180

Ежемесячные объемы производства ,емкость ОБ , и суммарные затраты на производство и доставку от ИЗГ. к ОБ приведены в таблице 2.

Таблица 2.

	ОБ	Произ-водство
	1	2	3
ПОСТАВ-ЩИКИ	А1				480
	А2				570
	А3				280
	А4				390
Запас	300	420	730

Выберем метод решения задачи.

Для данной задачи, которая является многоэтапной, в часности двухэтапной,

Существуют 3 метода решения:

1 метод: Поочередное решение.

2 метод: Обратно - поочередное решение.

3 метод: Метод Ордена - Маша.

1 и 2 метод приведут к одинаковому решению так как соблюдается условие (11) :

>< (11)

Где:

- Поставщик;

-Оптовые базы;

- Потребитель;

3 метод не подходит для данной задачи, так как не соблюдаются условие (12):

<>

== (12)

Где:

- Поставщик;

-Оптовые базы;

- Потребитель;

В данной задаче обязательно использование фиктивной Оптовой базы в обеих таблицах.

Выберем метод: Обратно - поочередного решения, так как он подходит для данной задачи и приведет к такому же результату, что и метод Поочередного решения.

Пусть X- суммарный запас ОБ, Y-суммарный спрос потребителя, Z-суммарное производство поставщика. Тогда:

X=1450 ед.

Y=1970 ед.

Z=1720 ед.

Задача будет решена в 2 этапа:

1 этап: Нахождение оптимального плана поставок от ОБ к Потребителю.

1 этап: Нахождение оптимального плана поставок от поставщика к ОБ.

Этап 1.

Дана таблица перевозок от ОБ к Потребителю, так как X<Y,введем фиктивную ОБ - Ф1.

X+Ф1=Y;

Ф1=Y-X;

Ф1=1970-1450=520 ед.

Ниже приведена начальная таблица плана перевозок.

Таблица 3 .

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1						300
	2						420
	3						730
Спрос	480	750	360	200	180

После введения фиктивной ОБ таблица примет вид:

Таблица 4 Введение фиктивного элемента.

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1						300
	2						420
	3						730
	Ф1						520
Спрос	480	750	360	200	180

Найдем опорный план. Для нахождения опорного плана будем использовать метод минимального элемента.

Таблица 5 Опорный план.

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1		300				300
	2		410			10	420
	3			360	200	170	730
	Ф1	480	40				520
Спрос	480	750	360	200	180

В таблице соблюдается условие (11)

n+m-1; (13)

Где :

m - Количество ОБ;

n - Количество Потребителей ;

Суммарная стоимость грузооборота будет высчитываться по формуле (14).

F1=1*А+1*Б+1*В+1*Г+1*Д+

2*А+2*Б+2*В+2*Г+2*Д+

3*А+3*Б+3*В+3*Г+3*Д+ (14)

Ф1*А+Ф1*Б+Ф1*В+Ф1*Г+Ф1*Д

F1 = 29670 руб.

Где:

F1 - Суммарная стоимость грузооборота от ОБ к Потребителям.

Построим матрицу для таблицы 5:

Матрица строится по принципу метода потенциалов (15) :

Q=С-A+B (15)

Где:

Q - мощность перевозки;

C - стоимость ед. перевозки в клетке;

A - потенциал Потребителя;

B - потенциал ОБ;

Матрица 1.

Если в матрице присутствует отрицательный элемент, то план перевозок не оптимален. Отрицательный элемент присутствует, это (-9) (3 стр. 2 ст.).

Построим график оптимизации плана перевозок по методу потенциалов:

График 1.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Найдем минимальный отрицательный элемент графика:

Min={170;410}=170;

Произведем перемещение поставок по методу потенциалов:

График 2.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Итерация 1:

Составим новую таблицу с учетом перемещений поставок:

Таблица 6 Итерация 1.

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1		300				300
	2		240			180	420
	3		170	360	200		730
	Ф1	480	40				520
Спрос	480	750	360	200	180

В таблице соблюдается условие n+m-1;

Суммарная стоимость грузооборота F1 = 28140 руб.

Построим матрицу для таблицы 6:

Матрица 2.

В матрице присутствует отрицательный элемент, это (-9) (4 стр. 3 ст.).

Построим график оптимизации плана перевозок:

График 3.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Найдем минимальный отрицательный элемент графика:

Min={40;360}=40;

Произведем перемещение поставок по методу потенциалов:

График 4.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Итерация 2:

Составим новую таблицу с учетом перемещений поставок:

Таблица 7 Итерация 2.

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1		300				300
	2		240			180	420
	3		210	320	200		730
	Ф1	480		40			520
Спрос	480	750	360	200	180

В таблице соблюдается условие n+m-1;

Суммарная стоимость грузооборота F1=27800.

Построим матрицу для таблицы 7:

Матрица 3.

В матрице присутствует отрицательный элемент, это (-15) (2 стр. 1 ст.).

Построим график оптимизации плана перевозок:

График 5.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Найдем минимальный отрицательный элемент графика:

Min={240;320;480}=240;

Произведем перемещение поставок по методу потенциалов:

График 6.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Итерация 3:

Составим новую таблицу с учетом перемещений поставок:

Таблица 8 Итерация 3.

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1		300				300
	2	240				180	420
	3		450	80	200		730
	Ф1	240		280			520
Спрос	480	750	360	200	180

В таблице соблюдается условие n+m-1;

Суммарная стоимость грузооборота F1=24180.

Построим матрицу для таблицы 8:

Матрица 4.

В матрице присутствует отрицательный элемент, это (-21) (1стр. 5ст.).

Построим график оптимизации плана перевозок:

График 7.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Найдем минимальный отрицательный элемент графика:

Min={300;180;240;80}=80;

Произведем перемещение поставок по методу потенциалов:

График 8.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Итерация 4:

Составим новую таблицу с учетом перемещений поставок:

Таблица 9 Итерация 4.

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1		220			80	300
	2	320				100	420
	3		530		200		730
	Ф1	160		360			520
Спрос	480	750	360	200	180

В таблице соблюдается условие n+m-1;

Суммарная стоимость грузооборота F1 = 22500 руб.

Построим матрицу для таблицы 9:

Матрица 5.

В матрице присутствует отрицательный элемент, это (-14) (4 стр. 5 ст.).

Построим график оптимизации плана перевозок:

График 9.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Найдем минимальный отрицательный элемент графика:

Min={100;160}=100;

Произведем перемещение поставок по методу потенциалов:

График 10.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Итерация 5:

Составим новую таблицу с учетом перемещений поставок:

Таблица 10 Итерация 5.

	ПОТРЕБИТЕЛИ	Запас
	А	Б	В	Г	Д
ОБ	1		220			80	300
	2	420					420
	3		530		200		730
	Ф1	60	360			100	520
Спрос	480	750	360	200	180

В таблице соблюдается условие n+m-1;

Суммарная стоимость грузооборота F1 = 21100 руб.

Построим матрицу для таблицы 10:

Матрицa 6.

В матрице отсутствует отрицательный элемент, это значит ,что найден оптимальный план перевозок продукции от ОБ к Потребителю.

Этап 2.

Дана таблица перевозок от Поставщика к ОБ, так как X<Z,введем фиктивную ОБ - Ф2.

X+Ф2=Z;

Ф2=Z-X;

Ф2=1720-1450=270 ед.

Ниже приведена начальная таблица плана перевозок.

Таблица 11 .

	ОБ	Произ-водство
	1	2	3
ПОСТАВ-ЩИКИ	А1				480
	А2				570
	А3				280
	А4				390
Запас	300	420	730

После введения фиктивной ОБ таблица примет вид:

Таблица 12 Введение фиктивного элемента 2.

	ОБ	Производство
	1	2	3	Ф2
ПОСТАВ-ЩИКИ	А1					480
	А2					570
	А3					280
	А4					390
Запас	300	420	730	270

Найдем опорный план. Для нахождения опорного плана будем использовать метод минимального элемента.

Таблица 13 Опорный план 2.

	ОБ	Производство
	1	2	3	Ф2
ПОСТАВ-ЩИКИ	А1	210			270	480
	А2		420	150		570
	А3	90		190		280
	А4			390		390
Запас	300	420	730	270

В таблице соблюдается условие n+m-1;

Где :

m - Количество ОБ;

n - Количество Потребителей ;

Суммарная стоимость грузооборота будет высчитываться по формуле (16).

F2=А1*1+А1*2+А1*3+А1*Ф2+

А2*1+А2*2+А2*3+А2*Ф2+

А3*1+А3*2+А3*3+А3*Ф2+ (16)

А4*1+А4*2+А4*3+А4*Ф2

F2 = 27090 руб.

Где:

F2 - Суммарная стоимость грузооборота от Поставщика к ОБ.

Построим матрицу для таблицы 13:

Матрица 7.

В матрице присутствует отрицательный элемент, это (-1) (3 стр. 4 ст.).

Построим график оптимизации плана перевозок:

График 11.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Найдем минимальный отрицательный элемент графика:

Min={270;90}=90;

Произведем перемещение поставок по методу потенциалов:

График 12.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Итерация 6:

Составим новую таблицу с учетом перемещений поставок:

Таблица 14 Итерация 6.

	ОБ	Производство
	1	2	3	Ф2
ПОСТАВ-ЩИКИ	А1	300			180	480
	А2		420	150		570
	А3			190	90	280
	А4			390		390
Запас	300	420	730	270

В таблице соблюдается условие n+m-1;

Суммарная стоимость грузооборота F2 = 27000 руб.

Построим матрицу для таблицы 14:

Матрицa 8.

В матрице отсутствует отрицательный элемент, это значит ,что найден оптимальный план перевозок продукции от Поставщика к ОБ.

F= F1+F2= 21100 + 27000=48100 руб.

Где F- суммарный грузооборот от Поставщика к Потребителю.

Ответ:

Данная двухэтапная транспортная задача решается Обратно- поочередным методом и разбивается на 2 обычные транспортные задачи, которые решаются методом потенциалов, с нахождением опорного плана методом минимального элемента. Суммарные грузообороты двух задач складываются и создают общий грузооборот (F). Суммарный грузооборот от поставщика к потребителю составляет 48100 рублей. Для большей выгоды всех трех участников задачи необходимо: поставщику увеличить производство на 250 ед. а оптовым базам расширить склады на 520 ед. В этом случае производитель будет удовлетворять нужды и потребителя, и вмещать всю продукцию на оптовых базах и при этом не оставлять лишние единицы производства.

3. Спецификация программы «RTZMP»

Программа RTZMP создана для применения математического программирования на ЭВМ. Программа решает транспортные задачи методом потенциалов. Программа так же предлагает выбрать метод нахождения опорного плана.

Системные требования программы:

ОС: Windows, Mac OS, Lunix.

CD/DVD - ROM привод.

16Мб оперативной памяти и более.

Клавиатура, мышь.

Процессор от 0,3 Гц.

Запустить программу можно, скопировав ее на жесткий диск компьютера, нажать двойным щелчком ЛКМ, либо запустить напрямую с CD-R.

Рисунок 1.

Интерфейс программы прост.

1 - необходимо ввести количество поставщиков и потребителей.

2 - заполнить таблицу данными.

3 - выбрать метод опорного плана.

4 - нажать «расчет».

Далее программа выведет опорный план, графики, стоимость грузоперевозок, и итерации, при необходимости сама добавит фиктивных поставщиков.

Недостаток программы в том, что она может решать двухэтапные задачи только 2 и 3 методом, метод Ордена-Маша не поддерживается программой.

Так же общую стоимость грузоперевозок задачи нужно считать вручную. линейное программирование транспортный

Заключение

В работе изложены основные подходы и методы решения многоэтапной транспортной задачи, являющейся довольно частой задачей линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.

Алгоритм и методы решения многоэтапной транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. К таким задачам относятся следующие:

- оптимальное закрепление за станками операций по обработке деталей. В них c_ij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения c_ij берутся с отрицательным знаком;

- оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью c_ij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

- увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;

Таким образом, важность решения данной задачи для экономики несомненна.

СПИСОК ЛИТЕРАТУРЫ

1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.

2. Баумоль У. Экономическая теория и исследование операций. - М.; Наука, 2004.

3. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.

4. Боровков А.А. Математическая статистика. М.: Наука, 2004.

5. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 2004

6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - СПБ: Издательство «Лань», 2003.

7. Коршунов Д.А., Чернова Н.И. Сборник задач и упражнений по математической статистике. Новосибирск: Изд-во Института математики им. С.Л.Соболева СО РАН, 2001.

8. Красс М. Математика для экономических специальностей. Учебник. 3-е изд., перераб и доп. М, Экономист, 2004.

9. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. - 3-е изд., исп. - М.: Дело, 2002.

10. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск, Высшая школа, 2005

11. Пехелецкий И.Д. Математика: учебник для студентов. - М.: Академия, 2003.

Приложение А Листинг программы «Rtzmp»

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls;

type

TForm1 = class(TForm)

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

RadioButton1: TRadioButton;

RadioButton2: TRadioButton;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Panel1: TPanel;

Panel2: TPanel;

Button1: TButton;

Button2: TButton;

Button3: TButton;

Button4: TButton;

Button5: TButton;

Button6: TButton;

Edit4: TEdit;

Button7: TButton;

Button8: TButton;

Panel3: TPanel;

Button9: TButton;

Label8: TLabel;

Label9: TLabel;

Edit5: TEdit;

Label10: TLabel;

Label11: TLabel;

Button10: TButton;

procedure Edit1Change(Sender: TObject);

procedure Button7Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button6Click(Sender: TObject);

procedure Button5Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button8Click(Sender: TObject);

procedure Button9Click(Sender: TObject);

procedure Edit2Change(Sender: TObject);

procedure Edit3Change(Sender: TObject);

procedure FormShow(Sender: TObject);

procedure Button10Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

ct,rt:array[1..999] of real;

i,j,n:integer;

ft:array [1..999,1..2] of real;

coin,miax,c1,r1,sdvig:real;

wins:array[1..999,1..999,1..2] of real;

l:integer;

implementation

uses unit2;

{$R *.dfm}

procedure TForm1.Edit1Change(Sender: TObject);

begin

if not(edit1.text='') then

try

n:=strtoint(edit1.Text);

except

showmessage('Введите корректное число');

end;

end;

procedure TForm1.Button7Click(Sender: TObject);

begin

edit4.Text:= 'невырожденная';

i:=1;

label3.Caption:=inttostr(i-1);

label5.Caption:=inttostr(n-1);

panel3.Visible:=true;

if radiobutton1.Checked then label6.Caption:='отккрытый';

if radiobutton2.Checked then label6.Caption:='закрытый ';

radiobutton1.Enabled:=false;

radiobutton2.Enabled:=false;

edit1.enabled:=false;

button7.Enabled:=false;

edit5.SetFocus;

end;

procedure TForm1.Button2Click(Sender: TObject);

begin (`не все ячейки заполнены') else

try

edit2.Text:=floattostr(ct[i+1]);

edit3.Text:=floattostr(rt[i+1]);

i:=i+1;

except showmessage('Введите корректные данные');

end;

label3.Caption:=inttostr(i-1);

end;

procedure TForm1.Button6Click(Sender: TObject);

begin

edit2.Text:=floattostr(ct[n]);

edit3.Text:=floattostr(rt[n]);

i:=n;

label3.Caption:=inttostr(i-1);

end;

procedure TForm1.Button5Click(Sender: TObject);

begin

i:=1;

edit2.Text:=floattostr(ct[i]);

edit3.Text:=floattostr(rt[i]);

label3.Caption:=inttostr(i-1);

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

if strtoint(label3.Caption)=0 then showmessage(открытый тип') else

begin

i:=i-1;

edit2.Text:=floattostr(ct[i]);

edit3.Text:=floattostr(rt[i]);

label3.Caption:=inttostr(i-1);

end;

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

halt;

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

edit1.Clear;

edit2.Clear;

edit3.Clear;

edit4.Clear;

i:=1;

label3.Caption:='';

label5.Caption:='';

panel3.Visible:=true;

for i:=1 to n do

begin

ct[i]:=0;

rt[i]:=0;

end;

edit5.Clear;

radiobutton1.Checked:=false;

radiobutton2.Checked:=false;

radiobutton1.Enabled:=true;

radiobutton2.Enabled:=true;

edit1.enabled:=true;

button7.Enabled:=true;

end;

procedure TForm1.Button8Click(Sender: TObject);

var

miax:real;

begin

if radiobutton1.Checked then begin

for i:=n downto 1 do

begin

for j:=2 to i do

if ct[j]-rt[j]+wins[i+1,j+1,1]>ct[1]-rt[1]-coin+ft[i+1,1] then

begin

wins[i,j,1]:=-rt[j]+ct[j]+wins[i+1,j+1,1];

wins[i,j,2]:=1;

end

else

begin

wins[i,j,1]:=ct[1]-rt[1]-coin+ft[i+1,1];

wins[i,j,2]:=2;

end;

miax:=wins[i,1,1];

for j:=2 to i do

if miax<wins[i,j,1] then begin ft[i,1]:=wins[i,j,1]; ft[i,2]:=wins[i,j,2]; miax:=wins[i,j,1]; end;

end;

for i:=2 to n do

if ft[i,2]=2 then begin j:=i; break; end;

edit4.Text:=Таблица 1 '+inttostr(j)+' у.е.';

end

else

if radiobutton2.Checked then

begin

c1:=coin-ct[1];

r1:=rt[1];

for i:=1 to n-1 do

ct[i]:=coin-ct[i+1];

for i:=1 to n-1 do

rt[i]:=rt[i+1];

n:=n-1;

for j:=1 to n do

begin

if rt[j]<ct[j]+r1 then

begin

wins[n,j,1]:=rt[j];

wins[n,j,2]:=1;

end

else

begin

wins[n,j,1]:=ct[j]+r1;

wins[n,j,2]:=2;

end;

end;

n:=n-1;

for i:=n downto 1 do

begin

miax:=wins[i+1,1,1];

for j:=1 to i do

if rt[j]+wins[i+1,j+1,1]<ct[j]+r1+miax then

begin

wins[i,j,1]:=rt[j]+wins[i+1,j+1,1];

wins[i,j,2]:=1;

end

else

begin

wins[i,j,1]:=ct[j]+r1+miax;

wins[i,j,2]:=2;

end;

end;

for i:=1 to n do

if wins[i,i,2]=2 then

begin

l:=l+1;

for j:=2 to i do

begin

ft[l,1]:=ft[l,1]+rt[j-1];

end;

ft[l,1]:=1-ft[l,1]-r1-ct[i];

ft[l,1]:=ft[l,1]*i;

ft[l,2]:=i;

end;

miax:=ft[1,1];

for i:=2 to l do

if miax<ft[i,1] then begin miax:=ft[i,1]; sdvig:=ft[i,2]; end;

edit4.Text:=опорный план '+floattostr(sdvig)+' оп.';

end

else

showmessage('Выберите критерий расчета');

end;

procedure TForm1.Button9Click(Sender: TObject);

begin

for i:=1 to n do

begin

rt[i]:=0;

ct[i]:=0;

end;

i:=1;

edit2.SetFocus;

panel3.Visible:=false;

label11.Caption:=edit5.Text;

coin:=strtofloat(edit5.Text);

end;

procedure TForm1.Edit2Change(Sender: TObject);

begin

ct[i]:=strtofloat(edit2.Text);

end;

procedure TForm1.Edit3Change(Sender: TObject);

begin

rt[i]:=strtofloat(edit3.Text);

end;

procedure TForm1.FormShow(Sender: TObject);

begin

edit1.SetFocus;

end;

procedure TForm1.Button10Click(Sender: TObject);

begin

form2.ShowModal;

end;

end.

Размещено на Allbest.ru