- •Глава I элементы линейного программирования Лекция 1
- •1. Элементы аналитической геометрии
- •1.1. Основные понятия и определения
- •1.2. Решение систем т линейных уравнений с двумя переменными
- •Лекция 2
- •2. Графический метод
- •2.1. Постановка задачи
- •2.2. Алгоритм решения задач
- •2.3. Выбор оптимального варианта выпуска изделий
- •Лекция 3
- •3. Симплексный метод
- •3.1. Общая постановка задачи
- •3.2. Алгоритм симплексного метода
- •Лекция 3.
- •3.3. Анализ эффективности использования производственного потенциала предприятия
- •3.4. Альтернативный оптимум
- •Лекция 4
- •4. Двойственность в линейном программировании
- •4.1. Виды двойственных задач и составление их математических моделей
- •4.2. Основные теоремы двойственности
- •Исходная задача
- •Двойственная задача
- •Исходная задача
- •Двойственная задача
- •Лекция 6
- •5. Транспортная задача
- •5.1. Общая постановка задачи
- •5.2. Нахождение исходного опорного решения
- •5.3. Определение эффективного варианта доставки изделий к потребителю
- •5.4. Проверка найденного опорного решения на оптимальность
- •5.5. Переход от одного опорного решения к другому
- •5.6. Альтернативный оптимум в транспортных задачах
- •Вырожденность в транспортных задачах
- •Открытая транспортная задача
- •Определение оптимального варианта перевозки грузов
- •Приложение транспортных моделей к решению некоторых экономических задач.
- •Выбор оптимального варианта использования производственного оборудования
- •Лекция 10 Целочисленное программирование
- •Параметрическое программирование
- •1. Постановка задачи
- •2. Линейное программирование с параметром в целевой функции
- •Определение диапазона оптимального решения выпуска продукции при изменении условий реализации
- •Транспортная параметрическая задача
- •Лекция Задача о назначениях
- •Нелинейное программирование Общая постановка задачи
- •Графический метод
- •Дробно-линейное программирование
- •Алгоритм решения
- •Экономическая интерпретация задач дробно-линейного программирования
- •Применение дробно-линейного программирования для определения себестоимости изделий
- •Сведение экономико-математической модели дробно-линейного программирования к задаче линейного программирования
- •Метод множителей Лагранжа
- •Динамическое программирование
- •Оптимальная стратегия замены оборудования
- •Сетевые модели
- •Выбор оптимальной стратегии развития предприятия в условиях трансформации рынка
- •Принятие решения о замене оборудования в условиях неопределённости и риска
- •Элементы системы массового обслуживания (смо)
- •1. Формулировка задачи и характеристики смо
- •2. Смо с отказами
- •3. Смо с неограниченным ожиданием
- •4. Смо с ожиданием и с ограниченной длиной очереди
Выбор оптимального варианта использования производственного оборудования
Задача. На предприятии имеется три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 ч. Каждая операция должна выполняться соответственно 100, 120, 70, 110, 130 ч.
Определить, сколько времени и на какую операцию нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей.
Производительность каждой группы станков на каждую операцию задана матрицей
.
РЕШЕНИЕ. Воспользуемся алгоритмом решения закрытой транспортной задачи.
Так как в задаче требуется найти максимум, а согласно алгоритму транспортной задачи находится минимум, тарифы умножим на (-1).
B j Ai |
1 |
2 |
3 |
4 |
5 |
ui |
100 |
120 |
70 |
110 |
130 |
||
1 100 |
-3 40 |
-5
|
-11
|
-10
|
-5 60 |
0 |
2 250 |
-5 60 |
-10 120 |
-15 70 |
-3 |
-2 |
-2 |
3 180 |
-4
|
-8
|
-6
|
-12 110 |
-10 70 |
-5 |
vj |
-3 |
-8 |
-13 |
-7 |
-5 |
|
Находим оценки свободных клеток: , , .
Так как > 0, перераспределим грузы, получим
60
130
Полученное перераспределение грузов занесём в табл.
B j Ai |
1 |
2 |
3 |
4 |
5 |
ui |
100 |
120 |
70 |
110 |
130 |
||
1 100 |
-3 40 |
-5
|
-11
|
-10 60 |
-5
|
0 |
2 250 |
-5 60 |
-10 120 |
-15 70 |
-3 |
-2 |
-2 |
3 180 |
-4
|
-8
|
-6
|
-12 50 |
-10 130 |
-2 |
vj |
-3 |
-8 |
-13 |
-10 |
-8 |
|
Оценки свободных клеток составляют
, , , , , , , .
Найденное решение является оптимальным, так как все оценки свободных клеток отрицательные. Итак,
Таким образом, на первой группе станков целесообразно выполнять операции 1 и 4 продолжительностью 40 и 60 ч соответственно, на второй группе – операции 1, 2 и 3 продолжительностью 60, 120 и 70 ч соответственно, на третьей группе – операции 4 и 5 продолжительностью 50 и 130 ч соответственно. При этом максимальное число обработанных деталей составит 5170 шт.