Принятие управленческих решений

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

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

«Применение транспортной задачи к планированию работы автомобильной спецтехники в зимний период»

По предмету: Принятие управленческих решений

МОСКВА 2011 г.

Содержание

Введение

1. Постановка задачи и стратегия решения

1.1 Методы нахождения начального плана перевозок

1.1.1 Метод северо-западного угла

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

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

2. Планирование работы снегоуборочной автомобильной спецтехники

Вывод

планирование автомобильный перевозка

Введение

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

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

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

1. Постановка задачи и стратегия решения

Предположим, что в пунктах A1, A2, …, Am хранится однородный груз в количестве a1, a2, …, am единиц. Этот груз следует доставить в n заданных пунктов назначения B1, B2, …, Bn , причем в каждый из них требуется завести соответственно b1, b2, …, bn единиц этого груза. Обозначим cij стоимость перевозки единицы груза из пункта Ai в пункт Bj.

Транспортные задачи делятся на две группы.

Задачи, удовлетворяющие условию баланса

,

означающему, что общий запас груза на всех пунктах хранения равен суммарной потребности всех пунктов назначения.

Задачи с нарушенным балансом, среди которых выделяются два случая:

а) (суммарные запасы больше суммарных потребностей);

б) (суммарные запасы меньше суммарных потребностей).

Рассмотрим формализацию транспортной задачи, удовлетворяющей условию баланса.

Обозначим - количество груза, перевозимого из пункта Ai в пункт Bj. Тогда суммарная стоимость перевозок имеет вид

. (1)

Ограничения представляются уравнениями вывоза и привоза груза:

(2)

(3)

(4)

Уравнение (2) означает, что из каждого пункта хранения Ai вывозится весь груз, а уравнение (3) описывает факт удовлетворения всех потребностей в пункте Bj . Условие (4) свидетельствует о том, что груз либо вывозится из пункта Ai в пункт Bj, и тогда либо нет, и в этом случае

Решение , системы (2) - (4) называется планом перевозки.

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

. (5)

Условия задачи удобно записывать в виде матрицы перевозок (табл. 1).

Таблица 1

Пункты							Запасы
Потребности							Сумма

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

В матрице перевозок хранится текущий план перевозок .

Стратегия решения задачи

Находится начальный план перевозок.

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

1.1 Методы нахождения начального плана перевозок

Клетки матрицы перевозок, где называются базисными, а остальные, где - свободными.

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

Значение в матрице перевозок находится по формуле

(6)

Значение в свободной клетке не пишется явно, а вместо этого в ней ставится точка.

1.1.1 Метод северо-западного угла

Вычисления осуществляются по формуле (6), начиная с элемента , стоящего в северо-западном углу матрицы перевозок.

Нахождение опорного плана перевозок в транспортной задаче методом северо-западного угла рассмотрим на примере 1:

Пример 1. Найти минимальный план перевозок в транспортной задаче, заданной матрицей (табл.2).

Таблица 2

Пункты				Запасы
	2 10	3 10	4 ?
	1 ?	2 10	5 30
Потребности

Начинаем с северо-западного угла, т.е. Тогда в пункте потребности удовлетворены и, следовательно, ( в табл.2 ставится точка). Первый столбец выбывает из рассмотрения.

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

Продолжаем с северо-западного угла:

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

Заполняем последний элемент, находящийся в северо-западном углу:

Таким образом, получен начальный план перевозок:

с суммарной стоимостью . Число базисных клеток, очевидно, равно ¦

Замечание 1. При нахождении начального плана перевозок возможен случай вырождения, когда в результате вычислений значения получается, что потребности в пункте удовлетворены, а запасы в пункте исчерпаны.

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

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

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

В этом методе по формуле (6) последовательно заполняются клетки с наименьшей стоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью то из них выбирается любая.

Пример 2. Найти минимальный план перевозок в транспортной задаче, заданной матрицей (табл.3).

Таблица 3

