Размещено на http://www.allbest.ru/

Оглавление

Введение

Глава I

1.1 Метод Гомори. Решения задач целочисленнного программирования

1.2 Метод ветвей и границ и его применение для решения задач коммивояжера

1.3 Системы массового обслуживания СМО с отказами

Глава II

2.1 Текстовая задача. Целочисленное программирование метод Гомори

2.2 Решение задачи методом ветвей и границ

2.3 Решение задачи СМО

Заключение

Список литературы



Введение

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

Дадим основные понятия по теме : «методы принятия управленческих решений.

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

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

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

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

Управленческое решение -- разработка вариантов действий, выбор варианта, его принятие и осуществление.

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

Важнейшие требования к управленческому решению :

· реализуемость

· эффективность, иногда -- оптимальность

Основные признаки управленческого решения :

· наличие альтернатив

· осуществление цели

· волевой акт

Специфические особенности управленческого решения:

· их разработка и реализация требует большого объема финансовых и материальных ресурсов

· высокий уровень воздействия на большие количества людей

· ответственность за принимаемые решения очень высока \

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

Общая структура процесса разработки, принятия и реализации решения может быть представлена в виде схемы. (рис.1.)

Рис. 1

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

Типология задач управления.

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

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

управленческий решение целочисленный программирование



Глава I

1.1 Метод Гомори. Решения задач целочисленного программирования

В общем случае задача целочисленного программирования формулируется следующим образом: найтии максимум или минимум функции

Z(X) =

При условиях

, i-1, 2, … , m,

, j=1, 2, … , т,

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

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



,

где - базисная переменная в уравнении;

- коэффициенты при неизвестных (коэффициенты разложений векторов условий по базису опорного решения);

- свободные переменные в системе уравнений;

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

Тогда дополнительное ограничение имеет вид

- 0,

где - дробная часть ;

-дробная часть .

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

Дробная часть числа находится как разность этого числа и его целой части:

= - ().

Например, для числа целая часть () = 1, дробная часть равна - 1 = . Для числа - целая часть ) = -2, дробная часть равна - - (-2) = . Дробная часть числа всегда неотрицательная и меньше единицы.

В неравенство вводится дополнительная переменная , получается уравнение



- + = 0.

В систему ограничений задачи это ограничение записывается в виде

- = -.

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

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

1.2 Метод ветвей и границ и его применение для решения задач коммивояжера

Постановка задачи. Рассмотрим задачу коммивояжера, которая заключается в определении последовательности объезда n пунктов, при которой требуется минимизировать некоторый критерий эффективности - стоимости проезда, время пути, суммарное расстояние и т.п. Требуется выбрать один или несколько оптимальных маршрутов из (n - 1)! Возможных вариантов. В качестве вариантов решений выбирается последовательность объезда городов, причем допустимыми являются такие варианты, при которых в каждом городе коммивояжер должен побывать ровно один раз и вернуться в исходный пункт.

Пусть дана c_ij - стоимость проезда из i-го города в j-ый. Диагональные элементы данной матрицы стоимостей проезда являются бесконечными. Если некоторые города для коммивояжера недоступны, то соответствующие элементы этой матрицы тоже бесконечны. В качестве варианта решения возьмем матрицу X, состоящую из элементов x_ij. Значение x_ij равно единице, если коммивояжер осуществляет проезд из i-го города в j-ый, и нулю в противном случае. Следовательно, математической моделью задачи коммивояжера является:

V = min

При ограничениях

Алгоритм метода ветвей и границ

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

2. Суммируем все минимальные элементы строк и столбцов, которые вычитали для проведения матрицы. Эта сумма является нижней границей Н множества решений, которая берется в качестве корня дерева решений. Если в каждой строке и в каждом столбце было ровно по одному нулевому элементу, то эти элементы образовали бы оптимальный маршрут, и оптимальная стоимость проезда равнялась бы Н.

