Главная Учебники - Разные Лекции (разные) - часть 65
Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40-х и 50-х годов. Последующие полтора десятилетия были отмечены широким применением полученных фундаментальных теоретических результатов к разнообразным практическим задачам и связанным с этим переосмыслением потенциальных возможностей теории. В результате исследование операций приобрело черты классической научной дисциплины, без которой немыслимо базовое экономическое образование. Обращаясь к задачам и проблемам, составляющим предмет исследования операций, нельзя не вспомнить о вкладе, внесенном в их решение представителями отечественной научной школы, среди которых в первую очередь должен быть назван Л. В. Канторович, ставший в 1975 г. лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике. Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Среди первых исследований в данном направлении может быть названа работа Л. В. Канторовича "Математические методы организации и планирования производства", вышедшая в 1939 г. В зарубежной литературе отправной точкой обычно считается вышедшая в 1947 г. работа Дж. Данцига, посвященная решению линейных экстремальных задач. Следует отметить, что не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Часто при ответе на данный вопрос говорится, что "исследование операций
представляет собой комплекс научных методов для решения задач эффективного управления организационными системами". Второе определение: Исследование операций
– это научная подготовка принимаемого решения – это совокупность методов, предлагаемых для подготовки и нахождения самых эффективных или самых экономичных решений. Природа систем, фигурирующих в приведенном определении под именем "организационных", может быть самой различной, а их общие математические модели находят применение не только при решении производственных и экономических задач, но и в биологии, социологических исследованиях и других практических сферах. Кстати, само название дисциплины связано с применением математических методов для управления военными операциями. Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. Как правило, это: 1. Постановка задачи. 2. Построение содержательной (вербальной) модели рассматриваемого объекта (процесса). На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия. 3. Построение математической модели, т. е. перевод сконструированной вербальной модели в ту форму, в которой для ее изучения может быть использован математический аппарат. 4. Решение задач, сформулированных на базе построенной математической модели.
5. Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели. 6. Реализация полученного решения на практике. Центральное место в данном курсе отведено вопросам, относящимся к четвертому пункту приведенной выше схемы. Это делается не потому, что он является самым важным, сложным или интересным, а потому, что остальные пункты существенно зависят от конкретной природы изучаемой системы, в силу чего для действий, которые должны производиться в их рамках, не могут быть сформулированы универсальные и содержательные рекомендации. В самых разнообразных областях человеческой деятельности встречаются сходные между собой задачи: организация производства, эксплуатация транспорта, боевые действия, расстановка кадров, телефонная связь и т.д. Возникающие в этих областях задачи сходны между собой по постановке, обладают рядом общих признаков и решаются сходными методами. Пример
: Организуется какое-то целенаправленное мероприятие (система действий), которое можно организовать тем или иным способом. Необходимо выбрать определенное решение из ряда возможных вариантов. Каждый вариант имеет преимущества и недостатки – сразу не ясно, какой из них предпочтительнее. С целью прояснить обстановку и сравнить между собой по ряду признаков различные варианты, организуется серия математических расчетов. Результаты расчетов показывают, на каком варианте остановится. Математическое моделирование
в исследовании операций является, с одной стороны, очень важным и сложным, а с другой - практически не поддающимся научной формализации процессом. Заметим, что неоднократно предпринимавшиеся попытки выделить общие принципы создания математических моделей приводили либо к декларированию рекомендаций самого общего характера, трудноприложимых для решения конкретных проблем, либо, наоборот, к появлению рецептов, применимых в действительности только к узкому кругу задач. Поэтому более полезным представляется знакомство с техникой математического моделирования на конкретных примерах. 1) План снабжения предприятия.
Имеется ряд предприятий, использующих различные виды сырья; имеется ряд сырьевых баз. Базы связаны с предприятиями различными путями сообщения (железные дороги, автотранспорт, водный, воздушный транспорт). Каждый транспорт имеет свои тарифы. Требуется разработать такой план снабжения предприятий сырьем, чтобы потребности в сырье были удовлетворены при минимальных расходах на перевозки. 2) Постройка участка магистрали.
Сооружается участок железнодорожной магистрали. В нашем распоряжении определенное количество средств: людей, техники и т.п. Требуется назначить очередность работ, распределить людей и технику по участкам пути таким образом, чтобы завершить строительство в минимальные сроки. 3) Выборочный контроль продукции.
Выпускается определенный вид изделий. Для обеспечения высокого качества продукции требуется организовать систему выборочного контроля: определить размер контрольной партии, набор тестов, правила отбраковки и т.д. Требуется обеспечить заданный уровень качества продукции при минимальных расходах на контроль. 4) Военные действия.
Целью в данном случае является уничтожение вражеского объекта. Подобные задачи встречаются в практике часто. Они имеют общие черты. В каждой задаче определена цель – цели эти похожи; заданы некоторые условия – в рамках этих условий и нужно принять решение, чтобы данное мероприятие было наиболее выгодным. В соответствии с этими общими чертами применяются и общие методы. 1.1. Цель и основные понятия в исследованиях операций
Операция –
это всякая система действий (мероприятие), объединенных единым замыслом и направленных к достижению какой-то цели. Это управляемое мероприятие, то есть от нас зависит, каким способом выбрать некоторые параметры, характеризующие его организацию. Каждый определенный выбор зависящих от нас параметров называется решением.
Целью исследования операций
является предварительное количественное обоснование оптимальных решений. Те параметры, совокупность которых образует решение, называются элементами решения.
В качестве элементов решения могут быть различные числа, векторы, функции, физически признаки и т.д. Пример
: перевозка однородного груза. Существуют пункты отправления: А1
, А2
, А3
,…, А
m
. Имеются пункты назначения: В1
, В2
, В3
,…, В
n
. Элементами решения здесь будут числа xij
,
показывающие, какое количество грузов будет отправлено из i-того пункта отправления в j
-ый пункт назначения. Совокупность этих чисел: x
11
,
x
12
,
x
13
,…,
x
1
m
,…,
xn
1
,
xn
2
,…,
xnm
образует решение. Чтобы сравнить между собой различные варианты, необходимо иметь какой-то количественный критерий – показатель эффективности (W
). Данный показатель называется целевой функцией.
Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Выбирая решение, стремимся, чтобы данный показатель стремился к максимуму или к минимуму. Если W – доход, то W Если выбор зависит от случайных факторов (погода, отказ техники, колебания спроса и предложения), то в качестве показателя эффективности выбирается среднее значение – математическое ожидание – В качестве показателя эффективности иногда выбирают вероятность достижения цели. Здесь цель операции сопровождается случайными факторами и работает по схеме ДА-НЕТ. Для иллюстрации принципов выбора показателя эффективности вернемся к рассмотренным ранее примерам: 1) План снабжения предприятия.
Показатель эффективности виден в цели. R
– число – стоимость перевозок, 2) Постройка участка магистрали.
В задаче большую роль играют случайные факторы. В качестве показателя эффективности выбирают среднее ожидаемое время окончания стройки 3) Выборочный контроль продукции.
Естественный показатель эффективности, подсказанный формулировкой задачи – это средние ожидаемые расходы на контроль за единицу времени, при условии, что система контролирует обеспечение заданного уровня качества. 4) Военные действия.
Операция должна быть спланирована так, чтобы уничтожить вражеский объект. В качестве целевой функции – вероятность того, что произойдет событие А (уничтожение). Р(А) 1.2. Основные элементы метода исследования операций
При решении любой конкретной задачи применение методов исследования операций заключается в следующем: построение математических, экономических и статистических моделей для задач принятия решений и управления в сложных ситуациях в условиях неопределенности (наличие случайных факторов); изучение взаимосвязей, определяющих возможные последствия принятых решений. Установление критериев эффективности, позволяющих оценить преимущества того или иного варианта. Методы исследования операций обладают рядом специфических черт. Чтобы подход к решению задач можно было считать операционным, он должен содержать следующие элементы: 1. Ориентация на принятие решений
. Основные результаты анализа должны иметь непосредственное и полностью определенное отношение к выбору способа действий (стратегии или тактики); 2. Оценка на основе критерия экономической эффективности
. Сравнение различных возможных вариантов действий должно основываться на количественных оценках, позволяющих однозначно определить полезность ожидаемого исхода. Количественные оценки для коммерческих фирм обычно предполагают использование таких измеримых величин, как расходы, доходы, наличие денежных средств, норма прибыли от дополнительных капиталовложений и т.д. В рекомендуемом решении должен быть достигнут оптимальный баланс с учетом всех, нередко противоречивых факторов; 3. Доверие математической модели
. Процедуры обращения с упомянутыми выше параметрами должны быть определены настолько точно, чтобы любой специалист в области системного анализа смог их трактовать совершенно однозначно. Другими словами: опираясь на одни и те же данные, различные специалисты должны получить одинаковые результаты. 4. Необходимость использования ЭВМ
. Это условие отнюдь не является лишь желательным, оно скорее необходимо. Это обуславливается сложностью используемых математических моделей и большим объемом исходных данных. Вычисления могут быть громоздкими – необходимо использовать ЭВМ; а могут быть несложными, но в больших объемах (статистические модели). Основные этапы применения метода ИО:
1. определение цели; 2. составление плана разработки проекта; 3. формулировка проблемы; 4. построение модели; 5. разработка вычислительного метода; 6. разработка технического задания на программирование, само программирование и отладка программы; 7. сбор данных; 8. проверка модели; 9. реализация результатов, то есть принятие решения. 1.3. Основные задачи, решаемые методом исследования операций. Классификация задач
Накопленный опыт в решении задач исследования операций и его систематизация позволили выделить следующие типы задач: задачи управления запасами, задачи распределения ресурсов, задачи ремонта и замены оборудования, задачи массового обслуживания, задачи упорядочивания, задачи сетевого планирования и управления (СПУ), задачи выбора маршрута, комбинированные задачи. 1. Задачи управления запасами.
Этот класс задач в настоящее время наиболее распространенный, а главное, изученный. Эти задачи имеют следующую особенность: с ростом запасов, увеличиваются расходы на их хранение, но снижаются потери, связанные с возможной их нехваткой. Следовательно, одна из задач управления запасами заключается в определении такого уровня запасов, который минимизирует следующие критерии: сумма ожидаемых затрат на хранение, сумма потерь из-за дефицита. В зависимости от условий, задачи управления запасами делятся на 3 группы: а)
моменты поставок или оформления заказов на поставки, пополнение запасов фиксированы. Определить объемы производимой или закупаемой партии запасов; б)
объемы производимой или закупаемой партии запасов фиксированы. Определить моменты оформления заказов на поставки; в)
моменты оформления заказов и объемы закупаемых партий запасов нефиксированы. Определить эти величины, исходя из минимальных затрат и минимальных потерь из-за дефицита. 2. Задачи распределения ресурсов.
Эти задачи возникают тогда, когда существует определенный набор операций (работ), которые необходимо выполнить, а наличия ресурсов для выполнения операций наилучшим образом не хватает. В зависимости от условия задачи эти также делятся на 3 группы: а)
заданы работы и ресурсы. Распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности (прибыль) или минимизировать ожидаемые затраты (издержки производства). Пример
: известны производственное задание и производственные мощности предприятия. При существующих различных способах получения изделия, ограничения по мощности не позволяют для каждого изделия использовать наилучшую технологию. Какие способы производства надо выбрать, чтобы выполнить задание с минимальными затратами? б)
заданы только наличные ресурсы. Определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности. Пример
: задано предприятие с определенными производственными мощностями. Какую продукцию следует производить, чтобы получить максимальный доход? в)
заданы только работы. Определить, какие ресурсы необходимы для того, чтобы минимизировать суммарные издержки производства. Пример
: известно месячное расписание движения полетов пассажирских самолетов на авиалинии. Какое количество экипажей необходимо подобрать, чтобы выполнить план с минимальными затратами? 3. Задачи ремонта и замены оборудования.
Производственное оборудование с течением времени изнашивается и подлежит предупредительно-восстановительному ремонту. Оборудование также устаревает (морально и физически) и подлежит полной замене. При этом постановка задачи такова: определить такие сроки ремонта и замены оборудования, при которых минимизируется сумма затрат на ремонт и замену оборудования при его старении. Иногда в оборудовании выходят из строя отдельные элементы (например, микросхемы) – в данном случае требуется определить такие сроки профилактического ремонта по замене вышедших из строя деталей, чтобы потери на данный элемент были минимальными. Здесь также имеет место профилактический контроль по обнаружению неисправностей. Требуется определить такие сроки контроля, при которых минимизируется сумма затрат на проведение контроля, а также минимизируется сумма потерь от простоя оборудования вследствие выхода из строя отдельных элементов. 4. Задачи массового обслуживания.
Данные задачи возникают там, где образуется очередь. С образованием очереди приходится сталкиваться как в производстве, так и в быту (производство: очередность выполнения заказа; в быту: магазин, поликлиника). Подобные задачи существуют и на транспорте. Очередь возникает из-за того, что поток клиентов (заказов) поступает неравномерно и имеет случайный характер. То есть поток клиентов неуправляем. Объект, который обслуживает клиента, называется каналом обслуживания
(продавец, врач, взлетно-посадочная полоса). Если каналов обслуживания много, очереди не образуется, НО
возможны простои каналов обслуживания. Если каналов мало – образуется очередь. А следовательно, возможны затраты, связанные с ожиданием в очереди клиента ми с отказом клиента от обслуживания. В данных задачах возможна следующая постановка: определить, какое количество каналов обслуживания необходимо, чтобы свести к минимуму суммарные затраты, связанные с несвоевременным обслуживанием и простоем каналов. Для решения задач используется теория массового обслуживания. 5. Задачи упорядочивания.
Эти задачи часто встречаются в производстве. Предположим, что в цехе изготавливается множество деталей по разным технологическим маршрутам. В парке оборудования имеется ограниченное число станков (токарный, фрезерный, строгальный и др.). На одном станке в данный момент времени может обрабатываться только 1 деталь. Появляется очередность выполнения работ, то есть появляются детали, ждущие обработки. Время обработки каждой детали обычно известно. Такая задача называется задачей календарного планирования
или составлением расписания работ.
Выбор очередности запуска деталей в обработку является задачей упорядочивания.
В таких задачах в качестве критерия эффективности часто встречаются следующие: минимизация общей продолжительности работ (то есть интервала времени между моментом началом первой операции и моментом окончания последней); минимизация общего запаздывания. Запаздывание определяется как разность фактическим и плановым сроком обработки каждой детали. Общее запаздывание = сумме запаздываний по всем деталям. 6. Задачи сетевого планирования и управления (СПУ).
Данные задачи актуальны при разработке сложных, дорогостоящих проектов. Здесь рассматривается соотношение между сроком выполнения крупного комплекса операций и моментом начала всех операций отдельно в комплексе. Для строгой постановки задачи необходимо выполнить следующие условия: Должно существовать точно определяемое количество операций, Множество операций по комплексу упорядочено так, что должно быть известно для каждой операции какие операции ей предшествуют, а какие следуют за ней, В пределах заданного упорядочивания операций, операции можно начинать и заканчивать независимо друг от друга, Известна взаимосвязь между ресурсами на выполнение операции и ее продолжительностью. Если все условия выполнены, возможны следующие постановки задачи: а)
задана продолжительность выполнения всего комплекса операций. Требуется определить сроки каждой операции, при которых: минимизируются общие затраты на выполнение всего комплекса операций, определяется вероятность невыполнения комплекса работ в установленные сроки, определяется среднеквартальные отклонения требуемых ресурсов от наличных. б)
заданы общие ресурсы. Определить сроки начала каждой операции, чтобы минимизировать время на выполнение всего комплекса операций. 7. Задачи маршрутизации.
Эти задачи возникают при исследовании разнообразных процессов на транспорте и в системах связи. Типичной задачей является задача выбора оптимального маршрута:
имеется несколько маршрутов, из них нужно выбрать один. Стоимость прохождения и время на прохождение зависит от выбранного маршрута. При рассмотрении ряда маршрутов вводятся следующие ограничения: - запрещается возвращаться в уже пройденный пункт, - в пунктах сети возможны задержки (например, из-за ограниченной пропускной способности). Задержки носят случайный характер. Критерии оптимизации: минимизация общего времени прохождения маршрута или минимизация общих затрат. Данные задачи наиболее изучены и в литературе носят специфические названия – задача о коммивояжере
или задача о максимальном потоке.
8. Комбинированные задачи.
Включают в себя несколько типовых задач одновременно. Пример: при планировании и управлении производством необходимо решить комплекс задач: 1) сколько изделий каждого наименования необходимо выпустить и каковы оптимальные размеры партии изделий – задача планирования производства; 2) распределить заказы или детали по видам оборудования, причем оптимальный план производства задан – задача распределения; 3) определить в какой последовательности следует выполнить производственные заказы – календарное планирование. Эти задачи нельзя решать независимо друг от друга. Критерии эффективности этих задач часто противоречат друг другу. Поэтому при решении задач часто используют: Метод последовательного приближения –
с помощью этого метода можно очень близко подойти к оптимальному решению. Метод имитационного моделирования –
основан на методе Монте-Карло (использование случайных чисел) и требует огромного количества вычислений, так как рассматривается очень много вариантов решений. 1.4. Методы отыскания оптимальных решений в задачах Исследования Операций. Классификация методов
К основным методам отыскания оптимальных решений относятся: математическое программирование. В свою очередь методы математического программирования делятся на следующие: линейное программирование, нелинейное программирование, динамическое программирование, целочисленное программирование, стохастическое программирование, эвристическое программирование теория массового обслуживания, сетевые модели планирования и управления, имитационное моделирование. Рассмотренные выше классы задач можно решать указанными методами. Методами математического программирования
решаются следующие классы задач: задачи управления запасами, задачи распределения ресурсов, задачи замены и ремонта оборудования, задачи выбора маршрута. С помощью теории массового обслуживания
решаются задачи массового обслуживания. С использованием сетевых моделей планирования и управления
можно решать: задачи массового обслуживания, задачи упорядочивания, задачи сетевого планирования. Методом имитационного моделирования
решаются комбинированные задачи. Данным методом можно решить задачу любого класса, однако, данный метод не является универсальным. Его применение ограничено следующими факторами: 1) требуется наличие высококвалифицированных специалистов, т.к. он содержит в себе элементы всех вышеперечисленных методов; 2) решение обходится дороже, чем при использовании других методов. Однако идеи Л.В.Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т.Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования. Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны. Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике". Оптимизационная задача
– это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. В самом общем виде задача математически записывается следующим образом:
где X = (x1
, x2
, ... , xn
);
W
– область допустимых значений переменных x1
, x2
, ... , xn
; f
(Х
) – целевая функция. Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f
(Х
) не ограничена сверху на допустимом множестве W
. Методы решения оптимизационных задач зависят как от вида целевой функции f
(Х
), так и от строения допустимого множества W
. Если целевая функция в задаче является функцией n
переменных, то методы решения называют методами математического программирования. 2.1. Задачи линейного программирования
Линейное программирование является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач линейного программирования следующие: 1) показатель оптимальности f
(X
) представляет собой линейную функцию от элементов решения X = (x1
, x2
, ... , xn
); 2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств. Задачей линейного программирования
называется задача исследования операций, математическая модель которой имеет вид: При этом система линейных уравнений (2.3) и неравенств (2.4), (2.5), определяющая допустимое множество решений задачи W
, называется системой ограничений задачи линейного программирования
, а линейная функция f
(Х
) называется целевой
функцией
или критерием оптимальности
. В частном случае, если I
= Ø, то система (2.3) – (2.4) состоит только из линейных неравенств, а если I
= M
, то – из линейных уравнений. При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность
означает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален
величине этой переменной. Например, если, продавая j
-й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной xj
. Т.е. в разных ситуациях одна
единица j
-го товара будет приносить разный
доход. Аддитивность
означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого. Допустимое решение
– это совокупность чисел (план) X = (x1
, x2
, ... , xn
), удовлетворяющих ограничениям задачи. Оптимальное решение –
это план, при котором целевая функция принимает свое максимальное (минимальное) значение. Если математическая модель задачи линейного программирования имеет вид:
то говорят, что задача представлена в канонической форме
. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот. Правило приведения задачи линейного программирования к каноническому виду состоит в следующем
: 1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции; 2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1; 3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства; 4) если некоторая переменная xk
не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: Пример 2.1
. Приведение к канонической форме задачи линейного программирования: Введем в каждое уравнение системы ограничений выравнивающие переменные x
4
, x
5
, x
6
. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x
4
, x
6
вводятся в левую часть со знаком "+", а во второе уравнение вводится x
5
со знаком "-". Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1: В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что
Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме: Назад | Содержание | Далее 2.2. Построение экономико-математических моделей задач линейного программирования
Рассмотрим процесс построения математических моделей задач линейного программирования на примерах. Пример 2.2.
Определение оптимального ассортимента продукции.
Предприятие изготавливает два вида продукции - П1
и П2
, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья - А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1
и вида П2
дан в табл. 2.1. Таблица 2.1. Расход сырья продукции
Сырье Расход сырья на 1 ед. продукции Запас сырья, ед. П1
П2
А 2 3 9 В 3 2 13 Опыт работы показал, что суточный спрос на продукцию П1
никогда не превышает спроса на продукцию П2
более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2
никогда не превышает 2 ед. в сутки. Оптовые цены единицы продукции равны: 3 д. е. - для П1
и 4 д.е. для П2
. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализация продукции был максимальным? Процесс построения математической модели для решения подавленной задачи начинается с ответов на следующие вопросы: 1. Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные данной задачи? 2. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы? 3. В чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи? Ответы на вышеперечисленные вопросы могут быть сформулированы для данной задачи так: фирме требуется определить объемы производства каждого вида продукции в тоннах, максимизирующие доход в д.е. от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов. Для построения математической модели остается только идентифицировать переменные и представить цель и ограничения в виде математических функций этих переменных. Предположим, что предприятие изготовит х1
единиц продукции П1
и х2
единиц продукции П2
. Поскольку производство продукции П1
и П2
ограничено имеющимися в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, должны выполняться следующие неравенства: Доход от реализациих1
единиц продукции П1
и х2
единиц продукции П2
составит F = 3 х1
+ 4х2
. Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F
принимает максимальное значения Fmax
. Рассмотренная задача относится к разряду типовых задач оптимизации производственной программы предприятия. В качестве критериев оптимальности в этих задачах могут быть также использованы: прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени. Пример 2.3.
Использование мощностей оборудования.
Предприятие имеет m
моделей машин различных мощностей. Задан план по времени и номенклатуре: Т
- время работы каждой машины; продукции j
-го вида должно быть выпущено не менее Nj
единиц. Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой i
-й машины по выпуску j
-го вида продукции bij
и стоимость единицы времени, затрачиваемого i
-й машиной на выпуска j
-го вида продукции cij
. Другими словами, задача для предприятия состоит в следующем: требуется определить время работы i
-й машины по выпуску j
-го вида продукции xij
, обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т
и заданному количеству продукции Nj
. По условию задачи машины работают заданное время Т
, поэтому данное ограничение можно представить в следующем виде:
Ограничение по заданному количеству продукции выглядит следующим образом:
Задача решается на минимум затрат на производство:
Необходимо также учесть неотрицательность переменных Задача поставлена так, чтобы израсходовать все отведенное время работы машины, т.е. обеспечить полную загрузку машины. При этом количество выпускаемой продукции каждого вида должно быть по крайней мере не менее Nj
. Однако в некоторых случаях не допускается превышение плана по номенклатуре, тогда ограничения математической модели изменяются следующим образом:
Пример 2.4.
Минимизация дисбаланса на линии сборки.
Промышленная фирма производит изделие, представляющее собой сборку из m
различных узлов. Эти узлы изготавливаются на n
заводах. Из-за различий в составе технологического оборудования производительность заводов по выпуску j
-го узла неодинакова и равна bij
. Каждый i
-й завод располагает максимальным суммарным ресурсом времени в течение недели для производства m
узлов, равного величине Ti
. Задача состоит в максимизации выпуска изделий, что по существу эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или по нескольким видам узлов. В данной задаче требуется определить еженедельные затраты времени (в часах) на производство j
-го узла на i
-м заводе, не превышающие в сумме временные ресурсы 1-го завода и обеспечивающие максимальный выпуск изделий. Пусть xij
- недельный фонд времени (в часах), выделяемый на заводе для производства узла j
. Тогда объемы производства узла j
будут следующими:
Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделии должно быть равно количеству комплектующих узлов, объем производства которых минимален:
Условие рассматриваемой задачи устанавливает ограничение на фонд времени, которым располагает завод i
. Таким образом, математическая модель может быть представлена в следующем виде. Максимизируем
Эта модель не является линейной, но ее можно привести к линейной форме с помощью простого преобразования. Пусть Y
- количество изделий:
Этому выражению с математической точки зрения эквивалентна следующая формулировка: максимизировать Z
= Y
при ограничениях
Пример 2.5.
Задача составления кормовой смеси, или задача диете.
. Пусть крупная фирма (условно назовем ее «Суперрацион») имеет возможность покупать m
различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных компонентов (ингредиентов). Лабораторией фирмы установлено, что продукция должна удовлетворять по крайней мере некоторым минимальным требованиям с точки зрения питательности (полезности). Перед руководством ширмы стоит задана определить количество каждого i
-го сырья, образующего смесь минимальной стоимости при соблюдении требований к общему расходу смеси и ее питательности. Решение
Введем условные обозначения: xi
- количество i
-го сырья в смеси; m
- количество видов сырья; n
- количество ингредиентов в сырье; aij
- количество ингредиента j
, содержащегося в единице i
-го вида сырья; bj
- минимальное количество ингредиента j
, содержащегося в единице смеси; ci
- стоимость единицы сырья i
; q
- минимальный общий вес смеси, используемый фирмой, Задача может быть представлена в виде
при следующих ограничениях: на общий расход смеси:
на питательность смеси:
на неотрицательность переменных:
Пример 2.6.
Задача составления жидких смесей.
Еще один класс моделей, аналогичных рассмотренным выше, возникает при решении экономической проблемы, связанной с изготовлением смесей различных жидкостей с целью получения пользующихся спросом готовых продуктов. Представим себе фирму, торгующую различного рода химическими продуктами, каждый из которых является смесью нескольких компонентов. Предположим, что эта фирма планирует изготовление смесей m
-видов. Обозначим подлежащее определению количество литров i
-
го химического компонента, используемого для получения j
-го продукта через xij
. Будем предполагать, что
Первая группа ограничений относится к объемам потребляемых химических компонентов:
где Si
- объем i
-го химического компонента, которым располагает фирма в начале планируемого периода. Вторая группа ограничений отражает требование, заключающееся в том, чтобы запланированный выпуск продукции хотя бы в минимальной степени удовлетворял имеющийся спрос на каждый из химических продуктов, т.е.
где Di
- минимальный спрос на продукцию у в течение планируемого периода. Третья группа ограничений связана с технологическими особенностями, которые необходимо принимать во внимание при приготовлении смеси например, простое ограничение, определяемое некоторыми минимально допустимыми значениями, отношения между объемами двух химических компонентов в процессе получения продукта j
: где r
- некоторая заданная константа. Обозначив через Рij
доход с единицы продукции хij
запишем целевую функцию:
Пример 2.7.
Задача о раскрое или о минимизации обрезков.
Данная задача состоит В разработке таких технологических планов раскроя, при которых получается необходимый комплекс заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Например, продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины L
. По специальным заказам потребителей фирма поставляет рулоны других размеров, для этого производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров могут включать т
видов шириной Hi
( Обозначим через aij
количество рулонов i
-го вида, получаемых при раскрое единицы стандартного рулона по j
-му варианту. При каждом варианте раскроя на каждый стандартный рулон возможны потери, равные Pi
. К потерям следует относить также избыточные рулоны нестандартной длины li
, получаемые при различных вариантах раскроя yij
, В качестве переменных следует идентифицировать количество стандартных рулонов, которые должны быть разрезаны при j
-м варианте раскроя. Определим переменную следующим образом: xj
- количество стандартных рулонов, разрезаемых по варианту j
, Целевая функция - минимум отходов при раскрое
Ограничение на удовлетворение спроса потребителя
Пример 2.8.
Транспортная задача.
Имеется три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их cij
, Требуется составить такой план перевозок, чтобы обеспечить минимальные суммарные затраты при полном удовлетворении потребностей. Введем переменные хij
- количество груза, перевозимого от i
-го поставщика j
-му потребителю. Ограничения задачи выглядят следующим образом: потребности всех потребителей должны быть удовлетворены полностью:
или в общем виде:
груз от поставщика должен быть вывезен полностью:
или в общем виде:
условие неотрицательности переменных: Целевая функция - минимизировать суммарные затраты на перевозку:
Количество поставщиков и потребителей в общем случае может быть произвольным. Мы рассмотрели девять примеров типовых задач линейного программирования. Обобщая их, можно сделать следующие выводы. 1. Ограничения в задачах линейного программирования могут быть выражены как равенствами, так и неравенствами. 2. Линейная функция может стремиться как к максимуму, так и к минимуму. 3. Переменные в задачах всегда неотрицательны. Напомним, что от любой из вышеперечисленных задач можно перейти к канонической (основной) задаче линейного программирования. Назад | Содержание | Далее 2.3. Графическое решение задачи линейного программирования
Графически способ решения задач линейного программирования целесообразно использовать для: решения задач с двумя переменными, когда ограничения выражены неравенствами; решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных. Запишем задачу линейного программирования с двумя переменными: целевая функция:
ограничения:
Каждое из неравенств (2.35) – (2.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми Областью допустимых решений
системы неравенств (2.35) – (2.36) может быть: выпуклый многоугольник; выпуклая многоугольная неограниченная область; пустая область; луч; отрезок; единственная точка. Целевая функция (2.34) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значений Z
. Вектор Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (2.35) – (2.36) и семейство параллельных прямых (2.34), то задача определения максимума функции Z
сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z
= const, и которая соответствует наибольшему значению параметра Z
. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня Заканчивая рассмотрение геометрической интерпретации задачи (2.35) – (2.36), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 2.1 – 2.4. Рис. 2.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 2.3 изображен случай, когда максимум недостижим, а на рис. 2.4. – случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z
при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора
Рис. 2.1. Оптимум функции Z достижим в точке А
Рис. 2.2. Оптимум функции Z достигается в любой точке |АB| Рис. 2.3. Оптимум функции Z недостижим
Для практического решения задачи линейного программирования (2.34) – (2.36) на основе ее геометрической интерпретации необходимо следующее: 1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (2.35) – (2.36) знаков неравенств на знаки равенств. 2. Найти полуплоскости, определяемые каждым из ограничений. 3. Определить многоугольник решений. 4. Построить вектор 5. Построить прямую 6. Передвигать прямую Z в направлении вектора 7. Определить точки координаты максимума функции и вычислить значение целевой функции в этой точке. Пример 2.9.
Рассмотрим решение задачи об ассортименте продукции (пример 2.2) геометрическим способом. Решение
Построим многоугольник решений (рис.2.5). Для этого в системе координат X1
0X2
на плоскости изобразим граничные прямые: 2х1
+ 3х2
= 9 (L1
); 3х1
+ 2х2
= 13 (L2
); х1
- х2
= 1 (L3
); х2
= 2 (L4
). Взяв какую-либо точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Полуплоскости, определяемые неравенствами, на рис. Показаны стрелками. Областью решений является многоугольник OABCD
. Для построения прямой Z = 3х1
+ 4х2
= 0 строим вектор-градиент Оптимальный план задачи х1
=2,4; х2
=1,4. Подставляя значения х1
и х2
в линейную функцию, получим: Полученное решение означает, что объем производства продукции П
1
должен быть равен 2,4 ед., а продукции П
2
– 1,4 ед. Доход, получаемый в этом случае, составит: Z
= 12,8 д.е.
Рис. 2.5. Решение задачи линейного программирования геометрическим способом Назад | Содержание | Далее 2.4. Анализ моделей на чувствительность
Анализ моделей на чувствительность — это процесс, реализуемый после получения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. В задаче об ассортименте продукции (пример 2.2) может представлять интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение спроса на продукцию или запасов исходного сырья. Возможно, также потребуется анализ влияния рыночных цен на оптимальное решение. При таком анализе всегда рассматривается комплекс линейных оптимизационных моделей. Это придает модели определенную динамичность, позволяющую исследователю проанализировать влияние возможных изменений исходных условий на полученное ранее оптимальное решение. Динамические характеристики моделей фактически отображают аналогичные характеристики, свойственные реальным процессам. Отсутствие методов, позволяющих выявлять влияние возможных изменений параметров модели на оптимальное решение, может привести к тому, что полученное (статическое) решение устареет еще до своей реализации. Для проведения анализа модели на чувствительность с успехом могут быть использованы графические методы. Рассмотрим основные задачи анализа на чувствительность на примере 2.9. Задача 1
. Анализ изменений запасов ресурсов.
После нахождения оптимального решения представляется вполне логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Для этого необходимо ответить на два вопроса: 1. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции Z
? 2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции Z
? Прежде чем ответить на поставленные вопросы, классифицируем ограничение линейной модели как связывающие (активные) и несвязывающие (неактивные) ограничения. Прямая, представляющая связывающее ограничение, должна проходить через оптимальную точку, в противном случае, соответствующее ограничение будет несвязываюшим. На рис. 2.5 связывающими ограничениями являются ограничения (1) и (3), представленные прямыми L1
и L3
соответственно, т.е. те, которые определяют запасы исходных ресурсов. Ограничение (1) определяет запасы сырья А
. Ограничение (3) определяет соотношение спроса на выпускаемую продукцию. Если некоторое ограничение является связывающим, то соответствующий ресурс относят к разряду дефицитных ресурсов, так как он используется полностью. Ресурс, с которым ассоциировано несвязывающее ограничение, следует отнести к разряду недефицитных ресурсов (т.е. имеющихся в некотором избытке). В нашем примере несвязывающими ограничениями являются (2) и (4). Следовательно, ресурс - сырье В
- недефицитный, т.е. имеется в избытке, а спрос на продукцию П2
не будет удовлетворен полностью (в таблице - ресурсы 2 и 4). При анализе модели на чувствительность к правым частям ограничений определяются: 1) предельна допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение, и 2) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденное ранее оптимальное значение целевой функции. В нашем примере сырье А
и соотношение спроса на выпускаемую продукцию П1
и П2
являются дефицитными ресурсами (в таблице - ресурсы 1, 3). Рассмотрим сначала ресурс - сырье А
. На рис. 2.6 при увеличении запаса этого ресурса прямая L1
перемещается вверх, параллельно самой себе, до точки К, в которой пересекаются линии ограничений L2
, L3
и L4
. В точке К
ограничения (2), (3) и (4) становятся связывающими; оптимальному решению при этом соответствует точка К
, а пространством (допустимых) решений становится многоугольник AKD
0
. В точке К
ограничение (1) (для ресурса А
) становится избыточным, так как любой дальнейший рост запаса соответствующего ресурса не влияет ни на пространство решений, ни на оптимальное решение.
Рис. 2.6. Геометрическая интерпретация решения задачи линейного программирования (изменение ресурса А) Таким образом, объем ресурса А
не следует увеличивать сверх того предела, когда соответствующее ему ограничение (1) становится избыточным, т.е. прямая (1) проходит через новую оптимальную точку К
. Этот предельный уровень определяется следующим образом. Устанавливаются координаты точки К, в которой пересекаются прямые L2
, L3
и L4
, т.е. находится решение системы уравнений В результате получается х1
= 3 и х2
= 1. Затем, путем подстановки координат точки К
в левую часть ограничения (1), определяется максимально допустимый запас ресурса А
: Рис. 2.7иллюстрирует ситуацию, когда рассматривается вопрос об изменении соотношения спроса на продукцию П1
и П2
.
Рис. 2.7. Геометрическая интерпретация решения задачи линейного программирования (изменение спроса на продукцию) Новой оптимальной точкой становится точка Е
, где пересекаются прямые L1
и L2
. Координаты данной точки находятся путем решения системы уравнений (1) и (2) следующим образом: В результате получается х1
= 4,2; х2
= 0,2, причем суточный спрос на продукцию П1
не должен превышать спрос на продукцию П2
на величину х1
- х2
= 4,2 -0,2= 4 ед. Дальнейшее увеличение разрыва в спросе на продукцию П1
и П2
не будет влиять на оптимальное решение. Рассмотрим вопрос об уменьшении правой части несвязывающих ограничений. Ограничение (4) фиксирует предельный уровень спроса на продукцию П2
. Из рис. 2.5 следует, что, не изменяя оптимального решения, прямую L4
(АВ
) можно опускать вниз до пересечения с оптимальной точкой С
. Так как точка С
имеет координаты х1
= 4,2; х2
=1,4 уменьшение спроса на продукцию П2
до величины х2
=1,4 никак не повлияет на оптимальность ранее полученного решения. Рассмотрим ограничение (2) Результаты проведенного анализа можно свести в следующую таблицу: Ресурс Тип ресурса Максимальное изменение запаса ресурса, ед. Максимальное увеличение дохода от изменения ресурса, у.д.е. 1 (А
) дефицитный 12 – 9 = +3 17 – 12,8 = +4,2 2 (В
) недефицитный 10 – 13 = -3 12,8 – 12,8 = 0 3 дефицитный 4 – 1 = +3 13,4 – 12,8 = +0,6 4 недефицитный 1,4 – 2 = -0,6 12,8 – 12,8 = 0 Задача 2.
Определение наиболее выгодного ресурса.
В задаче 1 анализа на чувствительность мы исследовали влияние на оптимум увеличения объема дефицитных ресурсов. При ограничениях, связанных с дополнительным привлечением ресурсов, естественно задать вопрос: какому из ресурсов следует отдать предпочтение при вложении дополнительных средств? Для этого вводится характеристика ценности каждой дополнительной единицы дефицитного ресурса, выражаемая через соответствующее приращение оптимального значения целевой функции. Такую характеристику для рассматриваемого примера можно получить непосредственно из таблицы, в которой приведены результаты решения задачи 1 на чувствительность. Обозначим ценность дополнительной единицы ресурса i
через yi
. Величина yi
определяется из соотношения Результаты расчета ценности единицы каждого из ресурсов представлены в следующей таблице:
Полученные результаты свидетельствуют о том, что дополнительные вложения в первую очередь следует направить на увеличение ресурса А
и лишь затем - на формирование соотношения спроса на продукцию П1
и продукцию П2
. Что касается недефицитных ресурсов, то, как и следовало ожидать, их объем увеличивать не следует. Задача 3.
Определение пределов изменения коэффициентов целевой функции.
Изменение коэффициентов целевой функции оказывает влияние на наклон прямой, которая представляет эту функцию в принятой системе координат. Вариация коэффициентов целевой функции может привести к изменению совокупности связывающих ограничений и, следовательно, статуса того или иного ресурса (т.е. сделать недефицитный ресурс дефицитным, и наоборот). При анализе модели ни чувствительность к изменениям коэффициентов целевой функции необходимо исследовать следующие вопросы: 1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходят изменения оптимального решения? 2. На сколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным, и, наоборот, дефицитный ресурс сделать недефицитным? Ответим на поставленные вопросы на нашем примере. Рассматривая первый вопрос, обозначим через c1
и c2
доходы предприятия от продажи единицы продукции П1
и П2
соответственно. Тогда целевую функцию можно представить в следующем виде: Z = с1
х1
+ с2
х2
На рис. 2.5 видно, что при увеличении c1
или уменьшении c2
прямая, представляющая целевую функцию Z
, вращается (вокруг точки С
) по часовой стрелке. Если же c1
уменьшается или c2
увеличивается, эта прямая вращается в противоположном направлении - против часовой стрелки. Таким образом, точка С
будет оставаться оптимальной точкой до тех пор, пока наклон прямой не выйдет за пределы, определяемые наклонами прямых для ограничений (1) и (3). Когда наклон прямой Z
станет равным наклону прямой L1
, получим две альтернативные оптимальные угловые точки - С
и В
. Аналогично, если наклон прямой Z
станет равным наклону прямой для ограничения (3), будем иметь альтернативные оптимальные угловые точки С
и D
. Наличие альтернативных оптимумов свидетельствует о том, что одно и то же оптимальное значение Z
может достигаться при различных значениях переменных х1
и х2
. Как только наклон прямой выйдет за пределы указанного выше интервала c1
, получим некоторое новое оптимальное решение. Рассмотрим на нашем примере, каким образом можно найти допустимый интервал изменения c1
, при котором точка С
остается оптимальной. Исходное значение коэффициента c2
= 4 оставим неизменным. На рис. 2.5 видно, что значение c1
можно уменьшать до тех пор, пока прямая Z
не совпадет с прямой L1
(отрезок ВС
). Это крайнее минимальное значение коэффициента c1
можно определить из равенства углов наклонов прямой Z
и прямой L1
. Так как тангенс угла наклона для прямой Z
равен (c1
/4) , а для прямой (1) равен 2/3, то минимальное значение c1
определим из равенства c1
/4=2/3, откуда Интервал изменения c1
, в котором точка С
по-прежнему остается единственной оптимальной точкой, определяется неравенством Можно заметить, что, как только коэффициент c1
оказывается меньше 8/3, ресурс 3 становится недефицитным, а ресурс 4 - дефицитным. Для предприятия это означает следующее; если доход от продажи единицы продукции П1
станет меньше 8/3 д.е., то наиболее выгодная производственная программа предприятия должна предусматривать выпуск максимально допустимого количества продукции П2
(полностью удовлетворять спрос на продукцию П2
). При этим соотношение спроса на продукцию П1
и П2
не будет лимитировать объемы производства, что обусловит недефицитность ресурса (3). Увеличение коэффициента c1
свыше 8/3 д.е. не снимает проблему дефицита ресурсов (1) и (3). Точка С
- точка пересечения прямых L1
и L3
- остается все время оптимальной. Назад | Содержание | Далее 2.5.1. Общая идея симплекс-метода
Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причем в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи при помощи симплекс-метода распадается на ряд шагов. На каждом шаге от данного базиса Б
переходят к другому, новому базису Б
1
с таким расчетом, чтобы значение функции Z
уменьшалось, т. е. Назад | Содержание | Далее 2.5.2. Алгоритм симплекс-метода
Рассмотрим систему ограничений и линейную форму вида:
Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения: x1
, x2
, ... , xr
- базисные переменные; xr
+1
, xr
+2
, ... , xn
- свободные переменные.
По последней системе ограничений и целевой функции Z
построим табл. 2.3. Таблица 2.3 Симплекс-таблица
Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы. Алгоритм симплекс-метода сводится к следующему.
1. В последней строке симплекс-таблицы находят наименьший положительный элемент, не считая свободного члена. Столбец, соответствующий этому элементу, считается разрешающим. 2. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс-отношений, оно соответствует разрешающей строке. 3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент. 4. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы. 5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс-таблица преобразована следующим образом (табл. 2.4): 6. Элемент табл. 2.4, соответствующий разрешающему элементу табл. 2.3, равен обратной величине разрешающего элемента. 7. Элементы строки табл. 2.4, соответствующие элементам разрешающей строки табл. 2.3, получаются путем деления соответствующих элементов табл. 2.3 на разрешающий элемент, 8. Элементы столбца табл. 2.4, соответствующие элементам разрешающего столбца табл. 2.3, получаются путем деления соответствующих элементов табл. 2.3 на разрешающий элемент и берутся с противоположным знаком. 9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 2.3, одна вершина которого совпадает с разрешающим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 2.4 будет равен соответствующему элементу табл. 2.3 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе - произведение элементов из двух неиспользованных вершин прямоугольника. 10. Как только получится таблица, в которой в последней строке все элементы отрицательны, считается, что минимум найден. Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю. 11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается). Таблица 2.4 Преобразование симплекс-таблицы
Пример 2.10
.
Решение задачи симплекс-методом: Приведем задачу к виду, допускающему применение симплекс-алгоритма: Подставим в выражение Zmax
величины x3
, x4
, x5
: По алгоритму целевая функция должна стремиться к минимуму: Составим симплекс-таблицу:
Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен +6, первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной x4
и столбца - x1
. Переходим к следующей таблице, используя правило прямоугольника:
В последней строке нет положительных элементов, следовательно, оптимальное решение найдено: Zmin
= -9; X
= (1; 0; 2, 0, 1); Zmin
= - Zmax
= 9 Назад | Содержание | Далее Построить математическую модель задачи линейного программирования (2.1 – 2.20). Задача 2.1
Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П1
и П2
равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед. Стоимость 1 ед. продукта П1
– 2 руб., П2
–3 руб. Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ. Задача 2.2
Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие: Поезда Количество вагонов в поезде багажный почтовый плацкарт купе СВ скорый 1 1 5 6 3 пассажирский 1 - 8 4 1 число пассажиров - - 58 40 32 парк вагонов 12 8 81 70 26 Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров? Задача 2.3
Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 тонны. Овощехранилища имеют соответственно 20, 20 ,15 и 25 тонн. Тарифы (в д.е. за 1 тонну) указаны в следующей таблице: Овощехранилища Магазины 1 2 3 1 2 7 4 2 3 2 1 3 5 6 2 4 3 4 7 Составьте план перевозок, минимизирующий суммарные транспортные расходы. Задача 2.4
Имеются два склада готовой продукции: А1
и А2
с запасами однородного груза 200 и 300 тонн. Этот груз необходимо доставить трем потребителям В1
, В2
и В3
в количестве 100, 150 и 250 тонн соответственно. Стоимость перевозки 1 тонны груза из склада А1
потребителям В1
, В2
и В3
равна 5, 3 ,6 д.е., а из склада А2
тем же потребителям – 3, 4, 2 д.е. соответственно. Составьте план перевозок, минимизирующий суммарные транспортные расход. Задача 2.5
При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице. Питательные вещества Количество единиц питательных веществ на 1 кг. корма 1 корма 2 белки 3 1 углеводы 1 2 протеин 1 6 Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е. Составьте дневной рацион питательности, имеющий минимальную стоимость. Задача 2.6
Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции: П1
, П2
, П3
и П4
. Организация производства характеризуется следующей таблицей: продукция Затраты на 1 ед. продукции Доход от единицы продукции площадь труд тяга П1
2 2 2 1 П2
3 1 3 4 П3
4 2 1 3 П4
5 4 1 5 Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль. Задача 2.7
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа – 3 тонны, проволоки – 18 тонн. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. Задача 2.8
Совхоз отвел три земельный массива размером 5000, 8000 и 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице: Посевы Массивы I II III рожь 12 14 15 пшеница 14 14 22 кукуруза 30 35 25 За 1 центнер ржи совхоз получает 2 д.е., за 1 центнер пшеницы – 2,8 д.е., за 1 центнер кукурузы – 1,4 д.е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 тонны ржи, 158 000 тонны пшеницы и 30 000 тонн кукурузы? Задача 2.9
Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице: Продукт Содержание химического вещества в 1 ед. продукции Стоимость 1 ед. продукции А В С I 2 1 3 2 II 1 2 4 3 III 3 1,5 2 2,5 Составьте наиболее дешевую смесь. Задача 2.10
В школе проводится конкурс на лучшую стенгазету. Одному школьнику дано следующее поручение: купить акварельной краски по цене 30 д.е. за коробку, цветные карандаши по цене 20 д.е. за коробку, линейки по цене 12 д.е., блокноты по цене 10 д.е.; красок нужно купить не менее трех коробок, блокнотов – столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д.е. В каком количестве школьник должен купить указанные предметы, чтобы общее число предметов было наименьшим? Задача 2.11
Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозу одного двигателя из районов к мастерским следующие: Районы Мастерские 1 2 3 1 4,5 3,7 8,3 2 2,1 4,3 2,4 3 7,5 7,1 4,2 4 5,3 1,2 6,2 5 4,1 6,7 3,1 Спланируйте количество ремонтов каждой мастерской для каждого из районов, минимизирующее суммарные транспортные расходы. Задача 2.12
Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е. Составьте план выпуска разных сортов авиационного бензина из условия получения максимальной стоимости всей продукции. Задача 2.13
Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по Буге, пряжкам в высоту, прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину – 8 спортсменов, а в прыжках в высоту – не более 10. количество очков, гарантируемых спортсмену каждого разряда по каждому виду, указано в таблице: Разряд Бег Прыжки в высоту Прыжки в длину I 4 5 5 II 2 3 3 Распределите спортсменов в команды так, чтобы сумма очков команды была наибольшей, если известно, что в команде I разряд имеют только 10 спортсменов. Задача 2.13
Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеется 10 000 клеток. В одной клетке могут быть либо 2 лисицы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма – 4 ед., а каждому песцу – 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца – 5 д.е. Какое количество лисиц и песцов нужно держать не ферме, чтобы получить наибольшую прибыль? Задача 2.14
Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 тонн зерна. Зерна необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 тонн каждому. Расстояние от элеватора до хлебозавода указано в следующей таблице: Элеваторы Хлебозаводы 1 2 3 1 20 30 50 2 60 20 40 Затраты на перевозку 1 тонны продукта на 1 км составляют 25 д.е. Спланируйте перевозки зерна из условия минимизации транспортных расходов. Задача 2.15
Из двух сортов бензина образуются две смеси – А и В. Смесь А содержит Бензина 60% 1-го сорта и 40% 2-го сорта; смесь В – 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А – 10 д.е., а смеси В – 12 д.е. Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензин 50 т 1-госорта и 30 т второго сорта. Задача 2.16
Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн. га. Данные об урожайности зерновых культур приведены в таблице: Зерновые культуры Урожайность (ц/га) Стоимость 1 ц, д.е. 1-я зона 2-я зона Озимые 20 25 8 Яровые 25 20 7 Определите размеры посевных площадей озимых и яровых культур, необходимые для достижения максимального выхода продукции в стоимостном выражении. Задача 2.17
Для полива различных участков сада, на которых растут сливы, яблони, груши, служат три колодца. Колодцы могут дать соответственно 180, 90 и 40 ведер воды. Участки сада требуют для полива соответственно 100 120 и 90 ведер воды. Расстояния (в метрах) от колодцев до участков чада указаны в следующей таблице: Колодцы Участки сливы яблони груши 1 10 5 12 2 23 28 33 3 43 4 39 Как лучше организовать полив? Задача 2.18
На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех видов: энергия, материалы, труд. Данные о технологическом процессе приведены в следующей таблице: Ресурсы Затраты ресурсов на единицу изделия Запасы ресурсов, ед. I II III IV энергия 2 3 1 2 30 материалы 4 2 1 2 40 труд 1 2 3 1 25 Спланируйте производство так, чтобы прибыль от их реализации была наибольшей. Задача 2.19
При изготовлении изделий П1
и П2
используются сталь и цветные металлы, а также токарные и фрезерные станки. По технологическим нормам на производство единицы изделия П1
требуется 300 и 200 станко-часов соответственно токарного и фрезерного оборудования, а также 10 и 20 кг соответственно стали и цветных металлов. Для производства единицы изделия П2
требуется 400, 100, 70 и 50 соответствующих единиц тех же ресурсов. Цех располагает 12400 и 6800 станко-часами соответственно токарного и фрезерного оборудования и 640 и 840 кг соответственно стали и цветных металлов. Прибыль от реализации единицы изделия П1
составляет 6 руб. и от единицы изделия П2
– 16 руб. Постройте математическую модель задачи, используя в качестве показателя эффективности прибыль и учитывая, что время работы фрезерных станков должно быть использовано полностью. Задача 2.20
Ежедневно в ресторане фирменный коктейль (порция составляет 0,33 л) заказывают в среднем 600 человек. Предполагается, что в ближайшее время их количество увеличится в среднем на 50 человек. Согласно рецепту в составе коктейля должно быть: не менее 20%, но и не более 35% спирта; не менее 2% сахара; не более 5% примесей; не более 76% воды; не менее 7% и не более 12% сока. В таблице приведены процентный состав напитков, из которых смешивается коктейль, и их количество, которое ресторан может ежедневно выделять на приготовление коктейля. Процентный состав и запасы напитков
Напиток Спирт Вода Сахар Примеси Количество, л/сут. Водка 40% 57% 1% 2% 50 Вино 18% 67% 9% 6% 184 Сок 0% 88% 8% 4% 46 Постройте модель, на основании которой можно будет определить, хватит ли ресторану имеющихся ежедневных запасов напитков для удовлетворения возросшего спроса на коктейль. Решите задачи линейного программирования (2.21 – 2.36) графическим методом, проведите анализ на чувствительность.
Во всех задачах Задачи линейного программирования (2.37 – 90) решите симплекс-методом и проведите анализ моделей на чувствительность.
Назад | Содержание | Далее Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока. Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Назад | Содержание | Далее Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m
производителей (поставщиков), по n
потребителям этих ресурсов. Различают два типа транспортных задач: но критерию стоимости
(план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени
(план оптимален, если на его реализацию затрачивается минимум времени). Наиболее часто встречаются следующие задачи, относящиеся к транспортным: прикрепление потребителей ресурса к производителям; привязка пунктов отправления к пунктам назначения; взаимная привязка грузопотоков прямого и обратного направлений; отдельные задачи оптимальной загрузки промышленного оборудования; оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др. Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m
пунктов отправления груза и объемы отправления по каждому пункту a1
, a2
,...,am
. Известна потребность в грузах b1
, b2
,...,bn
по каждому из n
пунктов назначения. Задана матрица стоимостей доставки по каждому варианту cij
, В общем виде исходные данные представлены в табл. 3.1. Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта ai
), а столбцы — пунктам назначения (последняя клетка каждого столбца содержит значение потребности bj
). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i
-го пункта в j
-й: в правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем — значение объема перевозимого груза для данных пунктов. Таблица 3.1 Исходные данные
Транспортная задача называется закрытой, если суммарный объем отправляемых грузов .
Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:
Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнении. Все грузы из i
-х пунктов должны быть отправлены, т.е.:
Все j
-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:
Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных:
Вместо матрицы стоимостей перевозок (cij
) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (3.1), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае, если потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления; запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления. Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая. Транспортным задачам присущи следующие особенности: распределению подлежат однородные ресурсы; условия задачи описываются только уравнениями; все переменные выражаются в одинаковых единицах измерения; во всех уравнениях коэффициенты при неизвестных равны единице; каждая неизвестная встречается только в двух уравнениях системы ограничений. Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения. Опорный план
является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее. Все существующие методы нахождения опорных планов отличаются только способом выбора клетки для заполнения. Само заполнение происходит одинаково независимо от используемого метода. Назад | Содержание | Далее 3.2. Методы составления начального опорного плана
Базисный план составляется последовательно, в несколько шагов (точнее, m + n - 1 шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка). В первом случае мы можем исключить столбец, содержащий заполненную на этом шаге клетку, и считать, что задача свелась к заполнению таблицы с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем же количеством строк и с соответственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге). Во втором случае исключается строка, содержащая заполняемую клетку, и считается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потребности заказчика, в столбце которого находится заполняемая клетка. Начиная с первоначально данной таблицы и повторив (m + n - 2) раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив (m + n - 1) шагов, мы и получим искомый опорный план. Замечание
.
Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется равной запасу груза на очередной базе. Тогда после заполнения очередной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется "остаток" равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная "потребность" в количестве нуля единиц груза, которая и удовлетворяется на одном из следующих шагов. Этот нуль ("запас" или "потребностью" – безразлично) надо записать в очередную заполняемую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем. 1. Диагональный метод
, или метод северо-западного угла
. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x11
и заканчивается в клетке неизвестного xmn
, т. е. идет как бы по диагонали таблицы перевозок. Пример
Заполнение таблицы начинается с ее северо-западного угла, т.е. клетки с неизвестным x11
. Первая база A1
может полностью удовлетворить потребность первого заказчика B1
(a1
=300, b1
=170, a1
> b1
). Полагая x11
= 170,
вписываем это значение в клетку x11
и исключаем из рассмотрения первый столбец. На базе A1
остается измененный запас Теперь переходим к заполнению клетки для неизвестного x23
и т.д. Через шесть шагов у нас останется одна база A3
с запасом груза (остатком от предыдущего шага) Общий объем перевозок в тонно-километрах для этого плана составит 2. Метод наименьшей стоимости
. При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них. Пример
В данном случае заполнение таблицы начинается с клетки для неизвестного x32
, для которого мы имеем значение c32
= 10, наименьше из всех значений cij
. Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе A3
и второму заказчику B2
. Третья база A3
может полностью удовлетворить потребность второго заказчика B2
(a3
=250, b2
=110, a3
> b2
) . Полагая x32
= 110, вписываем это значение в клетку x32
и исключаем из рассмотрения второй столбец. На базе A3
остается изменённый запас
На пятом шаге клеток с наименьшими значениями cij
оказалось две (c11
=c15
=70) . Мы заполнили клетку для x15
, положив x15
= 180. Можно было выбрать для заполнения другую клетку, положив x11
= 170, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит
Замечание
.
В диагональном методе не учитываются величины тарифов, в методе же наименьшей стоимости эти величины учитываются, и часто последний метод приводит к плану с меньшими общими затратами (что и имеет место в нашем примере), хотя это и не обязательно. Кроме рассмотренных выше способов иногда используется, так называемый, метод Фогеля. Суть его состоит в следующем: В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее. Назад | Содержание | Далее 3.3. Понятие потенциала и цикла
Для перехода от одного базиса к другому при решении транспортной задачи используются так называемые циклы. Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям: 1. Одно из неизвестных последовательности свободное, а все остальные – базисные. 2. Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке. 3. Три последовательных неизвестных не могут находиться в одном столбце или в одной строке. 4. Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному. Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы. Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла – замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные - в базисных клетках. Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно. Так, например, в таблице перевозок, составленной по диагональному методу при решения задачи из предыдущего пункта, неизвестному x21
соответствует цикл x21
,x
23
,x
13
,x
11
,x
21
и т.д. Пусть теперь мы имеем некоторую свободную клетку с соответствующим ей циклом. Если мы изменим значение свободного неизвестного, увеличив его на некоторое число x
, то, переходя последовательно от одной вершины цикла к другой, мы должны будем в силу неизменности сумм по строкам и по столбцам поочередно уменьшать и увеличивать значения неизвестных в цикле на то же число x
. Например, в указанном выше цикле для свободного неизвестного x21
получим: старые значения: x21
= 0, x
23
= 80, x13
= 20,x
11
= 170, x
21
= 0; новые значения: Очевидно, если снабдить вершины цикла поочередно знаками "+" и "–", приписав вершине в свободной клетке знак "+", то можно сказать, что в вершинах со знаком "+" число x
прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком "–" это число x
вычитается из прежнего значения неизвестного, находящегося в этой вершине. Замечание.
Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак "+", т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин. Если в качестве x
выбрать наименьшее из чисел, стоящих в вершинах, снабженных знаком "–", то, по крайней мере, одно из прежних базисных неизвестных примет значение нуль, и мы можем перевести его в число свободных неизвестных, сделав вместо него базисным то неизвестное, которое было свободным. Так, например, в рассмотренном выше цикле имеем отрицательные вершины x21
и x11
; следовательно, выбрав х = min {80; 170} = 80 , мы получаем: старые значения: x21
= 0, x
23
= 80, x13
= 20,x
11
= 170, x
21
= 0; новые значения: т. е. вместо прежнего базисного решения получаем новое базисное решение:
Выбор в качестве x
минимального среди чисел, стоящих в отрицательных вершинах цикла, обеспечивает допустимость нового базиса. Если минимальное значение среди базисных неизвестных, стоящих в отрицательных вершинах цикла, принимается не в одной отрицательной вершине, то свободной оставляют только одну из них, а в других клетках с тем же минимальным значением пишут нули. В этом случае новое базисное решение будет вырожденным. Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таблицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены. Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.
Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каждое из них остается либо в группе базисных, либо в группе свободных неизвестных, как и до пересчета. Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше. Пусть xpq
– некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом x
.
Если вершине цикла, находящейся в i-й строке и j-м столбце таблицы перевозок, приписан знак "+", то значение неизвестного xij
,
находящегося в этой вершине, увеличивается на x
,
что в свою очередь вызывает увеличение затрат на cij
x, где cij
– тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного xij
уменьшается на x
, что вызывает уменьшение затрат на cij
x. Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность Spq
назовем алгебраической суммой тарифов
для данного свободного неизвестного xpq
. Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”). Теперь, очевидно, мы можем, заключить, что в целом при пересчете но циклу, соответствующему свободному неизвестному xpq
общий объем затрат на перевозки изменится на произведение алгебраической суммы тарифов на x
, т. е. на величину Spq
x . Следовательно, если алгебраическая сумма тарифов для некоторого свободного неизвестного xpq
отрицательна (Spq
< 0), то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна (Spq
> 0), то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю (Spq
= 0), то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию). Так, например, для цикла x21
,x
23
,x
13
,x
11
,x
21
в рассмотренной задаче алгебраическая сумма тарифов
Значит, пересчет по этому циклу снижает расходы. И действительно, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет
тогда как по исходному плану он составил S1
= 30650. Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна –15, а пересчет по циклу осуществляется с помощью числа х = 80 (изменение затрат равно -15*80 = - 1200). Вычисление алгебраической суммы тарифов для каждого из свободных неизвестных можно производить без построения соответствующего цикла, пользуясь, так называемыми, потенциалами. Припишем каждой базе Ai
,
, некоторое число ui
,
и каждому потребителю Bj
некоторое число vj
:
так что ui
,
+ vj
= cij
, (3.6) где cij
– тарифы, соответствующие клеткам, заполненным базисными неизвестными. Эти числа ui
,
и vj
называются потенциалами
соответствующих баз и потребителей. Зная потенциалы, легко вычислить алгебраическую сумму тарифов. Действительно, если в алгебраической сумме тарифов по циклу, соответствующему свободному неизвестному xpq
, заменить тарифы базисных клеток их выражениями через потенциалы по формулам (3.6), то, в силу чередования знаков при вершинах цикла, все потенциалы, кроме up
и vq
сократятся, и мы получим: Spq
= cpq
- ( up
+ vq
). Так, например, для цикла x21
,x
23
,x
13
,x
11
,x
21
в рассмотренной выше задаче имеем
Для базисных клеток сумма потенциалов строки и столбца, в которых находится эта клетка, равна тарифу, соответствующему этой клетке; если же клетка для неизвестного xpq
свободная, то сумму потенциалов
называют косвенным тарифом
этой клетки. Следовательно, алгебраическая сумма тарифов для свободной клетки xpq
равна разности ее настоящего (“истинного”) и косвенного тарифов:
Из (3.8) следует, что если косвенный тариф для данной свободной клетки больше её истинного тарифа, то алгебраическая сумма тарифов по циклу, соответствующему этой клетке, будет отрицательна; если же косвенный тариф меньше истинного, то алгебраическая сумма тарифов положительна, и, наконец, если косвенный тариф равен истинному, то алгебраическая сумма тарифов равна нулю. Потенциалы можно найти из системы равенств (3.6), рассматривая их как систему (m + n - 1) уравнений с m+n неизвестными. Так как неизвестных здесь на единицу больше, чем уравнений, то, по крайней мере, один из потенциалов мы можем выбрать произвольно, положив,
например, u1
= 0; тогда остальные потенциалы легко определяются из уравнений (3.6). Например, для плана, полученного по диагональному методу в рассмотренной выше задаче, имеем
Система содержит семь уравнений с восемью неизвестными. Выбирая произвольно значение Положив, например, u1
= 0 , получаем значения потенциалов:
Найдем теперь косвенные тарифы для свободных клеток и сравним их с истинными тарифами:
Для клеток с неизвестными x21
и x32
косвенные тарифы больше истинных. Следовательно, для них мы будем иметь отрицательные алгебраические суммы тарифов:
Значение S21
= -15 мы уже имели раньше, вычисляя алгебраическую сумму тарифов для этой клетки непосредственно по циклу. Замечание 1.
Подсчитывая косвенные тарифы как суммы соответствующих потенциалов, полезно не пропускать и клетки с базисными неизвестными (заполненные клетки). Для этих клеток сумма потенциалов равна истинному тарифу; последнее может служить проверкой правильности найденных значении потенциалов. Замечание 2.
Можно показать, что если сумму всех затрат по данному плану перевозок выразить черех свободные неизвестные, то коэффициент при каждом из таких неизвестных будет равен алгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок. Это еще раз подтверждает, что пересчет по циклам является специфической формой применения симплекс-метода к решению транспортной задачи. Назад | Содержание | Далее Из сказанного в предыдущем пункте вытекает следующий критерий оптимальности базисного решения транспортной задачи:
если для некоторого базисного плана перевозок алгебраические суммы тарифов по циклам для всех свободных клеток неотрицательны, то этот план оптимальный. Отсюда вытекает способ отыскания оптимального решения транспортной задачи, состоящий в том, что, имея некоторое базисное решение, вычисляют алгебраические суммы тарифов для всех свободных клеток. Если критерий оптимальности выполнен, то данное решение является оптимальным; если же имеются клетки с отрицательными алгебраическими суммами тарифов, то переходят к новому базису, производя пересчет по циклу, соответствующему одной из таких клеток. Полученное таким образом новое базисное решение будет лучше исходного – затраты на его реализацию будут меньшими. Для нового решения также проверяют выполнимость критерия оптимальности и в случае необходимости снова совершают пересчет по циклу для одной из клеток с отрицательной алгебраической суммой тарифов и т. д. Через конечное число шагов приходят к искомому оптимальному базисному решению. В случае если алгебраические суммы тарифов для всех свободных клеток положительны, мы имеем единственное оптимальное решение; если же алгебраические суммы тарифов для всех свободных клеток неотрицательны, но среди них имеются алгебраические суммы тарифов, равные нулю, то оптимальное решение не единственное: при пересчете по циклу для клетки с нулевой алгебраической суммой тарифов мы получим оптимальное же решение, но отличное от исходного (затраты по обоим планам будут одинаковыми). В зависимости от методов подсчета алгебраических сумм тарифов для свободных клеток различают два метода отыскания оптимального решения транспортной задачи: 1.
Распределительный метод.
При этом методе для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов. 2. Метод потенциалов.
При этом методе предварительно находят потенциалы баз и потребителей, а затем вычисляют для каждой пустой клетки алгебраическую сумму тарифов с помощью потенциалов. Преимущества метода потенциалов по сравнению с распределительным методом состоят в том, что отпадает необходимость построения циклов для каждой из пустых клеток и упрощается вычисление алгебраических сумм тарифов. Цикл строится только один – тот, по которому производится пересчет. Применяя метод потенциалов, можно говорить не о знаке алгебраических сумм тарифов, а о сравнении косвенных тарифов с истинными. Требование неотрицательности алгебраических сумм тарифов заменяется условием, что косвенные тарифы не превосходят истинных. Следует иметь в виду, что потенциалы (так же как и циклы) для каждого нового базисного плана определяются заново. Назад | Содержание | Далее 3.5. Усложненные задачи транспортного типа
Выше рассмотрена классическая транспортная задача, на которой показано, как используется метод потенциалов для нахождения оптимального плана. В экономике предприятия такие задачи встречаются крайне редко. Обычно при составлении экономико-математической модели задачи транспортного типа приходится вводить целый ряд дополнительных ограничений, а затем пользоваться методом потенциалов. Ряд экономических задач легко сводимы к транспортной задаче. Рассмотрим наиболее часто встречающиеся ситуации в экономике предприятия
. 1. Отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки коммуникаций и т.д.). Это ограничение требует, чтобы в матрице перевозок, содержащей оптимальный план, определенные клетки оставались свободными. Последнее достигается искусственным завышением затрат на перевозки cij
в клетках, перевозки через которые следует запретить. При этом производят завышение величины cij
до таких значений, которые заведомо больше всех и с которыми их придется сравнивать в процессе решения задачи. 2. На предприятии необходимо определить минимальные суммарные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при решении вопросов, связанных с оптимальным размещением производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей его себестоимости. В таких задачах за критерий оптимальности принимают сумму затрат на производство и транспортировку продукции. 3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту Ai
Bj
можно провести не более q
единиц груза, то Bj
-й столбец матрицы разбивается на два столбца - 4. Поставки по определенным маршрутам обязательны и должны войти в оптимальный план независимо от того, выгодно это или нет. В этом случае уменьшают запас груза у поставщиков и спрос потребителей и решают задачу относительно тех поставок, которые необязательны. Полученное решение корректируют с учетом обязательных поставок. 5. Экономическая задача не является транспортной, но в математическом отношении подобна транспортной, т.к. описывается аналогичной моделью, например, распределение производства изделий между предприятиями, оптимальное закрепление механизмов по определенным видам работы. 6. Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателя cij
. Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице 7. необходимо в одно время распределить груз различного рода по потребителям. Задачи данного типа называются многопродуктовыми транспортными задачами. В этих задачах поставщики m
родов грузов разбиваются на m
условных поставщиков, а потребители n
родов грузов разбиваются на n
условных потребителей. С учетом этой разбивки составляют полную транспортную таблицу. При этом заметим, что некоторые маршруты Ai
Bj
должны быть блокированы (закрыты), поскольку в данной постановке задачи грузы разного рода не могут заменять друг друга. Этим маршрутам Ai
Bj
должна соответствовать очень высокая стоимость перевозки. Многопродуктовую задачу не всегда обязательно описывать одной моделью. Например, если поставки грузов различного рода независимы, тот задачу можно представить в виде комплекса транспортных задач по каждому роду груза. Однако, если между грузами Различного рода существует связь (например, одни из грузов можно заменить другими), то в общем случае исходную модель (задачу) не удается разбить на комплекс простых транспортных задач. Рассмотрим примеры задач транспортного типа. Пример 1. Одно фермерское хозяйство (A1
) имеет продовольственное зерно двух видов: 3 тыс. тонн – III класса и 4 тыс. тонн - IV класса. Второе фермерское хозяйство (A2
) также имеет зерно двух видов: 5 тыс. тонн – III класса и 2 тыс. тонн - IV класса. Зерно должно быть вывезено на два элеватора: на первый элеватор (B1
) необходимо поставить 2 тыс. тонн пшеницы III класса, 3 тыс. тонн пшеницы IV класса и остальные 2 тыс. тонн пшеницы любого класса. Аналогично второй элеватор (B2
) должен получить 8,25 тыс. тонн, из них пшеницы - 1 тыс. тонн III класса и 1,5 тыс. тонн IV класса. Стоимость перевозки в д.е. 1 тонны зерна составляет: из пункта A1
в пункты B1
и B2
- 1 и 1,5 соответственно; из пункта A2
в пункты B1
и B2
- 2 и 1 д.е. соответственно. Составить оптимальный план перевозок. Решение
Каждого поставщика условно разбиваем на две части согласно двум видам зерна ( С учетом сделанных замечаний составим первую таблицу (табл. 3.6). Таблица 3.6 Исходные данные
Перевозки от фиктивного поставщика не производятся, поэтому Таблица 3.7 Оптимальное решение
Анализ решения
. Первый поставщик поставит на первый элеватор (B1
) пшеницу III класса ( x
12
= 2); пшеницу IV класса (x
22
= 3), а также пшеницу любого класса (III или IV) (x
13
= 1 ; x
23
= 1). Второй поставщик (A2
) поставит на второй элеватор (B2
) пшеницу III класса (x
31
= 1), пшеницу IV класса (x
45
= 1,5) и частично любую пшеницу (x
36
= 4; x
46
= 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. тонн (x
56
= 1,25). Минимальные затраты на перевозку составили: Z
min
= 14 д.е. Пример 2
. Модель производства с запасами. Фирма переводит свой головной завод на производство определенного вида изделий, которые будут выпускаться в течение четыре месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет: запасов изделий, произведенных в прошлом месяце, сохраняющихся для реализации в будущем; производства изделий в течение текущего месяца; избытка производства изделий в более поздние месяцы в счет невыполненных заказов. Затраты на одно изделие в каждом месяце составляют 4 д.е. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 д.е. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере 2 д.е. в месяц. Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно. Требуется составить план, имеющий минимальную стоимость производства и хранения изделий. Решение
Задачу можно сформулировать как транспортную. Эквивалентность между элементами производственной и транспортной систем устанавливается следующим образом: Транспортная система Производственная система 1. Исходный пункт i
1. Период производства i
2. Пункт назначения j
2. Период потребления j
3. Предложение в пункте i
3. Объем производства за период i
4. Спрос в пункте j
4. Реализация за период j
5. Стоимость перевозки из i
в j
5. Стоимость производства и хранения за период i
и j
Перед нами структура транспортной модели. Для рассматриваемой задачи стоимость "перевозки" изделий из периода i
в период j
выражается как: Из определения cij
следует, что затраты в период i
при реализации продукции в тот же период i
(i
= j
) оцениваются только стоимостью производства. Если в период i
производится продукция, которая будет потребляться позже (i
< j
), то имеют место дополнительные издержки, связанные с хранением. Аналогично производство в i
–й период в счет невыполненных заказов (i
> j
) влечет за собой дополнительные расходы в виде штрафа. Например, c
11
= 4 д.е. c
24
= 4 + (0,5 + 0,5) = 5 д.е. c
41
= 4 + (2 + 2 + 2) = 10 д.е. Исходная транспортная таблица выглядит следующим образом (табл. 3.8). Таблица 3.8 Оптимальное решение
Пример 3
. Имеются три сорта бумаги в количестве 10, 8 и 5 т, которую можно использовать на издание четырех книг тиражом 8000, 6000, 15000 и 10000 экземпляров. Расход бумаги на одну книгу составляет: 0,6; 0,8; 0,4; 0,5 кг, а себестоимость тиража книги при использовании i
-го сорта бумаги задается следующей матрицей (д.е.):
Определить оптимальное распределение бумажных резервов. Решение
Задача по своему экономическому смыслу не является транспортной, в то же время можно построить математическую модель, аналогичную транспортной задаче. Потребности в бумаге легко определить, зная тираж и расход на одну книгу: 8000 * 0,6 = 4,8 т 15000 * 0,4 = 6 т 8000 * 0,6 = 4,8 т 10000 * 0,5 = 5 т Общие запасы бумаги составляют 23т, а общие потребности – 20,5 т, поэтому необходимо в таблицу ввести фиктивный тираж B
5
с нулевыми затратами. В связи с тем, что мы составляем модель относительно бумаги, а матрица cij
характеризует себестоимость печатания книги, необходимо исходную матрицу преобразовать относительно единицы бумаги (каждый столбец матрицы cij
разделим на количество бумаги, приходящейся на одну книгу). Согласно изложенному составим первую таблицу (табл. 3.9). Таблица 3.9 Исходные данные
Используя метод потенциалов, получим оптимальное решение (табл. 3.10). Таблица 3.10 Оптимальное решение
Анализ решения
. Бумаги 1-го сорта в количестве 4,8 т затрачено на издание второй книги; 2,8 т – на издание четвертой книги; 2,4 т – не использовано. Бумаги 2-го сорта затрачено: на первую книгу – 4,8 т; на издание третьей книги 1 т; на издание четвертой книги – 2,2 т; бумага 3-го сорта использована на издание третьей книги в количестве 5 т. Назад | Содержание | Далее Задача 3.1
В пунктах A
и B
находятся соответственно 150 и 90 т горючего. Пунктам 1, 2, 3 требуются соответственно 60, 70, 110 т горючего. Стоимость перевозки 1 т горючего из пункта A
в пункты 1, 2, 3 равна соответственно 60, 10, 40 тыс. руб. за 1 т соответственно, а из пункта B
в пункты 1, 2, 3 - 120, 20, 80 тыс. руб. за 1 т соответственно. Составьте план перевозок горючего, минимизирующий общую сумму транспортных расходов. Задача 3.2
Три завода выпускают грузовые автомобили, которые отправляются четырем потребителям. Первый завод поставляет 90 платформ грузовиков, второй – 30 платформ, третий – 40 платформ. Требуется поставить платформы следующим потребителям: первому – 70 штук, втором – 30, третьем – 20, четвертому – 40 штук. Стоимость перевозки одной платформы от поставщика до потребителя указана в следующей таблице (д.е.): Поставщики Потребители 1 2 3 4 I 18 20 14 10 II 10 20 40 30 III 16 22 10 20 Составьте оптимальный план доставки грузовых автомобилей Задача 3.3
Строительство магистральной дороги включает задачу заполнения имеющихся на трассе выбоин до уровня основной дороги и срезания в некоторых местах дороги выступов. Срезанным грунтом заполняются выбоины. Перевозка грунта осуществляется грузовиками одинаковой грузоподъемности. Расстояние в километрах от срезов до выбоин и объем работ указаны в следующей таблице: Поставщики Потребители Наличие грунта, т I II III А 1 2 3 10 В 2 1 3 30 С 1 2 4 20 Требуемое количество грунта, т 100 140 60 Составьте план перевозок, минимизирующий общий пробег грузовиков. Задача 3.4
Груз, хранящийся на трех складах и требующий для перевозки 60, 80, 106 автомашин соответственно, необходимо перевезти в четыре магазина. Первому магазину требуется 44 машины груза, второму – 70, третьему – 50 и четвертому – 82 машины. Стоимость пробега одной автомашины за 1 км составляет 10 д.е. Расстояния от складов до магазинов указаны в следующей таблице: Склады Магазины 1 2 3 4 1 13 17 6 8 2 2 7 10 41 3 12 18 2 22 Составьте оптимальный по стоимости план перевозки груза от складов до магазинов. Задача 3.5
На складах А, В, С находится сортовое зерно 100, 150, 250 т, которое нужно доставить в четыре пункта. Пункту 1 необходимо поставить 50 т, пункту 2 – 100, пункту 3 – 200, пункту 4 – 150 т сортового зерна. Стоимость доставки 1 т зерна со склада А в указанные пункты соответственно равна (д.е.) 80, 30, 50, 20; со склада В – 40, 10, 60, 70; со склада С -10, 90, 40, 30. Составьте оптимальный план перевозки зерна из условия минимума стоимости перевозки. Задача 3.6
Завод имеет три цеха – А, В, С и четыре склада – 1; 2; 3; 4. Цех А производит 30 тыс. шт. изделий, цех В – 40; цех С – 20 тыс. шт. изделий. Пропускная способность складов за то же время характеризуется следующими показателями: склад 1 – 20 тыс. шт. изделий; склад 2 – 30; склад 3 – 30 и склад 4 – 10 тыс. шт. изделий. Стоимость перевозки 1 тыс. шт. изделий из цеха А на склады 1, 2, 3, 4 – соответственно (д.е.): 20, 30, 40, 40; из цеха В – соответственно 30, 20, 50, 10; а из цеха С – соответственно 40, 30, 20, 60. Составьте такой план перевозки изделий, при котором расходы на перевозку 90 тыс. шт. изделий были бы наименьшими. Задача 3.7
Имеются две станции технического обслуживания (СТО), выполняющие ремонтные работы для трех автопредприятий. Производственные мощности СТО, стоимость ремонта в различных СТО, затраты на транспортировку от автопредприятий на СТО и обратно и прогнозируемое количество ремонтов в планируемом периоде на каждом автопредприятии приведены в следующей таблице: СТО Стоимость ремонта ед., д.е. Затраты на транспортировку, тыс. руб. Производственная мощность, шт. АТП-1 АТП-2 АТП-3 1 520 60 70 20 10 2 710 40 50 30 8 Потребное количество, д.е. 6 7 5 18 Требуется определить, какое количество автомашин из каждого автопредприятия необходимо отремонтировать на каждый СТО, чтобы суммарные расходы на ремонт и транспортировку были минимальными. Задача 3.8
Имеются два хранилища с однородным продуктом, в которых сосредоточено 200 и 120 т продукта соответственно. Продукты необходимо перевезти трем потребителям соответственно в количестве 80, 100 и 120 т. Расстояния от хранилищ до потребителей (8 км) следующие: Хранилище Потребители 1 2 3 1 20 30 50 2 60 20 40 Затраты на перевозку 1 т продукта на 1 км постоянны и равны 5 д.е. Определите план перевозок продукта от хранилищ до потребителей из условия минимизации транспортных расходов. Задача 3.9
Промышленный концерн имеет два заводы и пять складов в различных регионах страны. Каждый месяц первый завод производит 40,а второй 70 ед. продукции. Вся продукция, производимая заводами, должна быть направлена на склады. Вместимость первого склада равна 20 ед. продукции; второго – 30; третьего – 15; четвертого – 27; пятого – 28 ед. Издержки транспортировки продукции от завода до склада следующие (ед.): Заводы Склады 1 2 3 4 5 1 520 480 650 500 720 2 450 525 630 560 750 Распределите план перевозок из условия минимизации ежемесячных расходов на транспортировку. Задача 3.10
Три нефтеперерабатывающих завода с суточной производительностью 10, 8 и 6 млн. галлонов бензина снабжают три бензохранилища, спрос которых составляет 6, 11 и 7 млн. галлонов. Бензин транспортируется в бензохранилища по трубопроводу. Стоимость перекачки бензина на 2 км составляет 5 д.е. на 100 галлонов. Завод 1 не связан с хранилищем 3. Расстояние от заводов до бензохранилищ следующее: № завода Бензохранилища 1 2 3 1 100 150 - 2 420 180 60 3 200 280 120 Сформулируйте соответствующую транспортную задачу и решите на минимум транспортных затрат. Задача 3.11
Автомобили перевозятся на трайлерах из трех центров распределения пяти продавцам. Стоимость перевозки в расчете на 1 км пути, пройденного трайлером, равна 60 д.е. Один трайлер может перевозить 15 автомобилей. Стоимость перевозок не зависит от того, насколько полно загружается трайлер. В приведенной ниже таблице указаны расстояния между центрами распределения и продавцами, а также величины, характеризующие ежемесячный спрос и объемы поставок, исчисляемые количеством автомобилей: Центр распределения Продавцы Объем поставок, шт. 1 2 3 4 5 1 80 120 180 150 50 300 2 60 70 50 65 90 350 3 30 80 120 140 90 120 Спрос на автомобили, шт. 110 250 140 150 120 770 Определите минимальные затраты на доставку автомобилей. Задача 3.12
Решите задачу распределения станков четырех различных типов по шести типам работ. Пусть имеются 30, 45, 25 и 20 станков соответствующих типов. Шесть типов работ характеризуются 30, 20, 10, 40, 10 и 10 операциями соответственно. На станке 3 не может выполняться операция 6. Исходя из коэффициентов стоимости операции, представленных в следующей таблице, постройте модель и выполните оптимальное распределение станков по работам: Тип станков Тип работы 1 2 3 4 5 6 1 10 1 3 7 14 8 2 4 8 12 2 10 7 3 12 3 14 6 2 - 4 11 12 9 3 1 3 Задача 3.13
В данной транспортной задаче суммарный спрос превосходит суммарный объем производства. Пусть штрафы за недопоставку единицы продукции в пункты назначения 1, 2 и 3 равны соответственно 5, 3 и 2. Исходные данные следующие: Заводы Потребители Объем производства, шт. 1 2 3 A
1
3 2 4 50 A
2
5 4 5 75 A
3
1 6 7 30 Потребность, шт. 60 40 70 Найдите оптимальное решение. Для задач 3.14 – 3.25 дано следующее условие.
Имеются три пункта поставки однородного груза - A
1
; A
2
; A
3
и пять пунктов потребления этого груза B
1
; B
2
; B
3
; B
4
; B
5
. В пунктах A
1
; A
2
; A
3
находится груз a
1
; a
2
; a
3
соответственно. Груз необходимо доставить в пункты B
1
; B
2
; B
3
; B
4
; B
5
в количестве b
1
; b
2
; b
3
; b
4
; b
5
соответственно. Расстояния между пунктами в км заданы следующей матрицей:
Требуется найти оптимальный план закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей, используя параметры, представленные ниже. Задача 3.14
Задача 3.15
Задача 3.16
Задача 3.17
Задача 3.18
Задача 3.19
Задача 3.20
Задача 3.21
Задача 3.22
Задача 3.23
Задача 3.24
Задача 3.25
Назад | Содержание | Далее 4.1. Компоненты и классификация моделей массового обслуживания
Системы массового обслуживания - это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания. С позиции моделирования процесса массового обслуживания ситуации, когда образуются очереди заявок (требований) на обслуживание, возникают следующим образом. Поступив в обслуживающую систему, требование присоединяется к очереди других (ранее поступивших) требований. Канал обслуживания выбирает требование из находящихся в очереди, с тем чтобы приступить к его обслуживанию. После завершения процедуры обслуживания очередного требования канал обслуживания приступает к обслуживанию следующего требования, если таковое имеется в блоке ожидания. Цикл функционирования системы массового обслуживания подобного рода повторяется многократно в течение всего периода работы обслуживающей системы. При этом предполагается, что переход системы на обслуживание очередного требования после завершения обслуживания предыдущего требования происходит мгновенно, случайные моменты времени. Примерами систем массового обслуживания могут служить: 1. посты технического обслуживания автомобилей; 2. посты ремонта автомобилей; 3. персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач; 4. станции технического обслуживания автомобилей; 5. аудиторские фирмы; 6. отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий; 7. телефонные станции и т. д. Основными компонентами системы массового обслуживания любого вида являются: входной поток поступающих требований или заявок на обслуживание; дисциплина очереди; механизм обслуживания. Входной поток требований
. Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (требования поступают группами в систему). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием. Дисциплина очереди
- это важный компонент системы массового обслуживания, он определяет принцип, в соответствии с которым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами: первым пришел — первый обслуживаешься; пришел последним — обслуживаешься первым; случайный отбор заявок; отбор заявок по критерию приоритетности; ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»). Механизм обслуживания
определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продолжительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процедуры. Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований». Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода обслуживающего прибора по истечений некоторого ограниченного интервала времени. Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживание. Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно. Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований. Предметом теории массового обслуживания
является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам. Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса, происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские. В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими. Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему. В случае немарковских процессов задачи исследования систем массового обслуживания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ. Независимо от характера процесса, протекающего в системе массового обслуживания, различают два основных вида СМО: системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь; системы с ожиданием (очередью), в которых заявка, поступившая в момент, когда все каналы обслуживания заняты, становится в очередь и ждет, пока не освободится один из каналов. Системы массового обслуживания с ожиданием делятся на системы с ограниченным ожиданием и системы с неограниченным ожиданием. В системах с ограниченным ожиданием может ограничиваться: длина очереди; время пребывания в очереди. В системах с неограниченным ожиданием заявка, стоящая в очереди, ждет обслуживание неограниченно долго, т.е. пока не подойдет очередь. Все системы массового обслуживания различают по числу каналов обслуживания: одноканальные системы; многоканальные системы. Приведенная классификация СМО является условной. На практике чаще всего системы массового обслуживания выступают в качестве смешанных систем. Например, заявки ожидают начала обслуживания до определенного момента, после чего система начинает работать как система с отказами. 4.2. Определение характеристик систем массового обслуживания
Простейшей одноканальной моделью с вероятностными входным потоком и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид
где Плотность распределения длительностей обслуживания:
где Потоки заявок и обслуживании простейшие. Пусть система работает с отказами
. Необходимо определить абсолютную и относительную пропускную способность системы. Представим данную систему массового обслуживания в виде графа (рис. 4.1), у которого имеются два состояния: S0
- канал свободен (ожидание); S1
- канал занят (идет обслуживание заявки).
Рис. 4.1. Граф состояний одноканальной СМО с отказами Обозначим вероятности состояний: P0
(t) - вероятность состояния «канал свободен»; P1
(t) - вероятность состояния «канал занят». По размеченному графу состояний (рис. 4.1) составим систему дифференциальных уравнений Колмогорова для вероятностей состояний:
Система линейных дифференциальных уравнений (4.3) имеет решение с учетом нормировочного условия P0
(t) + P1
(t) = 1 . Решение данной системы называется неустановившимся, поскольку оно непосредственно зависит от t
и выглядит следующим образом:
P1
(t) = 1 - P0
(t) = 1 . (4.5) Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P0
(t) есть не что иное, как относительная пропускная способность системы q
. Действительно, P0
- вероятность того, что в момент t
канал свободен и заявка, пришедшая к моменту t
, будет обслужена, а следовательно, для данного момента времени t
среднее отношение числа обслуженных заявок к числу поступивших также равно P0
(t), т. е. q = P0
(t), (4.6) По истечении большого интервала времени (при
Зная относительную пропускную способность, легко найти абсолютную. Абсолютная пропускная способность (А) - среднее число заявок, которое может обслужить система массового обслуживания в единицу времени:
Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал занят»:
Данная величина Pотк
может быть интерпретирована как средняя доля необслуженных заявок среди поданных. Пример 4.1.
Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания (ЕО) для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей Требуется определить в установившемся режиме предельные значения: относительной пропускной способности q
; абсолютной пропускной способности А
; вероятности отказа Pотк
; Сравните фактическую пропускную способность СМО с номинальной, которая была бы, если бы каждый автомобиль обслуживался точно 1,8 часа и автомобили следовали один за другим без перерыва. Решение
1. Определим интенсивность потока обслуживания: 2. Вычислим относительную пропускную способность: Величина q
означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост ЕО автомобилей. 3. Абсолютную пропускную способность определим по формуле: Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час. 4. Вероятность отказа: Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании. 5. Определим номинальную пропускную способность системы: Оказывается, что Аном
в 1,5 раза Рассмотрим теперь одноканальную СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N
-требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость. Граф состояний СМО в этом случае имеет вид, показанный на рис. 4.2.
Рис. 4.2. Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения) Состояния СМО имеют следующую интерпретацию: S0
- «канал свободен»; S1
- «канал занят» (очереди нет); S2
- «канал занят» (одна заявка стоит в очереди); ……………………………………………………. Sn
- «канал занят» (n
-1 заявок стоит в очереди); SN
- «канал занят» (N
- 1 заявок стоит в очереди). Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:
где Решение приведенной выше системы уравнений (4.10) для нашей модели СМО имеет вид Тогда Следует отметить, что выполнение условия стационарности Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N
- 1): вероятность отказа в обслуживании заявки: относительная пропускная способность системы:
|