Учебное пособие: Методы исследования операций
при ограничениях
или вероятностных ограничениях
где My — математическое ожидание по у; Р{gi (х)£ b} — вероятность того, что выполняется условие gi (х)£ b.
6. Дискретное программирование, если на переменные xj наложено условие дискретности (например, целочисленности): xj — целое, j=1,2,…,n1£п.
7. Эвристическое программирование применяют для решения тех задач, в которых точный оптимум найти алгоритмическим путем невозможно из-за огромного числа вариантов. В таком случае отказываются от поиска оптимального решения и отыскивают достаточно хорошее (или удовлетворительное с точки зрения практики) решение. При этом пользуются специальными приемами — эвристиками, позволяющими существенно сократить число просматриваемых вариантов. Эвристические методы также применяют, когда оптимальное решение в принципе может быть найдено (т.е. задача алгоритмически разрешима), однако для этого требуются объемы ресурсов, значительно превышающие наличные.
По содержательной постановке выделяют следующие типичные классы задач исследования операций:
1) управления запасами,
2) распределения ресурсов,
3) ремонта и замены оборудования,
4) массового обслуживания,
5) упорядочения,
6) сетевого планирования и управления,
7) выбора маршрута,
8) комбинированные.
Из перечисленных выше методов математического программирования наиболее развитым и законченным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.
Линейное программирование
Несмотря на требование линейности целевой функции и ограничений, в рамки линейного программирования укладываются задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи, задачи теории расписаний и т. д.
Определение оптимального ассортимента. Имеется р видов ресурсов в количествах а1, а2, ..., аi, ..., аp и q видов изделий. Задана матрица А=||aik||, где аik характеризует нормы расхода i-го ресурса на единицу k-го изделия (k = 1, 2, ..., q).
Эффективность выпуска единицы k-го изделия характеризуется показателем сi, удовлетворяющим условию линейности.
Определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности принимает наибольшее значение.
Количество единиц k-го изделия, выпускаемых предприятием, обозначим хk. Тогда математическая модель задачи имеет такой вид:
найти
(1.3)
при ограничениях
(1.4)
Кроме ограничения по ресурсам (1.3), в модель могут быть введены дополнительные ограничения на планируемый выпуск продукции xj³xj0, условия комплектности для сборки xi : хj : xk. = bi : bj : bk для всех i, j, k и т. д.
Оптимальное распределение взаимозаменяемых ресурсов. Имеются т видов взаимозаменяемых ресурсов а1, а2, ..., аi, ..., аm используемых при выполнении п различных работ в объеме b1, b2, …, bn.