3. Если это не так, то по матрице стоимости строят одно звено оптимального маршрута. Если выбирают звено (i,j) (где i- строки, j- номер столбца матрицы стоимостей), то решение не должно содержать других звеньев соответствующих элементам i- ой строки и j- го столбца. Для выбора звена оптимального маршрута, выбираем вершины (i,j), для которых Cij = 0. Рассмотрим маршруты, не содержащие звено (i,j). Пункт i должен быть связан с некоторым другим пунктом и поэтому каждый маршрут, не содержащий узел (i,j) должен содержать звено, у которого стоимость не меньше минимального значения элемента i- ой строки, не считая Cij, равного нулю. Аналогично, для того чтобы в пункт j можно было попасть из некоторого другого пункта, маршрут, не содержащий узел (i,j), должен содержать звено, у которого стоимость не меньше, чем стоимость минимального значения элемента j-го столбца, не считая Cij. Сумму минимальной стоимости в i- ой строке (за исключением Cij) и минимальной стоимости в j-ом столбце (за исключением Cij) называют вторичным штрафом Fij. Значение Fij равно минимальному штрафу, которому мы подвергаемся, если не включаем звено(i,j) в оптимальный маршрут. Если штраф за не использование звена вычислить для всех звеньев, у которых Cij=0, то можно сравнить соответствующие значения Fij и включить текущий маршрут такое звено (i,j), для которого штраф за не использование звена максимальный. То есть включая звено (i,j), мы получаем выигрыш в стоимости, равный максимальному значению Fij. Таким образом, нижняя граница ветви дерева маршрутов, по ветке, не включающий узел (i,j), должна быть ровна сумме текущей нижней границе и максимального штрафа за не использование звена (i,j).

4. Чтобы определить новую нижнюю границу маршрутов, включающих звено (i,j), необходимо преобразовать матрицу стоимости. Если в маршрут включено некоторое звено (i,j), то в дальнейшем мы не рассматриваем i-ю строку и j-ый столбец. Кроме того, звено (i,j) является звеном некоторого ориентированного цикла, и но не может принадлежать этому же маршруту. Последнее условие можно выполнить, положив c_ij=co. Из рассмотрения следует исключить и так называемые запрещенные звенья, с помощью которых в дальнейшем могут быть образованы замкнутые циклы, включающие в себя неполное множество пунктов (могут быть образованы под маршруты) элементы матрицы стоимости, соответствующие этим звеньям, берут равными ?. Нижняя граница для маршрута, содержащего звено (i,j), вычисляется после приведения матрицы, полученной вычеркиванием i-ой строки и j-го столбца, как H с предыдущего уровня и констант приведения (то есть минимумов строк и столбцов, которые вычитались из новой матрицы для получения нулевых элементов в каждой строке и в каждом столбце). Далее процесс выбора звеньев оптимального решения повторяется, пока не построится замкнутый передвижения коммивояжера.

Размещено на http://www.allbest.ru/

H+Fij H₁

6. Построенный таким образом полный маршрут будет оптимальным, если его стоимость не превосходит стоимости любого маршрута, соответствующего другим звеньям дерева решений. Если есть ветви дерева стоимость движения, по которым меньше, чем стоимость движения по оптимальному маршруту, следует возвратиться на эти ветки и просчитать маршруты по ним. Процедуру анализа предыдущих промежуточных точек ветвления, которые могли бы определить более дешевый маршрут, называют возвратом. Матрицу стоимости в данном случае называют матрицей стоимости возврата (в ней в соответствии с веткой отражения звена (m,k), ставится запрещение движения по этому звену c_mk=?). С новой матрицей стоимости возврата выполняют описанные процедуры ветвления и построения границ. В результате выбирают маршрут с наименьшим значением нижней границы.

1.3 Системы массового обслуживания

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

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

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

Основными элементами СМО являются источники заявок, их входящий поток, каналы обслуживания и выходящий поток. Схематически это изображено на рис. 32.1.



В зависимости от характера формирования очереди СМО различают:

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

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

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

По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

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

Рассмотрим в отдельности элементы СМО.

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

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

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

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

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

где -- среднее значение интервала времени между двумя соседними заявками.

Для такого потока заявок время между двумя соседними заявками распределено экспоненциально с плотностью вероятности

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

где v -- интенсивность движения очереди, т.е. среднее число заявок, приходящих на обслуживание в единицу времени:



где _оч -- среднее значение времени ожидания в очереди.

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

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

где _обс -- среднее время обслуживания.

Важной характеристикой СМО, объединяющей л и м, является интенсивность нагрузки

Рассмотрим n-канальные разомкнутые СМО.

СМО с отказами

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

Формулы для расчета установившегося режима

1. Вероятность простоя каналов обслуживания, когда нет заявок (k = 0):

2. Вероятность отказа в обслуживании, когда поступившая на обслуживание заявка найдет все каналы занятыми (k = п):

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

P_обс = 1 - P_отк.

4. Среднее число занятых обслуживанием каналов:

5. Доля каналов, занятых обслуживанием:

6. Абсолютная пропускная способность СМО:



Глава II

2.1 Текстовая задача. Целочисленное программирование метод Гомори

1). Алгоритм:

