- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 1
- •Блок 1.
- •1.1. Предмет и задачи исследования операций
- •1.2. Основные понятия и принципы исследования операций
- •1.3. Математические модели операций
- •1.4. Понятие линейного программирования
- •1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
- •1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий
- •1.7. Примеры экономических задач линейного программирования. Задача о смесях
- •1.8. Примеры экономических задач линейного программирования. Транспортная задача
- •1.9. Основные виды записи задач линейного программирования
- •1.10. Способы преобразования
- •1.11. Переход к канонической форме
- •1.12. Переход к симметричной форме записи
- •Блок 2.
- •2.1. Геометрическая интерпретация задачи линейного программирования
- •2.2. Решение задач линейного программирования графическим методом
- •2.3. Свойства решений задачи линейного программирования
- •2.4. Общая идея симплексного метода
- •2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
- •2.6. Признак оптимальности опорного плана. Симплексные таблицы
- •2.7. Переход к нехудшему опорному плану.
- •2.8. Симплексные преобразования
- •2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
- •2.10. Признак неограниченности целевой функции
- •2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание
- •2.12. Понятие двойственности для симметричных задач линейного программирования
- •3.1. Несимметричные двойственные задачи
- •3.2. Открытая и закрытая модели транспортной задачи
- •3.3. Построение начального опорного плана. Правило "Северо-западного угла"
- •3.4. Построение начального опорного плана. Правило минимального элемент
- •3.5. Построение начального опорного плана. Метод Фогеля
- •3.6. Метод потенциалов
- •3.7. Решение транспортных задач с ограничениями по пропускной способности
- •3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
- •3.9. Сущность методов дискретной оптимизации
- •3.10. Задача выпуклого программирования
- •3.11. Метод множителей Лагранжа
- •3.12. Градиентные методы
- •4.1. Методы штрафных и барьерных функций
- •4.2. Динамическое программирование. Основные понятия. Сущность методов решения
- •4.3. Стохастическое программирование. Основные понятия
- •4.4. Матричные игры с нулевой суммой
- •4.5. Чистые и смешанные стратегии и их свойства
- •4.6. Свойства чистых и смешанных стратегий
- •4.7. Приведение матричной игры к злп
- •4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания
- •4.9. Потоки событий
- •4.10. Схема гибели и размножения
- •4.11. Формула Литтла
- •4.12. Простейшие системы массового обслуживания
- •2. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
3.7. Решение транспортных задач с ограничениями по пропускной способности
В некоторых случаях в условии транспортной задачи накладываются дополнительные ограничения на пропускную способность линии связи. Будем их обозначать . Тогда говорят о разновидности транспортных задач – транспортных задачах с ограничениями по пропускной способности. Все ограничения записываются в левом нижнем углу ячейки. Они означают, что больше чем записано в ячейку загрузить нельзя.
Решаются такие задачи обычным образом, но с дополнительными особенностями.
Алгоритм решения транспортных задач с ограничениями по пропускной способности:
Построение начального опорного плана можно осуществлять любым методом (правило северо-западного угла, минимального элемента, метод Фогеля). Лучше всего: по правилу минимального элемента. Особенность построения начального опорного плана заключается в следующем: в выбранную ячейку ставится минимальное из чисел ,и. Если было выбрано одно из чиселили, то говорят, что заполненная ячейка – базисная. Если же в ячейку записывается число, то ячейку назовем дополнительной. После заполнения распределительной таблицы для транспортной задачи с ограничениями по пропускной способности может остаться в некоторых столбцах и строках нераспределенный груз. В этом случае вводятся дополнительные строка и столбец, загрузка которых равна объему нераспределенного груза, а тарифы каждой ячейки, исключая (m+1, n+1), равны М. М – бесконечно большое, положительно число. В ячейке (m+1, n+1) тариф равен 0. В результате базисных переменных должно быть m+n-1.
Расчет потенциалов производится по базисным ячейкам. Расчет оценок свободных и дополнительных ячеек производится обычным образом. Однако, для оптимальности опорного плана необходимо, чтобы оценки дополнительных ячеек были неположительны. Для свободных ячеек оценки должны быть неотрицателтьны, а для базисных равны 0.
Если полученный опорный план не оптимален, то обычным образом строят цикл. производят перемещение груза по циклу и снова определяют оптимальность полученного решения.
Пример: Решить транспортную задачу с ограничениями по пропускной способности:
520 520 |
80 |
140 |
90 |
130 |
80 | |
220 |
5 + 10 БП |
8 v
|
7 v 60 |
2 130 БП |
1 – 80 БП |
-2 |
140 |
6 70 БП |
3 70 70 ДП |
5 v
|
4 v 70 |
6 v
|
-1 |
160 |
7 – 0 БП |
4 70 БП |
2 90 БП |
3 v
|
2 + v
|
0 |
7 |
4 |
2 |
4 |
3 |
|
Базисных переменных: 5+3-1=7. Дополнительная переменная 1.
Сосчитаем оценки:
=8-(-2+4)=6>0 =5-(2-1)=4>0 =3-(4+0)=-1<0 |
=7-(-2+2)=7>0 =4-(4-1)=3>0 =2-(3+0)=-1<0 |
=3-(4-1)=0=0 =6-(3-1)=4>0 |
Получились две отрицательные оценки. Строим цикл.
520 520 |
80 |
140 |
90 |
130 |
80 | |
220 |
5 10 БП |
8 v
|
7 v 60 |
2 130 БП |
1 80 БП |
-1 |
140 |
6 70 БП |
3 70 70 ДП |
5 v
|
4 v 70 |
6 v
|
0 |
160 |
7 v
|
4 70 БП |
2 90 БП |
3 v
|
2 0 БП |
0 |
6 |
4 |
2 |
3 |
2 |
|
Базисных переменных: 5+3-1=7. Дополнительная переменная 1.
Сосчитаем оценки:
=8-(-1+4)=5>0 =5-(2+0)=3>0 =3-(3+0)=0=0 |
=7-(-1+2)=6>0 =4-(3+0)=1>0 =7-(6+0)=1>0 |
=3-(4+0)=-1<0 =6-(2+0)=4>0 |
Полученный план оптимален. Z=5*10+2*130+1*80+6*70+3*70+4*70+ +2*90+2*0=1480
Ответ: Z=1480.