Пункты				Запасы
	2 ?	3 ?	4 20
	1 10	2 20	5 10
Потребности

Заполняем клетку с наименьшей стоимостью, равной 1:

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

Из оставшихся клеток ищем клетку с наименьшей стоимостью и заполняем ее: Тогда (в табл. 3 ставится точка), потребности в пункте удовлетворены и выбывает второй столбец.

Из оставшихся двух клеток заполняем клетку с наименьшей стоимостью: Тогда первая строка выбывает (запасы в пункте исчерпаны) и

Таким образом, получен начальный план перевозок



с суммарной стоимостью

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

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

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

Введем следующие понятия.

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

Означенный цикл - цикл, в котором некоторой вершине приписан знак “+”, а затем при обходе цикла в каком-либо направлении знаки чередуются.

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

Потенциалы - числа Каждому пункту хранения ставится в соответствие число , пункту потребления - число .

Алгоритм

Шаг 1. Найти начальный план перевозок методом северо-западного угла или методом минимального элемента.

Шаг 2. Для каждой базисной клетки составить уравнение

.

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

Шаг 3. Для каждой свободной клетки вычислить относительные оценки:

.

Шаг 4. Проанализировать относительные оценки:

а) если все относительные оценки неотрицательны, т.е.

то задача решена, и следует выписать полученный оптимальный план перевозок из последней матрицы, подсчитать его стоимость;

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

Шаг 5. Для свободной клетки с выбранной оценкой , помеченной , построить означенный цикл. Все его вершины, кроме расположенной в клетке , должны находиться в базисных клетках. Свободная клетка берется со знаком “+”.

Шаг 6. Выполнить сдвиг по построенному на шаге 5 циклу на величину , равную наименьшему из чисел, стоящих в отрицательных вершинах. При этом числа, стоящие в положительных вершинах, увеличить на , а числа стоящие в отрицательных вершинах, уменьшить на .

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

Элементы матрицы, не входящие в цикл, остаются без изменений.

Перейти шагу 2.

Замечание 2.

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

2. Значения суммарной стоимости перевозок при переходе от одной матрицы к другой связаны соотношением

,

где k - номер итерации, и находятся на шагах 3 и 6 соответственно.

Решим транспортную задачу, заданную матрицей перевозок

Пункты					Запасы
	1	2	4	1
	2	3	1	5
	3	2	4	4
Потребности

Решение поставленной задачи:

Решаем по алгоритму. Последовательный переход от матрицы к матрице отображен в таблице (з.1) - (з.3).

Таблица 2.1

Пункты					Запасы
	1 30	2 20	4 ?	1 ?
	2 ?	3 10	1 10	5 10
	3 ?	2 ?	4 ?	4 10
Потребности

1. Найдем начальный план перевозок методом северо-западного угла.

( в табл. з.1 ставятся точки)

Его стоимость

Найдем потенциалы, составляя для каждой базисной клетки уравнение

.

Положим . Тогда для базисных клеток (1,1) и (1,2) получаем

Отсюда

Далее для базисных клеток (2,2) и (2,3)

Отсюда

Рассмотрим последние базисные клетки (2,4) и (3,4)

Отсюда

Для каждой свободной клетки вычислим относительные оценки:

Проанализируем относительные оценки, Так как условия окончания не выполнено, то найдем наименьшую отрицательную оценку:

Для клетки (1,4) построим означенный цикл. Все его вершины кроме данной находятся в базисных клетках. Знак “+” ставится в свободной клетке (1,4).

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

Таблица 2.2

Пункты					Запасы
	1 30	2 10	4 ?	1 10
	2 ?	3 20	1 10	5 ?
	3 ?	2 ?	4 ?	4 10
Потребности

Стоимость

Найдем потенциалы. Для базисных клеток (1,1), (1,2) и (1,4) получаем

Поскольку , то

Остальные потенциалы найдем аналогично: рассмотрев клетки (2,2), (2,3) и (3,4). .