- производство А

- производство Б

- производство В

Z(x) = 40 + 50 + 10 > max

2). Ограничения:

3 + 2 ?51

+ 4 ?48

3 + 3 + ? 67

3). Введем дополнительные переменные:

В 1м неравенстве смысла (?) переменная ;

Во 2м неравенстве смысла (?) переменная ;

В 3м неравенстве смысла (?) переменная .

3 + 2 + = 51

+ 4 + = 48

3 + 3 + + = 67

	Z(x)	40	50	10	0	0	0
		()	()	()	()	()	()
0	()	3	2	0	1	0	0	51	17	25	-
0	()	1	4	0	0	1	0	48	48	12	-
0	()	3	3	1	0	0	1	51	22	22	67
	-40	-50	-10	0	0	0	0
40	()	1		0		0	0	17	25	-
0	()	0	3	0	-	1	0	31	9	-
0	()	0	1	1	-1	0	1	16	16	16
	0	-	-10		0	0	680
40	()	1	0	0			0		-
50	()	0	1	0	-		0		-
0	()	0	0	1		-	1		6
	0	0	-10	11	7	0	897
40	()	1	0	0			0
50	()	0	1	0	-		0
10	()	0	0	1			1
	0	0	0	2	4	10	964
	0	0	0			0	-1
40	()	1	0	0			0	0
50	()	0	1	0			0	0
10	()	0	0	1			1	0
	0	0	0	2	4	10	0	964
	0	0	0	1	2	0		2
								10

Max (-) = max (680; 600; 670) = 680

Max (-) = max (217; 160) = 217

= (10; 9; 6; 0; 0; 0)

Max Z(x) = 964

Метод Гомори

	Z(x)	40	50	10	0	0	0	0
		()	()	()	()	()	()	()
	Огр.	0	0	0			0	-1
40	()	1	0	0			0	0
50	()	0	1	0			0	0
10	()	0	0	1			1	0
	()	0	0	2	4	10	0	964
	()	0	0	0		1	0		1
40	()	1	0	0		0	0		11
50	()	0	1	0		0	0		9
10	()	0	0	1		0	1		7
	0	0	0		0	10		960

= (11, 9, 7) 40*11+50*9+10*7=440+450+70=960

План

= (9, 7, 6) 9*40+7*50+6*10=360+350+60=770

- 2*40+2*50+10=190

Необходимо увеличить

на 2

на 2

на 1

Ответ: максимальное количество изделий - 960, количество изделий по плану - 770. Разница между максимальным производством изделий и изделиями, выполненными по плану, составила 190.

2.2 Решение задачи методом ветвей и границ

1) Двое друзей собрались в каникулы посетить некоторые страны. Они планируют посетить Канаду, Бразилию, Италию, Испанию, Индию, Грецию. Требуется выбрать один или несколько оптимальных маршрутов из возможных вариантов, при котором получится сократить стоимости проезда. В качестве вариантов решений выбирается последовательность объезда стран, причем допустимым являются такие варианты, при которых в каждой стране друзья должны побывать ровно один раз и вернуться в исходный пункт. 2) Задачу коммивояжера решим методом ветвей и границ.

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

Матрица стоимостей проезда выглядит следующим образом:

Страна	Стоимость проезда
	1	2	3	4	5	6
1. Канада	?	22	26	56	38	60
2. Бразилия	34	?	12	51	37	27
3. Италия	45	33	?	44	47	37
4. Испания	39	7	16	?	57	8
5. Индия	35	56	40	58	?	27
6. Греция	9	20	36	31	18	?

3) Решение задачи с помощью алгоритма метода ветвей и границ:

Шаг 1. Определим минимальные элементы в каждой строке.

Город	Стоимость проезда
	1	2	3	4	5	6	Min
1	?	22	26	56	38	60	22
2	34	?	12	51	37	27	12
3	45	33	?	44	47	37	33
4	39	7	16	?	57	8	7
5	35	56	40	58	?	27	27
6	9	20	36	31	18	?	9

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



Таблица

Город	Стоимость проезда
	1	2	3	4	5	6
1	?	0	4	34	16	38
2	22	?	0	39	25	15
3	12	0	?	11	14	4
4	32	0	9	?	50	1
5	8	29	13	31	?	0
6	0	11	27	22	9	?
Min				11	9

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

Город	Стоимость проезда
	1	2	3	4	5	6
1	?	0	4	23	7	38
2	22	?	0	28	16	15
3	12	0	?	0	5	4
4	32	0	9	?	41	1
5	8	29	13	20	?	0
6	0	11	27	11	0	?

