Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2018-01-05 | 587 |
5.00
из
|
Заказать работу |
|
|
Теорема Кенига. Если к стоимостям какой-либо строки (столбца) задачи о назначениях прибавить одно и тоже число, то оптимальный план не изменится.
Алгоритм решения, основанный на этой теореме:
1) выбрать в каждой строке минимальный элемент и вычесть его из всех элементов этой строки;
2) если в каком-нибудь столбце не появилось нулей, то из всех элементов такого столбца вычитается минимальный элемент этого столбца;
3) рассматривается множество нулей таблицы и, если оно допустимо, то задача решена, иначе переходим к пункту 4;
4) минимальным числом прямых по строкам и столбцам вычеркиваются все нули, а из невычеркнутых элементов выбирается минимальный элемент ;
5) величина вычитается из невычеркнутых и прибавляется к дважды вычеркнутым элементам, после чего переходим к пункту 3.
Замечание. Допустимое множество нулей определяется следующим образом. Нулевой элемент в таблице с номером ij означает возможность выполнения i -тым исполнителем всей работы j. Поэтому расположение нужного количества нулей в таблице должно позволить выбрать единственным способом распределение всех работ между всеми исполнителями.
Сформулируем правило нахождения оптимального решения задачи о назначениях, в которой целевая функция минимизируется. Рассмотрим решение задачи на примере. Пусть задана матрица стоимости выполнения работ, причем для пяти работ имеется пять исполнителей.
1. Выберем в каждой строке матрицы наименьший элемент и вычтем его из каждого элемента этой строки.
2. Выберем столбцы, в которых нет нулей и найдем в них наименьший элемент. Затем вычтем его из каждого элемента столбца.
.
3. Попробуем составить опорное решение из нулей, входящих в полученную матрицу. Но допустимого множества нулей не получено. В частности, выбрав один из нулей во втором столбце, например верхний (работа А 1 распределена второму исполнителю), мы не сможем использовать нижнюю строку с оставшимся нулем. Это означает, что работа А 5 останется нераспределенной.
|
4.
Вычеркиваем все нули, проведя наименьшее число прямых, проходящих через все нули в матрице. Среди незачеркнутых найдем наименьший элемент, это элемент (он дважды подчеркнут в получившейся матрице), вычитаем его из всех невычеркнутых и прибавляем ко всем дважды вычеркнутым.
5. Снова пытаемся составить опорное решение. Допустимое множество нулей получено (выделено двойным подчеркиванием). Из таблицы следует, что первый исполнитель выполняет работу 5, второй – работу 1 и т.д. Запишем решение в виде матрицы
Возвращаясь к исходной матрице, вычисляем минимальное значение функции цели:
.
Решение задачи максимизации
Известно, что переход от задачи минимизации к задаче максимизации в линейном программировании достигается изменением знака функции цели.
, следовательно, данную задачу на нахождение max можно превратить в задачу минимизации, заменив знаки всех элементов в матрице стоимостей. Далее решение находится методом, рассмотренным выше. Пусть известен доход, который можно получить при назначении каждого исполнителя i (i = 1, 2,…, n) на любую работу j (j = 1, 2,…, n). Найдем распределение исполнителей, которое принесет максимальную прибыль.
Дана матрица
, меняя знаки, имеем:
Прибавим к элементам всех строк модуль максимального элемента в таблице (он равен 26), а затем проделаем шаги 1 и 2.
.
Получили оптимальное решение. Вычислим максимум функции цели, наложив эти нули на исходную матрицу.
,
при этом первый исполнитель выполняет первую работу, второй – четвертую, третий - вторую и т.д.
|
ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
Задача 1. Пусть пять проездных участков железной дороги могут обслуживать локомотивы пяти различных типов. Известен доход , получаемый при назначении локомотива типа i на участок j (матрица С). Требуется найти такое распределение локомотивов по участкам, которое обеспечит максимальный доход.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Красс М.С., Чупрынов Б.П. Математика для экономистов: Учебное пособие. – «Питер Пресс», 2008.
2. Введение в исследование операций: Х.Таха. – М.: Мир, 1985, т.1.1.
3. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высш. школа, 1976.
4. Недвецкая А.И., Толмачева М.А. Линейное программирование: Методическое руководство. УЭМИИТ, Свердловск, 1985.
5. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: Учебник для вузов. – М.: издательство «Дело», 2001.
6.Скачков П.П., Суровцев Г.И., Толмачева М.А. Транспортная задача линейного программирования. Часть 1. Методическая разработка. Из – во УрГАПС,1996.
7.Скачков П.П., Суровцев Г.И., Толмачева М.А. Транспортная задача линейного программирования. Часть 2. Методическая разработка. Из – во УрГАПС, Екатеринбург, 1997.
8. Тимофеева Г.А. Экономико-математические модели управления: Методическое руководство. УрГАПС, Екатеринбург, 2000.
9. Пирогова И.Н., Скачков П.П., Куликова О.В., Суровцев Г.И.
Линейное программирование. Методическое руководство. Из-во УрГУПС, Екатеринбург,2004.
10. Скачков П.П., Пирогова И.Н. Транспортная задача линейного программирования. Методическая разработка. Из – во УрГУПС, Екатеринбург, 2004.
Перминова Елена Анатольевна
Павел Павлович Скачков
Линейное программирование
Методическое руководство
для студентов очной и заочной формы обучения всех специальностей
Редактор С.В. Пилюгина
620034,Екатеринбург, ул. Колмогорова 66, УрГУПС
Редакционно-издательский отдел
Подписано в печать
Бумага писчая №1 Формат 60х84 1/16 Усл.п.л. Уч.-изд.л.
Тираж 200 Цена договорная Заказ
|
|
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!