Для каждой свободной клетки вычислим относительные оценки:

Т.к. условие окончания не выполнено, находим наименьшую отрицательную оценку: Для клетки (3,2) строим означенный цикл.

Находим Выполняем сдвиг по циклу на число Результат сдвига представлен в табл. з.3.

Таблица 2.3

Пункты					Запасы
	1 30	2 0	4 ?	1 20
	2 ?	3 20	1 10	5 ?
	3 ?	2 10	4 ?	4 ?
Потребности

Стоимость

Аналогично найдем потенциалы в базисных клетках и вычислим относительные оценки в свободных клетках:

Поскольку все , задача решена, оптимальный план перевозок найден. Т.к. , задача решена, оптимальный план перевозок методом потенциалов найден:



.

Затраты уменьшены на 60 единиц относительно начального или опорного плана перевозок.

2. Планирование работы снегоуборочной автомобильной спецтехники

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

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

	Участок A	Участок B	Участок C	Участок D	Участок E
АК 1	1200	1250	850	900	1350
АК 2	1250	950	1250	850	700
АК 3	1400	1000	1200	1050	850
АК 4	1350	850	800	750	1200
АК 5	1300	650	1300	1050	1300
АК 6	1500	850	1000	1250	700

Требования городских участков (кол-во машин):

Требуемое количество	79	28	61	77	72

Комбинаты в состоянии предоставить (кол-во машин):

Планируется отправить
65
46
52
29
28
67

Решение поставленной задачи:

Сначала проверяется, сбалансирована ли задача, так как дисбаланс сразу нужно будет учесть при правильной организации данных листе Excel. Общее количество снегоуборочных машин , которые можно вывезти с автокомбината - 287 штук. Общий заказ дорожных - служб бригад (участков) - 317 машин.

В задаче имеется дисбаланс потребностей и запасов. Размер дисбаланса - 30 машин.

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

	Участок A	Участок B	Участок C	Участок D	Участок E	Запасы
АК1	1200	1250	850	900	1350	65
АК2	1250	950	1250	850	700	46
АК3	1400	1000	1200	1050	850	52
АК4	1350	850	800	750	1200	29
АК5	1300	650	1300	1050	1300	28
АК6	1500	850	1000	1250	700	67
АК Х	0	0	0	0	0	30
Потребности	79	28	61	77	72
	Участок A	Участок B	Участок C	Участок D	Участок E
АК1
АК2
АК3
АК4
АК5
АК6
АК Х

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

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

Суммарная стоимость всех перевозок и есть целевая функция задачи.

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

	Участок A	Участок B	Участок C	Участок D	Участок E	Запасы
АК 1	1200	1250	850	900	1350	65
АК 2	1250	950	1250	850	700	46
АК 3	1400	1000	1200	1050	850	52
АК 4	1350	850	800	750	1200	29
АК5	1300	650	1300	1050	1300	28
АК6	1500	850	1000	1250	700	67
АК Х						30
Потребности	79	28	61	77	72	251 950
	Участок A	Участок B	Участок C	Участок D	Участок E	Запасы
АК 1	4	0	61	0	0	0,0E+00
АК 2	0	0	0	46	0	0,0E+00
АК 3	45	0	0	2	5	0,0E+00
АК 4	0	0	0	29	0	0,0E+00
АК5	0	28	0	0	0	0,0E+00
АК 6	0	0	0	0	67	0,0E+00
АК Х	30	0	0	0	0	0,0E+00
Потребности	0	0	0	0	0

Вывод

План составлен, общие издержки - 251 950 руб. - минимальные из всех возможных при выполнении заказов бригад.

Можно видеть, не повезло только дорожной службе, работающей на участке

А. Все недопоставленные машины пришлись на их долю (перевозки от поставщика АК Х).

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах. - М., Высшая школа, 1986.

2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М., 2006

3. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. - М., Высшая школа, 2002.

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