Решение задач на распределения механизмов среди участков с минимальными затратами различными методами

Введение

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

1. Общие сведения
2. Условия применения
3. Выходная информация
4. Входная информация
1. Нормативно-справочная информация
2. Оперативная информация
5. Описание задачи
1. Назначения разработки
2. Описание алгоритма
1. Основные положения задач оптимизации
2. Математическая модель
3. Блок-схема
4. Описание блок-схемы
6. Список литературы
7. Приложение 1. Техническое задание

7.2 Приложение 2. Инструкция по эксплуатации  задачи

7.3 Приложение 3. Описание контрольного  примера

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Общие сведения

Настоящая программа  разработана для выполнения оптимизационного распределения продукции между  участками работ. Продукцией является механизм. Потребителями- рабочие участки. Программа выполнена в табличном  процессоре Excel и может быть использована для решения задачи с максимальным количеством выпускаемой продукции – 9 и максимальным количеством потребителей продукции – 5. Результатом решения задачи является оптимальное распределение механизмов по участкам работ.

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

 

2. Условия применения
1. Для решения задачи требуется компьютер с минимальными параметрами

• Процессор 100 Гц
• Оперативная память 64 Мб
• Жесткий диск 1 Гб
• Подключение компьютера к сети не обязательно

2. Задача может эксплуатироваться при:

• Оперативная система не ниже Windows 98
• Табличный процессор Microsoft Office Excel не ниже 2002

 

 

3.  Входная и выходная информация

Входная и выходная информация предоставлена  в виде реквизитов:

• Количество механизмов A_i
• Количество участков B_j
• Производительность механизмов C_ij
• Оптимальное распределение механизмов K_ij
• Min потребности в механизмах D_ij

 

 

 

 

 

Табл.1

Наименование	Обозначение	Формат	Тип
Количество механизмов	Ai	Числовой (1.0)	Оперативная
Количество участков	Bj	Числовой (1.0)	Оперативная
Производительность механизмов	Cij	Числовой (4.0)	Нормативно-справочная
Оптимальное распределение механизмов	Kij	Числовой (3.0)	Оптивная
Min потребности в механизмах	Dij	Числовой (2.0)	Оперативная

 

 

4. Описание задачи

1. Назначение разработки

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

Программа должна соответствовать следующим условиям:

• Число рабочих участков Уi от 1 до 5
• Число механизмов Мi от 1 до 9

 

2.  Описание алгоритма
1. Основные положения задач оптимизации

 

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

• Необходимо выбрать наилучшее решение (оптимальный план) из множества возможных;
• Решения можно выразить как набор значений некоторых переменных величин;
• Ограничения, накладываемые на допустимые решения специфическими условиями задач, формулируются в виде линейных уравнений или неравенств;
• Цели выражаются в виде линейной функции, зависящей от основных переменных.

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

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

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

При условиях:

 

            

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

 

       

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

• Линейная задача общего типа;
• Транспортная задача;
• Линейная задача целочисленная;
• Дробно-линейная задача;
• Линейная задача, зависящая от параметров.

 

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

 

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

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

Под названием  «Транспортная задача» объединяется широкий круг задач с единой математической моделью, имеющий вид:

 

Математическую  модель можно сформулировать следующим  образом:

Среди множества  решений систем уравнений (5.5) и (5.6) и  неравенство (5.7) требуется найти  решение, которое обеспечивает достижение функцией (5.4) минимума.

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

Особенности состоят в следующем:

• Коэффициенты при переменных в ограничительных уравнениях равны единице или нулю;
• Каждая переменная встречается только в двух или только двух ограничительных уравнениях; один раз в системе ограничений по запасам (5.5), в другой раз в системе ограничений по потребностям (5.6)
• Система ограничительных уравнений симметрична относительно всех переменных

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

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

Условие  означает, является задача с правильным или неправильным балансом. Переменная Х_ij означает количество груза перевозимого от производителя А_i до потребителя B_j. Совокупность этих величин образует  матрицу перевозок. Для решения транспортной задачи необходимо кроме запасов и потребностей знать тарифы, то есть стоимость доставки груза от конкретного производителя конкретному потребителю. Совокупность тарифов С_ij так же образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу 5.

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

• Формирование начального опорного плана;
• Оценка опорного плана;
• Улучшение опорного плана.

4.2.1.1 Формирование начального опорного плана может выполняться одним из трех методов:

• Метод северо-западного Первой загружается клетка (1.1) Если закрывается строка, то следующей закрывается клетка (2.1), если столбец, то клетка (1.2). Таким образом, загружается клетка соседняя либо по строке, либо по столбцу. Последней будет загружена клетка (m.n). В результате загруженными будут клетки, расположенные по диагонали (1.1) – ( m;n).
• Метод минимального элемента. Первой загружается клетка с наименьшим тарифом, далее загружается клетка из того же столбца (строки) со следующим по величине тарифом и так до полного распределения.
• Метод Фогеля. Прежде всего, по каждой строке и каждому столбцу находят разности двух наименьших тарифов. Их этих разностей выбирается наибольшая и в соответствующей строке (столбце) загружается клетка с наименьшим тарифом. Закрывшаяся строка (столбец) исключается из дальнейшего рассмотрения. Описанная операция повторяется до тех пор пока не закроются все строки и столбцы. Если наибольшая разность окажется в нескольких строках или столбцах, то выбирается та строка (столбец), где придется загружать наименьший тариф. Если эти показатели будут одинаковыми, то выбирают клетку, в которую придется записать большую поставку.

 

 

 

4.2.1.2 Оценка опорного плана может выполняться следующими методами:

• Распределительный метод. Заключается в том, что для каждой свободной клетки строят цикл и вычисляют их оценку по формуле

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

• Метод потенциалов. Потенциалами U_i и V_j поставщиков A_i и потребителей В_j являются компоненты оптимального плана задачи

Из этого  следует, что если в распределительной  таблице выполняется равенство  U_i+V_j=C_ij для каждой свободной клетки, то из этого следует, что план оптимален. Оценки свободных клеток связаны с потенциальной зависимостью

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