- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 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. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
2.2. Решение задач линейного программирования графическим методом
Решение задачи линейного программирования графическим методом производится по следующему алгоритму:
1. Интерпретируется система ограничений. Строится область допустимых решений.
2. Строится произвольная линия уровня.
Замечание: При решении ЗЛП графическим методом удобнее всего строить линию уровня при Z=0.
3. Выбирается направление перемещения линии уровня.
Замечание1: Направление перемещения линии уровня выбирается с учетом направления наибольшего изменения функции. Это направление определяется с помощью градиента:
grad Z = =(,)
Если решается задача на max, то выбирается направление вектора градиента (направление вектора ). В противном случае – направление антиградиента (вектора -).
Замечание 2: С помощью вектора можно построить линию уровня. Она строится перпендикулярно градиенту, через точку (0,0).
4. Перемещается линия уровня, до тех пор, пока не найдено решение ЗЛП.
Замечание 1: При решении ЗЛП возможны следующие случаи:
Рис. 8 Рис. 9.
Рис. 10 Рис. 11
На рис. 8 показан случай, когда минимум и максимум целевой функции найдены и находятся соответственно в точках max и min. Во втором случае (рис. 9) минимум целевой функции существует. Однако область допустимых решений не ограничена сверху, следовательно, максимума у целевой функции нет. В третьем случае (рис. 10) нет ни минимума, ни максимума функции. На рис.11 ЗЛП имеет бесконечно много решений.
Пример1: Решить ЗЛП графическим методом. Найти:
при
Решение.
Найдем градиент: (2;-3).
Построим область допустимых значений. Для этого построим прямые, соответственные ограничениям:
1: |
A |
B |
|
2: |
A |
B |
|
3: |
A |
B |
-6 |
0 |
4 |
0 |
|
0 |
4 | ||||
0 |
4 |
0 |
3 |
|
0 |
4 |
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
C |
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Решение находится, исходя из решения системы:
Тогда: =; =иmax Z= –
Ответ: Z= –в.
Пример 2. Решить ЗЛП графическим методом. Найти:
при
Решение.
Задачи, представленные в канонической форме можно решать графическим методом только в том случае, если разность между порядком и рангом системы ограничений равна 2. В данном случае: 5-3=2.
Представим задачу таким образом, чтобы можно было решать графическим методом. Для этого в системе ограничений выразим переменные ,ичерези.
Так как все переменные неотрицательны, то можно составить систему неравенств:
Подставим в целевую функцию вместо ,исоответственные значения:
Таким образом, ЗЛП имеет вид:
при
Найдем градиент: (1;1).
Построим область допустимых значений. Для этого построим прямые, соответственные ограничениям:
1: |
A |
B |
|
2: |
A |
B |
|
3: |
A |
B |
7 |
0 |
2 |
0 |
|
-5 |
0 | ||||
0 |
2 |
0 |
6 |
|
0 |
4 |
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Область допустимых решений не ограничена сверху. Значит, решений нет.
Ответ: Решений нет.