Шаг 2. Определим нижнюю границу дерева решений, для этого найдем сумму всех вычитаемых на предыдущем шаге минимумов:

Н = 22+12+33+7+27+9+9+11 =130

Шаг 3. Оценим штраф за отклонение от каждого нуля приведенной матрицы: F₁₂ = + = 4; F₂₃ = + = 19; F₃₂ = + = 0; F₃₄ = + = 11; F₄₂ = + = 1; F₅₆ = + = 9; F₆₁ = + = 8; F₆₅ = + = 5 Максимальное значение штрафа равно 19 за отклонение от узла (2,3). Следовательно, первым включаем в маршрут движения компании участок 2 3. Если не включать этот участок в путь компании, то значение нижней границы увеличится на 19 и будет равным 130+19 = 149. Шаг 4. Оценим нижнюю границу при выборе узла (2,3). Для этого из последней матрицы вычеркиваем 2-ю строку и 3-ий столбец, при этом запретим возврат из 3-го пункта в 2-ый. Получим:

Город	Стоимость проезда
	1	2	4	5	6
1	?	0	23	7	38
3	12	?	0	5	4
4	32	0	?	41	1
5	8	29	20	?	0
6	0	11	11	0	?

Полученная матрица редуцированна. Значение нижней границы осталось прежним и равно Н = 130.

Шаг 5. Оценим штрафы для нулевых элементов последней приведенной матрицы: F₁₂ = 7; F₃₄ = 15; F₄₂ = 1; F₅₆ = 9; F₆₁ = 8; F₆₅ = 5

Максимальное значение штрафа равно 15 дает отказ от узла (3,4). Следовательно, включаем в маршрут движения компании участок 3 4. При этом отказ от этого участка приводит к увеличению длительности проезда, таким образом, Н+F₃₄ = 130+15 = 145.

Шаг 6. После выбора узла (3,4) вычеркиваем из матрицы стоимостей строку, соответствующую 3-му пункту и 4-ой столбец. Получим матрицу, в которой строка, соответствующая 4-му пункту не содержит нулевого элемента.

Город	Стоимость проезда
	1	2	5	6
1	?	0	7	38
4	32	?	41	1
5	8	29	?	0
6	0	11	0	?
Min		11



После приведения и наложения запретов на образование замкнутых контуров, эта матрица имеет вид:

Город	Стоимость проезда
	1	2	5	6
1	?	0	7	38
4	31	?	40	0
5	8	29	?	0
6	0	11	0	?

Таким образом, Н₁ =130+1 = 131. Шаг 7. Оценим штрафы для нулевых элементов последней приведенной матрицы: F₁₂ = 18; F₄₆ = 31; F₅₆ = 8; F₆₁ = 8; F₆₅ = 7 Таким образом, выбираем узел (4,6), а значение границы дерева решений будет следующим - H+F₄₆ = 131+31=162

Шаг 8. После выбора узла (4,6) вычеркиваем строку, соответствующую 4-му пункту, и столбец, соответствующий 6-му пункту.

Табл.7

Город	Стоимость проезда
	1	2	5
1	?	0	7
5	8	29	?
6	0	?	0
Min		8

В полученной матрице строка, соответствующая 6-му пункту, не содержит нулевого элемента. Получим матрицу:

Город	Стоимость проезда
	1	2	5
1	?	0	7
5	0	21	?
6	0	?	0



Таким образом, Н₁ = 131+8 = 139 для выбора узла (4,6)

Шаг 9. Оценим штрафы для нулевых элементов последней приведенной матрицы: F₁₂ = 7+21=28; F₅₁ = 0+21=21; F₆₁ = 0+0=0; F₆₅ =0+7=7

Таким образом, выбираем узел (1,2), а значение границы дерева решений будет следующим - Н+F₁₂ = 139 + 28 = 167.

Шаг 10. После выбора узла (1,2) вычеркиваем строку, соответствующую 1-му пункту, и столбец, соответствующий 2-му пункту. После привидения и наложения запретов на образование замкнутых контуров, получим матрицу:

Город	Стоимость проезда
	1	5
5	0	?
6	?	0

Шаг 11. В результате получили следующую последовательность объезда городов компанией: причем стоимость проезда по этому пути равна 139. Реализация метода ветвей и границ привела к получению следующего дерева решений:



Шаг 12. Таким образом, последовательность объезда стран коммивояжёром:

1 ---- 2 ---- 3 ---- 6 ---- 5 со стоимостью проезда равной 139 является оптимальным решением.

