![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Некоторые модели задач ЦЛП.
Задачи с неделимостью. Класс задач с неделимостями представляется двумя типами моделей. Первый тип моделей это обычные целочисленные модели ЛП. Т.е.
К такой модели сводится задача определения оптимальной производственной программы предприятия с индивидуальным или мелкосерийным типом производства. В этом случае Приведем примеры задач такого типа. 1)Пусть есть m видов транспортных единиц для перевозки груза Построим модель. Обозначим через xij - количество транспортных средств i– ого вида идущих в j- ом направлении. Тогда ограничения на фонд времени ограничения на доставку грузов ограничения на неизвестные Условие целочисленности неизвестных обязательна, так как это количество транспортных средств. 2) Задача про ранец. Есть n предметов Введем переменные xj, которые принимают значения тогда задача про ранец запишется так В других вариантах этой модели может быть несколько типов ограничений, например, ограничения не только на суммарную массу предметов, но и на суммарный объем и т.д.Такие задачи называются багатомерными задачами про ранец. А если, предположить, что каждый предмет может загружаться не в одном экземпляре, а в нескольких, то ограничения
Экстремальные комбинаторные задачи. Комбинаторные экстремальные задачи могут быть решены методом проб и ошибок, т.е. имеют чисто переборный характер, так как варианты решений задач или известны, или легко комбинируются. 1)Пример задачи: задача про назначения. Пусть есть работ n и n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами cij Иначе говоря, решение этой задачи представляет собой перестановку (p1, p2, …, pn), каждое из чисел описывается соответствием Это типовая экстремально комбинированная задача. Ее решение путем прямого перебора, т.е. вычисление значении целевой функции при всех перестановках и сравнения их, практически невозможно при больших n, так как число перестановок будет Элементы матрицы Х должны удовлетворять следующим условиям Эти условия говорят, что в каждой строке и в каждом столбце матрицы Х есть только по одной единице. Иначе говоря, каждый кандидат имеет работу и каждая работа имеет своего кандидата. Эти назначения должны быть такими, чтобы минимизировать суммарные затраты, получаем целевую функцию Условие, что xij это булевая переменная можно записать так 2) Задача про коммивояжера. Пусть n есть городов. Известна матрица расстояний между любой парой городов Введем неизвестные Тогда получаем задачу Первая группа ограничений говорит о том, что коммивояжер выезжает из каждого города один раз, а вторые о том, что он один раз въезжает в каждый город.
ЛЕКЦИЯ 11.
|