Решение транспортной задачи закрытого типа методом «наименьшей стоимости»

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

Федеральное агентство по образованию 

Федеральное государственное образовательное  учреждение

среднего профессионального образования

 Соликамский горно-химический  техникум

 

 

 

 

 

                                                               Отделение дневное

                                                                     Специальность 230105

 

 

 

 

 

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

типа методом «наименьшей стоимости»

Курсовой проект

 

КП 230105 00.00.00 ПЗ

 

 

 

 

 

 

 

Студент         

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

                                          

Нормоконтроль       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Соликамск 2010

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

1 ОБЩАЯ ЧАСТЬ

1.1 Математическая постановка  задачи 7 

1.2 Методы решения транспортной задачи закрытого типа

( в том числе метод минимальной стоимости) 14

1.3 Производственно-транспортная задача 17

2 АЛГОРИТМ РЕШЕНИЯ  ТРАНСПОРТНОЙ ЗАДАЧИ 18

3 БЛОК-СХЕМА

3.1 Транспортная задача 23

3.2 Метод минимальной  стоимости 24

4 ФОРМЫ ВХОДНОЙ ИНФОРМАЦИИ 25

5 ФОРМЫ ВЫХОДНОЙ ИНФОРМАЦИИ 26

6 ИНСТРУКЦИЯ ДЛЯ ПОЛЬЗОВАТЕЛЯ 27

7 ИНСТРУКЦИЯ ДЛЯ ПРОГРАММИСТА 28

ЗАКЛЮЧЕНИЕ 30

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

ПРИЛОЖЕНИЕ (ЛИСТИНГ ПРОГРАММЫ) 32

 

ВВЕДЕНИЕ

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

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

Ввиду длительности истории  изучения транспортной задачи накоплено  большое количество программного обеспечения для ЭВМ предыдущих поколений, но современных ПЭВМ распространенных программ, позволяющих наглядно и быстро решать различные разновидности транспортных задач неизвестно . Поэтому представляется перспективным использование электронных таблиц EXCEL, с помощью которых, на основе встроенного языка BASIC, создать программную среду для решения некой конкретной транспортной задачи, а перспективе -  и целого класса задач[1].

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

Задачи:

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

Целью данного курсового  проекта является решение транспортной задачи

методом минимальной стоимости, и составление программы на ЭВМ. 
1 ОБЩАЯ ЧАСТЬ

1.1 Математическая постановка задачи

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

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

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

Транспортную задачу по критерию стоимости представим в  виде таблицы, где указаны поставщики А₁, А₂, …, А_т, у которых имеется в наличии соответственно а₁, а₂, …, а_т единиц однородного груза. Данный груз должен быть доставлен n потребителям В₁, В₂, …, В_n в количествах b₁, b₂, …, b_n единиц. Заданы стоимости с_ij перевозок единицы груза от i-го поставщика j-му потребителю (Cij- удельная стоимость).

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

 

Таблица 1- Исходные данные

Поставщики	Потребители				Запас груза ai
	B1	B2	…	Bn
A1	c11	c12		c1n	a1
	x11	x12	…	x1n
A2	c21	c22		c2n	a2
	x21	x22	…	x2n
…	…	…	…	…	…
Am	cm1	cm2		cmn	am
	xm1	xm2	…	xmn
Потребность в грузе bj	b1	b2	…	bn

 

Исходные данные задачи могут быть представлены также в  виде вектора запасов поставщиков А=(а₁,а₂,…,а_m), вектора запасов потребителей В=(b₁,b₂,…,b_n) и матрицы стоимостей

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

, (1.1.1)

называются закрытыми (сбалансированными), а задачи с отсутствием баланса между ресурсами и потребностями:

, (1.1.2)

 

называются открытыми (несбалансированными).

Для составления математической модели задачи введем переменные х_ij= , обозначающие количество единиц груза перевозимого от i-го поставщика j-му потребителю. Очевидно, что таких переменных m*n и они должны удовлетворят следующим условиям:

1. ограничения по запасам:

;    (1.1.3)

2. ограничения по потребностям:

;   (1.1.4)

3. условия неотрицательности:

х_ij

.(1.1.5)

Суммарные транспортные затраты на перевозки

. (1.1.6)

Таким образом, математически  транспортная задача представляется так. Найти m*n переменных величин х_ij, удовлетворяющих системам уравнений (1.1.3), (1.1.4) и условиям неотрицательности (1.1.5), для которых целевая функция (1.1.6) принимает минимальное значение. Следовательно, целевая функция имеет вид  

Необходимым и достаточным  условием решения транспортной задачи в области допустимых решений является условие (1.1.3).

Особенности систем (1.1.4), (1.1.5):

1. коэффициенты при неизвестных во всех уравнениях равны единице;
2. каждая переменная встречается только в двух уравнениях;
3. система уравнений транспортной задачи симметрична относительно всех переменных x_ij;
4. матрица, составленная из коэффициентов при переменных х_ij состоит из единиц и нулей, причем каждый столбец матрицы содержит два элемента, равных единице, а остальные – нулю.

При решении транспортной задачи важное значение имеет теорема о ранге матрицы: ранг матрицы транспортной задачи на единицу меньше числа уравнений:

r=m+n-1, (1.1.7)

  где m – число поставщиков; n – число потребителей[3].

Из данной теоремы  следует, что каждое опорное решение  системы ограничений транспортной задачи должно иметь n-r=mn-(m+n-1)=(m-1)(n-1) свободных переменных, равных нулю, и r=m+n-1 базисных переменных.

Если число базисных клеток удовлетворяет условию m+n-1, то план перевозок называют невырожденным, а если число занятых клеток не удовлетворяет этому условию, то план перевозок называют вырожденным.

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

1. определение исходного опорного плана;
2. оценка этого плана;
3. переход к следующему плану путем однократной замены одной из базисных переменных на свободную.

Существуют различные  способы реализации приведенных  этапов решения транспортной задачи. Сюда можно отнести:

• правило «северо-западного угла»;
• правило «минимального элемента»;
• метод потенциалов и др.

 

Пример №1: построить начальное опорное решение транспортной задачи, используя метод минимальной стоимости, исходные данные которой приведены в таблице 2.

Таблица 2 – Исходные данные

Поставщики	Потребители				Запас груза ai
	B1	B2	B3	B4
A1	2	1	2	2	50
A2	1	3	4	4	40
A3	3	4	5	1	20
Потребность в грузе bj	15	35	20	40

 

Находим минимальную  оценку и рассматриваем соответствующего поставщика и потребителя. Если минимальных оценок несколько, то заполняем одну из клеток. Запасы 1-го поставщика уменьшаем на 35, то есть а₁=а₁-в₂=50-35=15. Исключаем из рассмотрения первого потребителя, так как его запросы удовлетворены. Максимально возможная перевозка, которую можно осуществить от 1-го поставщика одному из  потребителей, равна 15.