Транспортная задача. Решение методом минимального элемента

 

МИНИСТЕРСТВО  СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное образовательное  учреждение  высшего пРофессионального  образованияроссийский государственный аграрный университет – МСха имени К.А. Тимирязева  (ФГОУ ВПО ргау - МСХА имени К.А. Тимирязева)

Учетно-финансовый факультет

Кафедра прикладной информатики

 

 

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

по  теме: «Транспортная задача. Решение методом минимального элемента»

 

 

 

Выполнил:

Студент 107 группы

дневного отделения,

учетно-финансового  ф-та

Оганесян  Евгений Зарзандович

Преподаватель:

Белоярская  Татьяна Сергеевна,

старший преподаватель

кафедры прикладная информатика

 

 

МОСКВА  2013

 

 

 

 

 

 

 

Введение.

 

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

Каждый  из методов имеет ряд своих  общих черт и недостатков.

В качестве потребности могут рассматриваться  овещствительные потребности: люди, транспорт, средства труда и т. д.

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

К этим задачам приводится широкий круг вопросов планирования экономических и техника - экономических процессов, где ставится задача поиска наилучшего решения. Существует несколько типов линейного программирования:

1.задача  о комплексном использовании  сырья;

2.задача  о загрузке оборудования;

3.задача  текущего производственного планирования;

4.задача  перспективного оптимального планирования;

5.задача  планирования экономического комплекса.

Задача  будет не линейной, если указанные  функции не соответствуют.

 

Глава 1.Методика расчета транспортной задачи методом минимального элемента.

1.1.Сущность задачи.

 

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

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

В случаи превышения запаса над потребностью, т.е.

 

  ,

 

вводится фиктивный (n+1)-й пункт назначения с потребностью

 

 

 

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

Если в опорном плане  число отмеченных от нуля компонент  рано в точности n+m-1, то план является невыраженным, а если меньше, то выражены.

 

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

 

Под моделированием понимают изучение объекта  не непосредственно, а косвенно при  помощи изучения вспомогательных объектов, которые называются моделями. Модель – это образ или прообраз изучаемого объекта.

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

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

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

Рассмотрим общую модель транспортной задачи:

 

Станция отправления	Запасы груза	Пункты назначения и их потребности  в грузе
		В1	В2	В3	В4
		в1	в2	в3	в4
А1	a1	c11 x11	c12 x12	c12 x13	c14 x14
А2	a2	c21 x21	c22 x22	c23 x23	c24 x24
А3	a3	c31 x31	c32 x32	c33 x33	c34 x34

 

Задача минимального элемента состоит  в определение такого плана перевозок, при котором удовлетворяла:

1. был бы точно удовлетворён спрос в каждом пункте назначения B1, B2, B3, B4;
2. был бы вывезен весь груз со станций отправления A1, A2, A3;
3. общие транспортные расходы были бы наименьшими.

 Описание задачи описана в пункте “сущность задачи”.

Из таблицы составим расход при плане перевозок:

 

Z=c11x11+c21x21+c31x31+c12x12+c22x22+c32x32+c13x13+c23x23+

с33x33+c14x14+c24x24+c34x34,

 

 можно записать короче

 

,

 

где

I-пункт отправления

J-пункт назначения

Xij-количество единиц груза перевезённого из i-го в j-ый пунк назначения

Cij-тарифы перевозок

 

Определение 1: всякое неотрицательное решение систем линейных уравнений (2) и (3), определимое матрицей X=(xij)(i=1, m)(j=1,n), называется планом транспортной задачи.

Определение 2: план x*=(x*ij) (i=1,m;j=1,n), при котором функция (1) принимает своё минимальное значение, называется оптимальным планом транспортной задачи.

 

Общее наличие груза  у поставщиков равно , а общая потребность в грузе пунктах назначения равна . Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах направления, то есть

 

,

 

то модель называется закрытой, иначе открытой.

 

Глава 2. Разработка программного расчета  транспортной задачи методом минимального элемента.

2.1. Блок-схема расчета транспортной задачи методом минимального элемента.

 

 Рисунок 1. Ввод данных.

2.3 Контрольный пример.

 Смысл моей задачи: На четырёх складах оптовой базы сосредоточен однородный груз в количествах 100, 250, 200, и 300 единиц. Груз необходимо перевезти в четыре магазина, каждый из магазинов должен получить соответственно 200, 200, 100, 100 и 250 единиц груза. Тарифы перевозок единицы груза из каждого из складов во все магазины. Задача задаётся матрицей:

 

 

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

 

	200	200	100	100	250
100	10 -	7 -	4  -	1 100	4  -
250	2 200	7 50	10 -	6  -	11 -
200	8 -	5 -	3 -	2 -	2 200
300	11 -	8 150	12 100	16 -	13 50

 

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

После находим число F:

F=1*100+2*200+50*7+2*200+150*8+100*12+50*13=4300 единиц.

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

F удовлетворяет потребностям. План является минимальным.

 

2.4. Описание входной и выходной информации.

 

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

 

	200	200	100	100	250
100	10 -	7 -	4  -	1 100	4  -
250	2 200	7 50	10 -	6  -	11 -
200	8 -	5 -	3 -	2 -	2 200
300	11 -	8 150	12 100	16 -	13 50

 

При помощи этих данных находим минимальный элемент по поставщикам и по потребителям. Входная информация представлена в приложение

Результат нахождения метода в приложение

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

 

 

 

Заключение

Программа предназначена для нахождения минимального элемента транспортной задачи, а именно для того чтобы найти более оптимальный план перевозок. Программа может быть использована при проведение практических работ по предмету “Компьютерное моделирование”. Эта математическая модель анализирует ситуацию.

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

 

 

Литература

 

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

Издательство "экономика" 1985 год, Хазанов В.В. Математическое моделирование в экономике.

Издательство "экономика" 1976 год, Хруцкий Е.А. “”Экономико  – технические методы в планирование материально – технического снабжения”

 

Приложение