Ирина Эланс

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

Математические методы решения задачи о получении оптимального плана перевозок (транспортной задачи)

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГО»

Колледж радиоэлектроники имени П. Н. Яблочкова

МАТЕМАТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ

наименование курсовой работы (проекта)

О ПОЛУЧЕНИИ ОПТИМАЛЬНОГО ПЛАНА

прописными буквами

ПЕРЕВОЗОК (ТРАНСПОРТНОЙ ЗАДАЧИ)

курсоваЯ РАБОТА

Специальность 230105 «Программное обеспечение вычислительной

техники и автоматизированных систем»

шифр, полное наименование

Студента курса группы .

фамилия, имя, отчество

Руководитель,

преподаватель _________________ .

подпись, дата инициалы, фамилия

Председатель

предметной

(цикловой) комиссии __________________ .

подпись, дата инициалы, фамилия

Саратов 2012 .

год

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГО»

Колледж радиоэлектроники имени П. Н. Яблочкова

ПРИНЯТО

на заседании цикловой

(предметной) комиссии

Протокол от _____ №____

ЗАДАНИЕ

на курсовую работу

Специальность 230105 «Программное обеспечение вычислительной .

техники и автоматизированных систем»

шифр, полное наименование

Тема МАТЕМАТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ

полное наименование темы, прописными буквами

О ПОЛУЧЕНИИ ОПТИМАЛЬНОГО ПЛАНА ПЕРЕВОЗОК

(ТРАНСПОРТНОЙ ЗАДАЧИ)

студента курса группы .

фамилия, имя, отчество

Саратов 2012 .

год

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

1 ТРАНСПОРТНАЯ ЗАДАЧА КАК ЧАСТНЫЙ СЛУЧАЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5

1.1 Постановка транспортной задачи 5

1.2 Метод северо-западного угла нахождения опорного решения 8

1.3 Метод потенциалов нахождения оптимального решения 8

2 РЕШЕНИЕ ЗАДАЧИ О ПОЛУЧЕНИИ ПЛАНА ГРУЗОПЕРЕВОЗОК 11

2.1 Математическая модель задачи 11

2.2 Получение опорного плана грузоперевозок 14

2.3 Получение оптимального плана грузоперевозок 15

3 РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ НАДСТРОЙКИ EXCEL «ПОИСК РЕШЕНИЯ» 24

3.1 Табличное представление модели 24

3.2 Настройка модели 26

3.3 Решение задачи 28

3.4 Анализ решения 28

ЗАКЛЮЧЕНИЕ 30

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 31

Срок выполнения курсовой работы ________________

число, месяц, год

Руководитель,

преподаватель ________________ .

подпись, дата инициалы, фамилия

Председатель

предметной

(цикловой) комиссии ________________ .

подпись, дата инициалы, фамилия

ВВЕДЕНИЕ

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

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

Внедрение математических методов оптимального планирования перевозок грузов на автомобильном транспорте начато в середине XX века. Большая заслуга в разработке и внедрении математических методов на транспорте принадлежит отечественному ученому Л.В.Кантаровичу и его последователям.

Целями настоящей курсовой работы являются:

- систематизация и закрепление полученных теоретических знаний и практических умений по дисциплине «Математические методы»;

- углубление теоретических знаний по теме «Транспортная задача»;

- формирование умений использовать справочную литературу;

- развитие творческой инициативы, самостоятельности, ответственности и организованности;

- подготовка к итоговой государственной аттестации.

В работе приводится теоретический материал на тему «Транспортная задача», решение задачи о получении оптимального плана грузоперевозок, описывается технология использования электронных таблиц Excel для нахождения оптимального решения

1 ТРАНСПОРТНАЯ ЗАДАЧА КАК ЧАСТНЫЙ СЛУЧАЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1 Постановка транспортной задачи

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

Каждому потребителю нужно некоторое количество единиц этого груза (спрос потребителя). Известны затраты на перевозку единицы груза от каждого из поставщиков к каждому из потребителей.

Нужно составить такой план перевозок от поставщиков к потребителям, при котором:

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

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

, , …, в количествах , , …, . Известны стоимости перевозок единицы груза из А_i пункта отправления в B_j пункт назначения.

