Решение задач о назначениях с помощью табличных процессоров

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Российская академия народного хозяйства

и государственной службы при Президенте Российской Федерации»

Петропавловский филиал РАНХиГС

Направление бакалаврской подготовки: 081100.62 Государственное и муниципальное управление

Кафедра экономических и социально-гуманитарных наук

Дисциплина: Информационные технологии управления

 

КУРСОВАЯ РАБОТА (ПРОЕКТ)

на тему:«Решение задач о назначениях с помощью табличных процессоров»

 

 

Автор работы:

студент 121-взК группы

заочной формы обучения

И.В.Кузьмина

подпись

 

Руководитель  работы:

А.А.Кайгородова

____________________

оценка

____________________

подпись

 

 

г. Петропавловск-Камчатский 2013 г.

Содержание

 

Введение____________________________________________________

Глава 1. Целочисленное  линейное программирование_____________

1.1 Целочисленное  линейное программирование ____________________

1.2 Способы  решения задач линейного программирования_________

Глава 2 Решение задач о назначениях с помощью табличных процессоров_____________________________________________________

2.1 Постановка  задачи________________________________________

2.2 Решение  задач линейного программирования  с помощью надстройки MS Excel «Поиск  решения»__________________________

Заключение__________________________________________________

Библиографический список_______________________________________

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Задачи и методы, относящиеся к перечисленному кругу вопросов, в литературе именуются по-разному. Наибольшее распространение получил термин «целочисленное программирование», однако встречаются и такие как «дискретное программирование», реже «комбинаторное (или диофантово) программирование».

Наиболее изученными задачами этого класса являются целочисленные  задачи линейного программирования, в которых на все переменные (или  на их часть) наложено дополнительное требование целочисленности. От них  принято отличать так называемые дискретные задачи линейного программирования, в которых область допустимого изменения каждой переменной – не множество целых неотрицательных чисел, а некоторое заданное конечное множество.

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

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

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

3. Другим важным толчком  к построению теории целочисленного программирования стал новый подход к некоторым экстремальным комбинаторным задачам. В них требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. Такие задачи принято называть задачами с альтернативными переменными. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями (например, типа «или – или», «если – то» и т. п.).

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

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

 

Глава 1. Целочисленное линейное программирование

1.1 Целочисленное линейное программирование (ЦЛП) ориентировано на решение задач линейного программирования, в которых все или некоторые переменные должны принимать целочисленные (или дискретные) значения. Несмотря на интенсивные исследования, проводимые на протяжении последних десятилетий, известные вычислительные методы решения задач ЦЛП далеки от совершенства. На сегодня не существует надежных вычислительных алгоритмов решения таких задач.

Виды задач ЛП:

1) задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии (задача об ассортименте);

2) задача на максимум выпуска продукции при заданном ассортименте;

3) задача о смесях (рационе,  диете);

4) транспортная задача;

5) задача о рациональном  использовании имеющихся мощностей;

6) задача о назначениях.

1.2 Способы  решения задач линейного программирования

Постановка  транспортной задачи по критерию стоимости  в матричной форме.

Транспортная задача (ТЗ) формулируется следующим образом. В m пунктах отправления A1,….,Am сосредоточен однородный груз в количествах соответственно a1,….,am единиц. Имеющийся груз необходимо доставить потребителям B1,….,Bn спрос которых выражается величинами b1,….,bn единиц. Известна стоимость сij перевозки единицы груза из i-го пункта отправления в j-й который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.

Для построения экономико-математической модели ТЗ рассмотрим матрицу

 

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

Матрицу Х=[хij]т×п будем называть матрицей перевозок. Предполагается, что все xij≥0. Удельные транспортные издержки (расходы) запишем в форме матрицы C = [cij]m×n и назовем ее матрицей тарифов.

Для наглядности условия  ТЗ можно представить таблицей (табл. 2.1), которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ.

Таблица 2.1

 

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

В математической форме  эти условия можно записать так.

целочисленный отсечение транспортный гомори

       (2.1)

      (2.2)

 

Цель ТЗ — минимизировать общие затраты на реализацию плана перевозок, которые можно представить функцией

 

  (2.3)

 