Проверим полученное решение, путем подстановки полученного маршрута в первоначальную матрицу стоимостей:

Город	Стоимость проезда
	1	2	3	4	5	6
1. Канада	?	22	26	56	38	60
2. Бразилия	34	?	12	51	37	27
3. Италия	45	33	?	44	47	37
4.Испания	39	7	16	?	57	8
5. Индия	35	56	40	58	?	27
6.Греция	9	20	36	31	18	?

Стоимость проезда равна: 22+ 12+44+8+35+18=139.

Ответ: стоимость проезда равна 139.

3.2 Решение задачи СМО

2) Контроль готовой продукции фирмы осуществляют 4 контролера. Если изделие поступает на контроль, когда все контролеры заняты проверкой готовых изделий, то оно остается непроверенным. Среднее число изделий, выпускаемых фирмой, составляет 24 изд./ч. Среднее время на проверку одного изделия 3 мин.

По условию задачи:

л=24 изд./ч. ; t_обс= 3 мин. = 0,05 час

1. Интенсивность потока обслуживания

м = 1/ t_обс = 1/ 0,05 = 20



2. Интенсивность нагрузки каналов

с = л / t_обс = 24 / 20 = 1,2

3. Вероятность, что канал свободен.

Р₀ = (1+ с + + + ) ^-1 = (1+1,2+0,72+0,288+0,0864) ^-1 = = 0,304

Следовательно, 30,4% в течение часа канал будет не занят.

Время простоя t_пр = 18,2 мин.

Вероятность того, что обслуживанием:

занят 1 канал:

Р₁ = (с¹/1!) Р₀ = 1,2* 0,304 = 0,3648

заняты 2 канала:

Р₂ = (с²/2!) Р₀ = 0,72* 0,304 = 0,219

заняты 3 канала:

Р₃ = (с³/3!) Р₀ = 0,288 * 0,304 = 0,0875

заняты 4 канала:

Р₄ = (с⁴/4!) Р₀ = 0.0864 * 0,304 = 0,0262

4. Вероятность отказа

Р_отк = Р_n = (сⁿ/n!)Р₀ = (с⁴/4!) Р₀ = 0,0262

Значит, 3% из числа поступивших заявок не принимаются к обслуживанию.

5. Относительная пропускная способность

Q = Р_обс

Р_отк + Р_обс = 1



Р_обс = 1 - Р_отк = 1 - 0,0262 = 0,974

Следовательно, 97% из числа поступивших заявок будут обслужены.

6. Абсолютная пропускная способность

A = Р_обс л = 0,974*24 = 23,37 заявок/час.

7. Среднее число занятых каналов

k = А/м = 23,37/20 = 1,169

В среднем в течении всего дня занято 1 канал.

Чтобы рассчитать, сколько необходимо контролеров, чтобы Р_обс ? 0,98, произведем аналогичные расчеты для n=5

Р₀ = (1+ с + + + + ) ^-1 = (1+1,2+0,72+0,288+0,0864+0,0208) ^-1 = = 0,3016

Р_отк = Р_n = (сⁿ/n!)Р₀ = (с⁵/5!) Р₀ = 0,3016 * 0,0208 = 0,0063

Р_обс = 1 - Р_отк = 1 - 0,0063 = 0,9937 0,98

Вероятность того, что при n=3 изделий пройдет проверку, составляет 97%, и среднее число занятых каналов составляет 1. Чтобы Р_{обс =} 0,98, необходимо не менее 5 контролеров.



Заключение

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

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

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

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

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



Список литературы

1) Красс М.С., Чупрынов Б.П. Основы математики и её приложения в экономическом образовании. 5-е изд., испр. и доп.-М.: Дело, 2006. - 719 с.

2) Кузнецов Б.Т. Математика. 2-е изд., перераб. и доп.-М.: ЮНИТИ, 2004. - 781 с.

3) Ломакина Л.С., Прохорова Е.С. Разработка управленческих решений. Методологические указания к решению типовых задач: Учебное пособие. - Нижний Новгород, Издательство Волго-Вятской академии государственной службы, 2006. - 36 с.

4) Надеев А.Т., Данилова О.С., Прохорова Е.С. Разработка управленческих решений: Учеб. Пособие. - 2-е изд., испр. И доп. - Н.Новгород: Изд-во Волго-Вятской академии государственной службы, 2007. - 116 с.

5) Глебова Н. В. Применение методов линейного программирования для решения экономических задач: Учебно - методическое пособие для студентов 3 курса ВВАГС, 2001

Размещено на Allbest.ru