Введение 4
Глава 1. Теоретические основы решения задачи транспортного типа 6
1.1 Постановка транспортной задачи замкнутого типа и методы её решения 6
1.2 Постановка транспортной задачи с фиксированными доплатами 9
1.3 Приближенный метод, основанный на искусственном создании вырожденности 10
1.4 Приближенный метод, основанный на сведении задачи к целочисленной 11
Глава 2. Сравнение двух методов 13
2.1 Тестовые примеры метода, основанного на искусственном создании вырожденности. 13
2.2 Тестовые примеры метода, основанного на сведении задачи к целочисленной 22
2.3 Сравнительный анализ двух исследуемых методов 31
Глава 3. Программная реализация приближенных методов 35
3.1 Разработка интерфейса программы 35
3.2 Работа программы 36
Заключение 44
Список использованных источников 45
Приложение
С каждым годом тема выпускной работы становится все актуальнее, так как она связана с перевозкой товаров из одного пункта в другой и с минимизацией затрат на перевозку. Уверена, что даже в далёком будущем будет существовать спрос на товары и необходимость в их доставке транспортом, а главное в планировании перевозок грузов. Конечно, некоторые предпринимают попытки осуществлять доставку дронами или роботами, без участия человека. Но на это потребуется гораздо больше затрат. Во-первых, необходимо организовать их работу, чтобы дроны не сталкивались с посторонними предметами, птицами или друг с другом. Во-вторых, не обойтись без инженеров, которые бы их обслуживали в случае поломки. В-третьих, данный способ доставки вряд ли будет возможен в нашей стране: это связано и с погодными условиями, и с российским менталитетом.
Всё больше людей предпочитают заказывать товары в интернетмагазинах, поэтому уже сейчас доставка одежды, бытовой техники, продуктов питания очень популярна среди обычных граждан. Поставщики, в свою очередь, устраивают различные акции, побуждающие людей делать заказ на большую сумму и именно у них, например, магазины или рестораны делают доставку бесплатной либо дают скидку на следующий заказ, если совершить покупку свыше определённой суммы. Но проблема, связанная с затратами на транспортировку товаров в пределах одного города или района, не так глобальна. Когда же транспортируются товары из города в город практически через всю страну, тогда возникает необходимость в минимизации расходов. Расходы складываются из цен на топливо, аренды самих транспортных средств, заработной платы людям, которые непосредственно доставляют товар, постройки или ремонта автомагистрали, по которой совершаются перевозки грузов и тому подобное. Люди ищут различные способы решения для минимизации затрат на перевозку товаров от поставщика потребителю.
Наиболее распространённой задачей, которая решает данную проблему, является всем известная классическая транспортная задача. Однако в целевой функции этой задачи учитываются лишь прямые затраты на перевозку товаров, то есть те затраты, которые связаны только со стоимостью перевозки единицы груза из одного пункта в другой, но в ней не учитываются косвенные затраты. К косвенным затратам могут относиться аренда и ремонт транспортного средства, затраты на строительство магистралей, по которым будут перевозиться данные грузы, другие затраты, не зависящие от грузопотока. Когда к прямым затратам прибавляются косвенные, целевая функция становится нелинейной, и способ решения обычной транспортной задачи уже не подойдёт.
Целью выпускной работы является численное исследование методов решения одной задачи транспортного типа. Особенность задачи состоит в том, что её ограничения имеют тот же вид, что и у классической транспортной задачи замкнутого типа, а целевая функция вогнута. В отличие от классической эта задача не имеет эффективных точных методов решения. Требуется программно реализовать два приближенных метода её решения, основанных на специфике ограничений, и исследовать на тестовых примерах эффективность этих методов.
В выпускной бакалаврской работе исследованы два приближенных метода решения транспортной задачи с доплатами: метод искусственной вырожденности и метод Балинского. С целью исследования была разработана программа в MS Visual Studio, Windows Forms, с помощью которой можно решить транспортную задачу с доплатами любым из двух приближенных методов, вводя данные вручную либо из файла.
У каждого из исследуемых методов свои достоинства и недостатки. Тестовые расчёты показали, что метод Балинского в большинстве случаев даёт результат лучше по значению целевой функции. Однако, решив ту же задачу методом искусственной вырожденности, можно получить значение общих затрат на перевозку грузов меньше, чем методом Балинского, если правильно подобрать значение, используемого в алгоритме параметра А (шаг вырождения). Достоинством метода Балинского является то, что при решении используются известные всем методы решения классической транспортной задачи, например, таковым является метод потенциалов. Достоинством метода искусственной вырожденности считается то, что для его реализации необходима лишь одна функция, содержащая алгоритм искусственного вырождения задачи.
Параметр А для получения минимального значения целевой функции рекомендуется брать больше или равным максимальной разнице между объёмами производства ai и объёмами потребления bj, если количество поставщиков и потребителей разное, и меньше максимальной разницы между объёмами производства ai и объёмами потребления bj, если количество поставщиков совпадает с количеством потребителей.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