Обозначим общее количество имеющегося в наличии груза

а потребности в грузе –

В зависимости от значений a и b различают два типа транспортных задач:

Если a = b, имеем закрытую модель, или модель, удовлетворяющую условию баланса. В этой модели суммарный объем груза у поставщиков (суммарная мощность поставщиков) равен суммарному спросу потребителей.

Если – открытую модель или модель с нарушенным балансом. Здесь различают два случая.

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

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

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

Сформулируем закрытую транспортную задачу в общем виде.

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

Пункты отправления	Пункты назначения	Запасы
Пункты отправления		Запасы




Потребности		a = b

Математически задачу можно сформулировать следующим образом. Определить переменные ,которые минимизируют суммарную стоимость перевозок

и удовлетворяют системе ограничений:

– с каждого пункта отправления груз должен быть вывезен полностью;
– потребитель должен получить ровно столько, сколько ему требуется;

Остановимся на решении закрытой транспортной задачи. Порядок решения для закрытой модели:

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

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

1.2 Метод северо-западного угла нахождения опорного решения

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

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

1.3 Метод потенциалов нахождения оптимального решения

Метод потенциалов является модификацией симплекс - метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого опорного решения, получить оптимальное решение за конечное число итераций.

Алгоритм метода потенциалов состоит в следующем. После построения опорного плана все переменные транспортной задачи разбиваются на две группы:

– базисные переменные (заполненные клетки);

– свободные переменные (незаполненные клетки).

Функция стоимости перевозок выражается через свободные переменные следующим образом:

(*)

здесь – номер итерации

Для нахождения коэффициентов каждому пункту отправления ставится величина , – потенциал пункта .

Для каждой заполненной клетки составляется уравнение , где – стоимость перевозки единицы груза из пункта в пункт .

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

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

Если все величины будут неотрицательными, то исходное решение является оптимальным.

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

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

Условимся отмечать знаком «плюс» те вершины цикла, в которых перевозки необходимо увеличить, а знаком «минус» – те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть означенным. Перенести какое-то количество единиц груза по означенному циклу – это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по-прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце – заявке этого столбца.

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

2 РЕШЕНИЕ ЗАДАЧИ О ПОЛУЧЕНИИ ПЛАНА ГРУЗОПЕРЕВОЗОК

2.1 Математическая модель

У поставщиков сосредоточено соответственно 60, 40, 20 единиц некоторого однородного груза, который необходимо добавить потребителям ,,, в количестве 40, 30, 30 и 50 единиц. Данные о стоимости перевозок единицы груза от поставщиков к потребителям приведены в таблице. Составить такой план перевозок от поставщиков к потребителям, при котором суммарные затраты на перевозку груза будут минимальны.

Пункты отправления	Пункты назначения				Запасы
Пункты отправления	B₁	B₂	B₃	B₄	Запасы
A₁	2	3	5	1	60
A₂	3	4	9	4	70
A₃	2	5	2	5	20
Потребности	40	30	30	50	150

Обозначим через количество единиц груза, перевозимого из пункта в пункт

Тогда

2ден. ед. – стоимость перевозки груза из в ,

3ден. ед. – стоимость перевозки груза из в ,

5ден. ед. – стоимость перевозки груза из в ,

ден. ед. – стоимость перевозки груза из в ,

3ден. ед. – стоимость перевозки груза из в

4ден. ед. – стоимость перевозки груза из в ,

9ден. ед. – стоимость перевозки груза из в ,

2_ден. ед. – стоимость перевозки груза из в ,

5ден. ед. – стоимость перевозки груза из в ,

2_ден. ед. – стоимость перевозки груза из в ,

5 ден. ед. – стоимость перевозки груза из в .

Суммарная стоимость перевозок равна:

(2₊3₊5_{++3+4+9+2+2+5+2+5)} ден. ед.

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

2₊₃₊5_{++3+4+9+2+2+5+2+5}

Опишем систему ограничений:

