Двухэтапная (многоэтапная) транспортная задача
Рассмотрение двухэтапной транспортной задачи линейного программирования и метода потенциалов как метода ее решения. Разработка наиболее рациональных путей и способов транспортирования товаров, устранения чрезмерно дальних, встречных, повторных перевозок.
Рубрика | Экономико-математическое моделирование |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 18.03.2011 |
Размер файла | 675,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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, в которых сосредоточены запасы однородных продуктов в количестве a1, ..., аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1, ..., Вm, потребность которых в указанных продуктах составляет b1, ..., bn единиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта Ai в пункт Вj, i 1, …, m; j 1, ..., n. Предположим, что
(1)
т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.
Пусть хij - количество единиц продукта, поставляемого из пункта Аi в пункт Вj. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой (2) :
(2)
Суммарное количество продукта, направляемого из каждого пункта отправения во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что (3)
, i 1, …, m; (3)
Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие (4) полного удовлетворения спроса:
, j 1, …, n; (4)
Объемы перевозок (5) - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:
xij0, i =1, ..., m; j =1, ..., n; (5)
Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.
Определение 1.
Всякое неотрицательное решение системы линейных уравнений (6)
, j 1, …, n и , i 1, …, m, (6)
определяемое матрицей X=(xij)(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 методом, метод Ордена-Маша не поддерживается программой.
Так же общую стоимость грузоперевозок задачи нужно считать вручную. линейное программирование транспортный
Заключение
В работе изложены основные подходы и методы решения многоэтапной транспортной задачи, являющейся довольно частой задачей линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Алгоритм и методы решения многоэтапной транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. К таким задачам относятся следующие:
- оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;
- оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
- увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;
Таким образом, важность решения данной задачи для экономики несомненна.
СПИСОК ЛИТЕРАТУРЫ
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
Подобные документы
Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
реферат [4,1 M], добавлен 09.03.2011Решение задач линейного программирования на примере ПО "Гомсельмаш". Алгоритм и экономико-математические методы решения транспортной задачи. Разработка наиболее рациональных путей, способов транспортирования товаров, оптимальное планирование грузопотоков.
курсовая работа [52,3 K], добавлен 01.06.2014Транспортная задача линейного программирования, закрытая модель. Создание матрицы перевозок. Вычисление значения целевой функции. Ввод зависимостей из математической модели. Установление параметров задачи. Отчет по результатам транспортной задачи.
контрольная работа [202,1 K], добавлен 17.02.2010Численные методы решения трансцедентных уравнений. Решение с помощью метода жордановых исключений системы линейных алгебраических уравнений. Симплексный метод решения задачи линейного программирования. Транспортная задача, применение метода потенциалов.
методичка [955,1 K], добавлен 19.06.2015Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
контрольная работа [135,3 K], добавлен 01.06.2014Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа [268,0 K], добавлен 17.02.2010Понятие "транспортная задача", ее типы. Отыскание оптимального плана перевозок однородного груза, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок. Решения прямой и двойственной задачи линейного программирования.
контрольная работа [81,9 K], добавлен 14.09.2010Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
учебное пособие [126,0 K], добавлен 07.10.2014Экономико-математическая модель прикрепления пунктов отправления к пунктам назначения, расчет оптимального плана перевозок. Решение транспортной задачи метолом потенциалов (перераспределение ресурсов по контуру), пример вычислительного алгоритма.
учебное пособие [316,8 K], добавлен 17.10.2010