- •Б.К. Алабин
- •1.2. Основные понятия и определения исследования операций
- •1.3. Общая постановка задачи исследования операций
- •Тема 2 индексный метод (теория графов)
- •2.1. Основные понятия и определения индексного метода (им)
- •2.2. Постановка задачи маршрутизации в им
- •2.3. Идея решения задачи
- •2.4. Алгоритм решения задачи с помощью произвольного дерева маршрутов
- •2.5. О порядковой функции
- •2.6. Общая теория индексного метода на матрице орграфа
- •2.7. Общий алгоритм решения задачи маршрутизации на матрице орграфа
- •2.8. Иллюстративный пример
- •2.9. Последовательные графы в им
- •2.10. Решение задачи распределения ресурсов индексным методом
- •3.4. Условия, которым должна удовлетворять задача, описываемая моделью дп
- •3.5. Вычислительная схема дп для обратного хода
- •3.6. Особенности вычислительной схемы дп для прямого хода
- •3.7. Основные достоинства метода дп
- •3.8. Типовые задачи в моделях дп
- •Тема 4 методы линейного программирования (лп)
- •4.1. Систематизация моделей лп
- •4.2. Возможные исходы решения задач лп
- •4.3. Транспортная задача (т-задача)
- •Метод потенциалов для оценки Δij в т-задаче
- •Замечания к решению т-задачи
- •4.4. Задача «о назначениях»
- •4.5. Задача планирования производства при фиксированном фонде времени
- •Иллюстративный пример
- •Тема 5 задача и модель «черного ящика»
- •5.1. Общие замечания
- •5.2. Содержательная постановка задачи
- •5.3. Формальная постановка задачи
- •5.4. Математическая модель и математическая постановка задачи
- •5.5. О решении задачи
- •5.6. Иллюстративный пример
- •Рекомендуемая литература
- •Содержание
Тема 4 методы линейного программирования (лп)
4.1. Систематизация моделей лп
В отличие от ДП в ЛП разработано несколько методов решения задач. Эти методы, очевидно, связаны с различными типами моделей ЛП. Попытаемся выяснить, с какими.
Прежде всего следует отметить, что показатель эффективности d ЛП (целевая функция) есть линейная функция от переменных управления. Чтобы иметь экстремумы, такая функция должна быть ограничена. Действительно, любая модель ЛП помимо линейного показателя эффективности содержит ограничения на переменные управления в виде линейных равенств или неравенств. Поэтому для выяснения типов моделей ЛП достаточно задать типы показателя эффективности и типы ограничений на переменные управления.
Положим, что переменные состояния в какой-то задаче ЛП представлены двумя независимыми категориями. Им соответствуют две категории состояний системы: А1 = {аi} и А2 = {аj}. Тогда общее состояние системы есть пара (ai, aj), где аi А1, aj А2. Множество таких пар образует декартово произведение А1 × А2 = {(ai, aj)}, а каждой паре (ai, aj) приписывается цена с (ai, aj) = сij и количество объектов системы в этом состоянии: х(ai, aj) = хij (переменные управления). Цена сij обычно называется стоимостью перехода от ai к aj.
Рассмотрим пару множеств А1 и А2. Принято различать следующие случаи их задания.
1-й случай: А1 А, А2 = . Пример: А есть множество типов изделий, А1 – множество выпускаемых типов изделий на данном предприятии. Тогда сi – цена одного изделия, а хi – количество изделий i-го типа. Целевая функция при этом выражается в векторной форме:
2-й случай: А1 А, А2 В. Множества А и В принципиально различны. Пример: А есть типы изделий, В – типы технологий. Тогда сij – стоимость одного изделия, а хij – количество изделий i-го типа из А1, изготовленных по j-й технологии из А2. Целевая функция выражается в матричной форме:
с разнородными наборами А1 и А2.
3-й случай: А1 А, А2 А. Пример: множество А – различные пункты, А1 – пункты отправления, А2 – пункты назначения. Тогда сij – цена доставки, а хij – количество единиц продукции, доставляемых из ai в aj; ai А1, aj А2. Целевая функция выражается в матричной форме:
с однородными наборами А1 и А2.
Что касается ограничений на переменные управления хi и xij, то здесь достаточно различать лишь два случая: 1) хi, xij 0 и 2) хi, xij = = 0,1 (т.е. непрерывные или дискретные переменные), так как здесь возникают принципиально различные алгоритмы.
Полученные результаты полезно представить в следующем виде (табл. 1).
Таблица 1
Типы показателя эффективности |
Векторная форма
|
Матричная форма
| ||||
А1 А, А2 В (разнородные наборы) |
А1 А, А2 А (однородные наборы) | |||||
Типы ограничений |
хi 0 |
хi = 0,1 |
xij 0 |
xij = 0,1 |
xij 0 |
xij = 0,1 |
Тип модели |
(1) |
(2) |
(3) |
(4) |
(5) |
(6) |
Для каждого из шести типов моделей ЛП возникает свой тип задач, которые, как правило, имеют теоретически разработанные методы решения:
Задачи самого общего вида. Специально для таких задач разработан универсальный метод решения – симплекс-метод.
Частный случай (1), но эффективных алгоритмов в ЛП нет. В принципе можно свести к симплекс-методу.
Задачи распределения или назначения общего вида. Сводятся к типу (1), но некоторые задачи имеют специфические алгоритмы.
Частный случай типа (3), эффективных алгоритмов в ЛП нет.
Т-задачи. Наиболее разработанный тип задач под названием «Транспортные задачи». Имеют хорошо разработанную математическую теорию решения (распределительный метод, метод потенциалов, обобщенный венгерский метод).
Частный случай типа (5): задачи «О назначениях». Весьма эффективно решаются венгерским методом, но могут быть решены любым алгоритмом Т-задачи.
Замечания
Все методы ЛП, кроме симплекс-метода, привязаны к специфике решаемых классов задач и поэтому неотделимы от их конкретных математических моделей.
Решение конкретной прикладной задачи осуществляется сведением (если это возможно) ее модели к типовой модели какого-либо метода.