1) (2 + 3_{+ 5}+ ₎ ед. груза – мощность поставщика ,

(3+ 4_{+ 9} + 2₎ед. груза – мощность поставщика ,

(2 x₃₁+ 5 x₃₂ + 2 x₃₃ + 5 x₃₄) ед. груза – мощность поставщика .

Так как мощности поставщиков ограничены и заданы условием задачи, то:

2) (2 + + ) ед. груза – потребность пункта ,

(+ + )ед. груза – потребность пункта ,

(+ + ) ед. груза – потребность пункта ,

( + + ) ед. груза – потребность пункта .

Так как потребности пунктов ,,, в грузе ограничены и заданы условием задачи, то:

3) Условие неотрицательности

Таким образом, математическая модель задачи имеет вид:

=(2_+3+5++3+4+9+

+2_+2+5+2+5)

при ограничениях:

Суммарная мощность поставщиков равна: 60+70+20=150 (ед. груза)

Суммарный спрос потребителей равен: 40+30+30+50=150 (ед. груза)

Это закрытая модель.

2.2 Получение опорного плана грузоперевозок

Для составления исходного плана перевозов используем метод северо-западного угла:

Пункты отправления	Пункты назначения				Запасы
Пункты отправления	B₁	B₂	B₃	B₄	Запасы
A₁	2 40	3 20	5	1	60
A₂	3	4 10	9 30	4 30	70
A₃	2	5	2	5 20	20
Потребности	40	30	30	50	150

Стоимость перевозок по этому плану

2.3 Получение оптимального плана грузоперевозок

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

Полагая, например, , найдем:

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

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

Определим новое базисное решение.

Минимальной разностью является для клетки (3, 3). Отрицательная оценка показывает, что при включении в данную свободную клетку каждой единицы груза общая стоимость уменьшается на 8 единицы. Для определения количества груза , подлежащего распределению, построим замкнутый цикл (указан пунктиром в таблице). Одна из вершин цикла находится в незанятой клетке (3, 3), которую отмечаем знаком «плюс». Все остальные вершины цикла находятся в базисных клетках, с чередующимися знаками «минус» и «плюс».


Пункты	B₁	B₂	B₃	B₄	Запасы
A₁	2 40	3 20	5	1	60
A₂	3	4 10	9 – 30	4 + 30	70
A₃	2	5	2 +	5 – 20	20
Потребности	40	30	30	50	150

Найдем значение , равное наименьшему из чисел, стоящих в отрицательных вершинах цикла. Значение записываем в незанятую клетку. Двигаясь далее по означенному циклу, вычитаем из объемов перевозок, расположенных в клетках, которые обозначены знаком «минус», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «плюс». Элементы таблицы, не входящие в цикл, остаются без изменений. В результате получаем новую таблицу:


Пункты	B₁	B₂	B₃	B₄	Запасы
A₁	2 40	3 – 20	5 +	1	60
A₂	3	4 + 10	9 – 10	4 50	70
A₃	2	5	2 20	5	20
Потребности	40	30	30	50	150

Стоимость перевозок по этому плану

Исследуем базисное решение на оптимальность.

Вычислим потенциалы и , исходя из базисных переменных:

Полагая, например, , найдем:

,
,
,

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

Условие оптимальности плана перевозок не выполняется, так как одна из оценок отрицательна.

Определим новое базисное решение.

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

В клетку (1, 3) поместим груз .

После преобразований получаем новый план перевозок:


Пункты	B₁	B₂	B₃	B₄	Запасы
A₁	2 40	3 – 10	5 10	1 +	60
A₂	3	4 + 20	9	4 – 50	70
A₃	2	5	2 20	5	20
Потребности	40	30	30	50	150

Стоимость перевозок по этому плану

Исследуем базисное решение на оптимальность.

Вычислим потенциалы и , исходя из базисных переменных:

Полагая, например, , найдем:

,
,
,

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

Условие оптимальности плана перевозок не выполняется, так как одна из оценок отрицательна.

Определим новое базисное решение.

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

В клетку (1, 4) поместим груз .

После преобразований получаем новый план перевозок:


Пункты	B₁	B₂	B₃	B₄	Запасы
A₁	2 – 40	3	5 10	1 + 10	60
A₂	3 +	4 30	9	4 – 40	70
A₃	2	5	2 20	5	20
Потребности	40	30	30	50	150

Математические методы решения задачи о получении оптимального плана перевозок (транспортной задачи) 📙 Курсовая → 🆔 121077