Вход

Применение методов линейного программирования

Курсовая работа*
Код 102288
Дата создания 2016
Страниц 21
Источников 5
По техническим причина покупка готовых работ временно недоступна.
1 520руб.

Содержание

Введение 2
Транспортная задача 3
Задача о назначениях 14
Задача СМО 17
Заключение 20
Литература 21

Фрагмент работы для ознакомления

Решение ищем, используя венгерский метод.
Проводим редукцию матрицы по строкам. В каждой строке исходной матрицы ищем минимальный элемент и отнимаем его от всех элементов строки:
0 3 1 4 0 8 5 7 0 1 4 5 9 17 3 1 6 9 7 0 14 1 4 2 3 0 3 12 1 8 3 2 2 1 0 1 7 2 8 6 1 3 12 5 6 4 0 5 10 13 0 4 7 1 5 5
Затем такую же операцию редукции проводим по столбцам, получая в итоге полностью редуцированную матрицу:
0 3 1 4 0 7 5 0 1 4 5 9 16 3 6 9 7 0 14 0 4 3 0 3 12 1 7 3 2 1 0 1 7 1 8 1 3 12 5 6 3 0 10 13 0 4 7 0 5 0 0 0 0 0 1 0
Далее методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость:
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем. 
Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 2 и столбце 1 вычеркиваем. 
Фиксируем нулевое значение в клетке (3, 4). Другие нули в строке 3 и столбце 4 вычеркиваем. 
Фиксируем нулевое значение в клетке (4, 2). Другие нули в строке 4 и столбце 2 вычеркиваем. 
Фиксируем нулевое значение в клетке (5, 3). Другие нули в строке 5 и столбце 3 вычеркиваем. 
Фиксируем нулевое значение в клетке (6, 7). Другие нули в строке 6 и столбце 7 вычеркиваем. 
Фиксируем нулевое значение в клетке (7, 6). Другие нули в строке 7 и столбце 6 вычеркиваем. 
В итоге получаем следующую матрицу:
[-0-] 3 1 4 [0] 7 5 [0] 1 4 5 9 16 3 6 9 7 [0] 14 [-0-] 4 3 [0] 3 12 1 7 3 2 1 [0] 1 7 1 8 1 3 12 5 6 3 [0] 10 13 [-0-] 4 7 [0] 5
Количество найденных нулей равно k = 7. В результате получаем эквивалентную матрицу:
0 3 1 4 0 7 5 0 1 4 5 9 16 3 6 9 7 0 14 0 4 3 0 3 12 1 7 3 2 1 0 1 7 1 8 1 3 12 5 6 3 0 10 13 0 4 7 0 5
Далее методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения:
[-0-] 3 1 4 [0] 7 5 [0] 1 4 5 9 16 3 6 9 7 [0] 14 [-0-] 4 3 [0] 3 12 1 7 3 2 1 [0] 1 7 1 8 1 3 12 5 6 3 [0] 10 13 [-0-] 4 7 [0] 5
Минимальная стоимость назначения:
Cmin = 7 + 1 + 2 + 2 + 6 + 5 + 6 = 29
Задача СМО
Дано:
, , ,
В данном случае реализуется случай многоканальной СМО без ожидания (с отказами). Рассчитаем основные характеристики такой системы.
Интенсивность проверок изделий:
Интенсивность нагрузки системы контроллеров:
Вероятность того, что система контроллеров будет свободной (равна доли времени простоя системы):
Таким образом, в течение каждого часа система в среднем будет простаивать без работы
Вероятность того, что из заняты будут контроллер системы:
(3.1)
Из (3.1) находим соответствующие вероятности. Вероятность того, что занят будет ровно 1 контроллер:
Вероятность того, что заняты будут ровно 2 контроллера:
Вероятность того, что заняты будут ровно 3 контроллера:
Вероятность того, что заняты будут ровно 4 контроллера:
Вероятность того, что заняты будут ровно 5 контроллера:
Поскольку в последнем случае все 5 контроллеров заняты, то вероятность представляет собой вероятность того, что изделие не пройдет проверку:
В рассматриваемой СМО с отказами события отказа и проверки составляют полную группу событий, т.е.
где – вероятность обслуживания (проверки изделия). Итак, искомая вероятность того, что изделие пройдет проверку:
Итак, в среднем приблизительно изделий пройдет проверку.
Среднее число контроллеров, занятых проверкой:
Среднее число простаивающих контроллеров:
Абсолютная пропускная способность системы контроллеров:
Найдем теперь число контроллеров, необходимых для того, чтобы вероятность проверки (обслуживания) изделия была не ниже . Вероятность того, что система из контроллеров осуществит проверку изделия:
Итак, для нахождения числа нужно решить неравенство:

(3.2)
Неравенство (3.2) является трансцендентным относительно , поэтому решать его будем путем прямого перебора возможных значений , начиная с единицы. В табл.№3.1 представлены результаты расчетов для . Как видно, условие (3.2) начинает выполняться при . Итак, искомое число каналов системы контроллеров равно 8.
Таблица №3.1
1 3,0333E+00 1 3,0333 2 9,2009E+00 2 4,6005 3 2,7909E+01 6 4,6515 4 8,4657E+01 24 3,5274 5 2,5679E+02 120 2,1399 6 7,7892E+02 720 1,0818 7 2,3627E+03 5040 0,4688 8 7,1668E+03 40320 0,1777 9 2,1739E+04 362880 0,0599 10 6,5941E+04 3628800 0,0182
Заключение
В работе были рассмотрены и решены две задачи линейного программирования (транспортная задача и задача о назначениях), а также задача, посвященная многоканальной СМО без ожидания. Соответствующие методы, которые были использованы при решении этих задач: метод потенциалов, венгерский метод и методы теории вероятностей и математической статистики.
Литература
1. А.В. Кузнецов, Н.И. Холод, Л.С Костевич. Руководство к решению задач по математическому программированию. Минск, «Вышэйшая школа», 1978
2. Дж. Данциг. Линейное программирование, его применения и обобщения. Издательство, Москва, «Прогресс», 1966
3. Хемди А. Таха. гл 5.4 Задача о назначениях. // Введение в исследование операций. 7-е издание. Пер. с англ. Москва, «Вильямс», 2005
4. Harold W. Kuhn, «Variants of the Hungarian method for assignment problems», Naval Research Logistics Quarterly, 3: 253–258, 1956.
5. Е.С. Вентцель, Л.А. Овчаров. Теория вероятностей. Москва, «Наука», 1969
20

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


1. А.В. Кузнецов, Н.И. Холод, Л.С Костевич. Руководство к решению задач по математическому программированию. Минск, «Вышэйшая школа», 1978
2. Дж. Данциг. Линейное программирование, его применения и обоб-щения. Издательство, Москва, «Прогресс», 1966
3. Хемди А. Таха. гл 5.4 Задача о назначениях. // Введение в исследование операций. 7-е издание. Пер. с англ. Москва, «Вильямс», 2005
4. Harold W. Kuhn, «Variants of the Hungarian method for assignment problems», Naval Research Logistics Quarterly, 3: 253–258, 1956.
5. Е.С. Вентцель, Л.А. Овчаров. Теория вероятностей. Москва, «Наука», 1969
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала, который не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, но может использоваться в качестве источника для подготовки работы указанной тематики.
Сколько стоит
консультация по подготовке материалов?
1
Заполните заявку - это бесплатно и ни к чему вас не обязывает. Окончательное решение вы принимаете после ознакомления с условиями выполнения работы.
2
Менеджер оценивает работу и сообщает вам стоимость и сроки.
3
Вы вносите предоплату 25% и мы приступаем к работе.
4
Менеджер найдёт лучшего автора по вашей теме, проконтролирует выполнение работы и сделает всё, чтобы вы остались довольны.
5
Автор примет во внимание все ваши пожелания и требования вуза, оформит работу согласно ГОСТ, произведёт необходимые доработки БЕСПЛАТНО.
6
Контроль качества проверит работу на уникальность.
7
Готово! Осталось внести доплату и работу можно скачать в личном кабинете.
После нажатия кнопки "Узнать стоимость" вы будете перенаправлены на сайт нашего официального партнёра Zaochnik.com
© Рефератбанк, 2002 - 2018