Итак, математически ТЗ ставится так. Даны система ограничений (2.1) при условии (2.2) и линейная функция (2.3). Требуется среди множества  решений системы (2.1) найти такое  неотрицательное решение, при котором линейная функция (2.3) принимает минимальное значение (минимизируется).

Будем называть план перевозок Х=[хij]т×п допустимым, если он удовлетворяет ограничениям (2.1) и (2.2).

Допустимый план перевозок, доставляющий минимум целевой функции (2.3), называется оптимальным.

 

 Задача  о назначении (проблема выбора, задача  о женихах и невестах)

 

Она является исторически  первой задачей дискретного программирования (опубликована венгерским математиком  Е. Эгервари в 1932 г. как задача транспортного типа).

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

Известна полезность cij связанная с выполнением i-м исполнителем j-й работы.

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

Для составления математической модели задачи обозначим через xij факт назначения или неназначения i-го исполнителя на j-ю работу. Так как количество исполнителей равно количеству работ и каждый из них может быть назначен только на одну работу, то xij должны принимать только два значения: 1 или 0. Такие переменные называют булевыми. Итак,

Приходим к задаче: найти план назначения xij, который максимизирует суммарную полезность назначений:

при следующих ограничениях. Каждый исполнитель назначается  только на одну работу:

       (3.1)

На каждую работу назначается  только один исполнитель

        (3.2)

Условия неотрицательности и целочисленности (булевости):

       (3.3)

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

Задача о назначении имеет самое широкое применение. Например, при закреплении машин за маршрутами, распределении инструментов для обработки различных марок стали, рабочих или бригад и т. д. В каждом конкретном случае математическая модель задачи может иметь специфику. Например, в задаче распределения алгоритмов между вычислительными машинами на ВЦ число распределяемых алгоритмов, как правило, не равно числу машин. При назначении на должности для некоторых исполнителей существуют ограничения. Прежде всего необходимо отметить, что если задача о назначениях ставится при условии получения максимального эффекта, то ее сводят к задаче на минимум. Пусть дана матрица эффективности C=[cij].В каждом столбце найдем максимальный элемент Построим матрицу С'=[ lj-cij ]

Задача

где — область допустимых решений системы (3.1) — (3.3), эквивалентна задаче

В самом деле,

Функция Z' достигает минимума при условии, что Z достигает максимума,

Если в задаче о  назначениях число исполнителей равно числу работ, то говорят  о закрытой модели, в противном случае — об открытой модели задачи о назначениях. Если число m меньше числа исполнителей n (m<n) то вводят n-m фиктивных работ. Считается, что с назначением на фиктивные работы исполнителей не связаны затраты, т. е. соответствующие коэффициенты матрицы потерь равны нулю. В случае же m>n вводят m-n фиктивных исполнителей. Соответствующие элементы cij матрицы потерь можно полагать очень большими («блокируют бесконечностью»).

И еще одна деталь. Если по каким-либо причинам запрещается  выполнение какой-либо работы каким-либо исполнителем, то и в этом случае соответствующую клетку «блокируют бесконечностью» (ставят большую стоимость М). Точное решение задачи о назначениях можно найти венгерским методом, методом динамического программирования и др. Существует также много приближенных методов. Хорошее приближение дает модификация способа Фогеля для определения опорного плана транспортной задачи.

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

 

Найти план закрепления, максимизирующий суммарный эффект.

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

 

которую будем решать на минимум:

Для получения приближенного  решения воспользуемся способом Фогеля для нахождения начального опорного плана транспортной задачи. В каждом ряду матрицы Сi найдем минимальный и ближайший к нему элементы и их разность по абсолютной величине записываем в конце соответствующего ряда справа и снизу (табл.3.1). Находим максимальную из этих разностей (число 5 заключено в рамку). В ряду, соответствующем максимальной разности, находим минимальный элемент . Мысленно вычеркиваем из матрицы (табл. 3.1) строку и столбец, соответствующие этому элементу. Фиксируем полученное назначение. Для нашего примера закрепляем третье транспортное средство за третьим маршрутом, это закрепление в табл. 3.1 подчеркнуто. С оставшейся матрицей поступаем аналогично предыдущему. Все вычисления сведены в табл.3.1.