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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...............................................................................................................3

Глава 1. ПОСТАНОВКА ЗАДАЧИ В ОБЩЕМ ВИДЕ И МЕТОДЫ ЕЕ РЕШЕНИЯ.................................................................................................................5

1.1. Общая математическая формулировка транспортной задачи ……………...5

1.2. Общая математическая формулировка транспортной задачи о назначениях…………………………………………………………………………………….7

1.3. Методы решения транспортной задачи о назначениях………….……........11

Глава 2. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ И ЕЕ РЕШЕНИЕ……………………………………………………………………………...…15

2.1. Постановка транспортной задачи о назначениях…………………………...15

2.2. Решение транспортной  задачи о назначениях «Венгерским методом»…...16

2.3. Решение транспортной задачи о назначениях с помощью средств Microsoft Excel (функция «Поиск решения»)…………………………………………….…22

2.4. Интерпретация результатов расчетов и выработка управленческого решения ………………………………………………….……………….……………...25

ЗАКЛЮЧЕНИЕ…………………………………………………………………..31

Список использованных источников…………………………………………….33

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

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

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

1.  Математическая формулировка  ЗЛП о назначениях;

2.  Общая постановка  ЗЛП о назначениях;

3. Рассмотрение методов решения задач линейного программирования;

4. Решение задачи вручную;

5. Решение задачи с использованием Excel;

6. Анализ отчета и выработка решения.

Объектом данного исследования является ателье-студия АЛЛЮР, занимающееся производством детских платьев, при этом предметом исследования является планирование производства двух видов детских платьев.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ В ОБЩЕМ ВИДЕ И МЕТОДЫ ЕЕ РЕШЕНИЯ

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

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

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

Исходные параметры  модели ТЗ:

1) - количество пунктов отправления, - количество пунктов назначения.

2) - запас продукции в пункте отправления [ед. тов.].

3) - спрос на продукцию в пункте назначения [ед. тов.].

4) - тариф (стоимость) перевозки единицы продукции из пункта

отправления в пункт назначения [руб./ед. тов.].

Искомые параметры  модели ТЗ:

1. - количество продукции, перевозимой из пункта отправления в пункт назначения .

2. L(X) - транспортные расходы на перевозку всей продукции [руб.].

Этапы построения модели:

I. Определение  переменных.

II. Проверка  сбалансированности задачи.

III. Построение  сбалансированной транспортной  матрицы.

IV. Задание целевой функции (ЦФ).

V. Задание ограничений.

Транспортная  модель:

.       (1)

Ограничения:

        (2)

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

 

 

 

 

 

 

 

 

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

Задача о  назначениях – это распределительная задача (РЗ), в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задачу о назначениях является частным случаем ТЗ, в которой претенденты представляют «исходные пункты», а вакансии – «пункты назначения». Стоимость «перевозки» равна баллу, набранному i – м претендентом при тестировании на j – ю вакансию. Формулировки задачи о назначениях могут быть самыми разными, но это всегда связано с выбором лучшего исполнителя для работы.

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

Исходные параметры  модели задачи о назначениях:

1. – количество ресурсов, – количество работ.

2. =1 – единичное количество ресурса , например: один работник; одно транспортное средство; одна научная тема и т.д.

3. =1 – единичное количество работы , например: одна должность; один маршрут; одна лаборатория.

4. – характеристика качества выполнения работы с помощью ресурса . Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

Искомые параметры:

1. – факт назначения или не назначения ресурса на работу :

= 0, если i-й ресурс не назначен на j-ю работу,

= 1, если i-й ресурс назначен на j-ю работу.

2. L(X) – общая (суммарная) характеристика качества распределения ресурсов по работам.

Таблица 1.2(1)

Общий вид транспортной матрицы задачи о назначениях

Ресурсы,	Работы,				Количество  ресурсов
					1
					1
					1
Количество  работ	1	1		1

 

Модель задачи о назначениях:

.       (3)

 

 

Система ограничений:

        (4)

Специфическая структура задачи о назначениях  позволила разработать так называемый "Венгерский метод" ее решения. Поэтому, хотя в Excel такие задачи решаются обычным симплекс-методом, в лабораторной работе требуется построить модель задачи о назначениях вида (3). В некоторых случаях, например, когда – это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ, в отличие от (3). В этом случае ЦФ (X) заменяют на (X)= (X) и решают задачу с ЦФ (X)→min , что равносильно решению задачи с ЦФ (X)→max .

 

РЕКОМЕНДАЦИИ  К РЕШЕНИЮ ЗАДАЧИ О НАЗНАЧЕНИЯХ

1. Процесс приведения  задачи о назначениях к сбалансированному  виду имеет свои особенности по сравнению с ТЗ. Если условие сбалансированности задачи не выполняется из-за нехватки работ или исполнителей в количестве kab , то для создания баланса надо ввести такое же количество kab фиктивных строк или столбцов.

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

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

4. Значения "тарифов"  выбираются в зависимости от направления оптимизации ЦФ задачи о назначениях (L(X)→max или L(X)→min ). При этом руководствуются принципом "невыгодности" запрещенных назначений.

Так, если L(X) –  это общая компетентность работников, то в качестве запрещающих надо выбирать нулевые компетентности . А если L(X) – это общее время прохождения машинами транспортных маршрутов, то в качестве запрещающих надо выбирать значения , превосходящие по величине максимальные реальные значения .

5. При решении  задач о назначении в Excel необходимо учитывать, что переменные являются булевыми.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.3. Методы решения  транспортной задачи о назначениях

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

Метод северо-западного угла: этот метод позволяет найти допустимое базисное решение, такое, что количество ненулевых решений = n+m-1 и, при этом, будут выполняться все ограничения задачи. Составление плана начинается с верхнего левого угла таблицы (северо-западный угол). В этот угол ставится такой объем поставки, который позволял бы вычеркнуть из таблицы либо строку, либо столбец из дальнейшего рассмотрения. После этого определяется таким же образом поставка груза в левую верхнюю клетку новой (полученной) таблицы и так до тех пор, пока мы не зачеркнем все столбцы и строки.

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

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