Вход

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

Курсовая работа
Дата создания 14.05.2016
Страниц 21
Источников 5
Вы будете перенаправлены на сайт нашего партнёра, где сможете оформить покупку данной работы.
1 287руб.
КУПИТЬ

Содержание

Введение 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 - 2017