- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 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.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
Существует несколько приемов нахождения начального опорного плана в зависимости от вида системы ограничений.
Случай 1:
Пусть система ограничений представлена в каноническом виде:
().
Определение 1: Говорят, что ограничение в ЗЛП имеет предпочтительный вид, если при неотицательной правой части () левая часть уравнения содержит переменную с коэффициентом 1, которая в другие уравнения системы входит с коэффициентом, равным 0.
Пример 1:
В данном примере первое и второе уравнения имеют предпочтительный вид, так как в первом есть переменная , коэффициент у которой 1, а в остальные уравнения данная переменная не входит; во втором такая переменная -.
Определение 2: Переменная, входящая в одно из уравнений системы с коэффициентом, равным 1, а в остальные с коэффициентом, равным 0, называется предпочтительно переменной.
В примере 1 в первом уравнении предпочтительная переменная – , во втором –. В третьем уравнении предпочтительных переменных нет.
Определение 3: Говорят, что система уравнений имеет предпочтительный вид, если каждое уравнение системы имеет предпочтительный вид.
Если система имеет предпочтительный вид, то начальное опорное решение находится следующим образом: все предпочтительные переменные будут базисными, а остальные свободными. Базисные переменные приравниваются к свободным членам, а свободные к нулю. Полученное решение является начальным опорным планом.
Пример 2:
Система имеет предпочтительный вид. Предпочтительные переменные (соответственно уравнениям) , и . Следовательно, решение ЗЛП имеет вид: (13, 0, 56, 0, 4).
Случай 2.
Пусть система ограничений ЗЛП представлена в виде:
(),
()
().
Приведем систему к каноническому виду. Для этого прибавим к левым частям неравенств новые неотрицательные переменные.
(),
()
().
Переменные () являются предпочтительными. Случай 2 свелся к случаю 1.
Случай 3.
Пусть система ограничений ЗЛП представлена в виде:
(),
()
().
Система представлена в каноническом виде. однако, в отличие от случая 1, среди уравнений системы нет таких, которые представлены в предпочтительном виде. В этом случае говорят, что есть необходимость решать М-задачу. Для того, чтобы построить М-задачу необходимо прибавить к каждому уравнению системы ограничений дополнительные переменные. Будем их обозначать .будем называть искусственным базисом. Все переменные искусственного базиса – неотрицательны. В целевую функцию они входят с коэффициентом М (бесконечно большое положительное число). Знак коэффициента определяется в зависимости от того, какая ЗЛП решается. Если ЗЛП на максимум, то коэффициент (–М). В противном случае – (+М). Таким образом ЗЛП имеет вид:
при
(),
()
()
().
Переменные () являются предпочтительными. Случай 3 свелся к случаю 1.
Теорема 1: Если в оптимальном плане М-задачи все искусственные переменныебудут равны 0, то планявляется оптимальным для исходной задачи.
Теорема 2: Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных не равна 0, то исходная задача не имеет допустимых планов, т.е. ее условия несовместны.
Случай 4.
Пусть система ограничений ЗЛП представлена в виде:
(),
()
().
Приведем систему к каноническому виду. Для этого вычтем из левых частей неравенств новые неотрицательные переменные.
(),
()
().
Переменные () не являются предпочтительными. Случай 4 свелся к случаю 3.
Рассмотрены всевозможные варианты составления начального опорного плана. Однако, следует отметить, что на практике чаще всего встречаются смешанные системы ограничений, т.е. системы где есть уравнения, содержащие предпочтительную переменную, не содержащие таковую, неравенства. Для каждого ограничения такой системы находится своя предпочтительная переменная.
Пример 3: Составить начальный опорный план при решении ЗЛП:
при
Решение.
Первое уравнение системы имеет предпочтительный вид (случай 1). Предпочтительная переменная . Второе уравнение не содержит предпочтительной переменной (случай 2). Необходимо добавить одну переменную искусственного базиса. Получим уравнение:
.
В целевую функцию новая переменная войдет с коэффициентом, равным –М.
Третье ограничение имеет вид неравенства ≤ (случай 2). Необходимо добавить дополнительную переменную . Она и будет иметь предпочтительный вид. В целевую функцию она войдет с коэффициентом 0.). Следовательно, вычтем из левой части неравенстваи добавим вторую переменную искусственного базиса. Соответственно, в целевую функцию добавятся две новые переменные с коэффициентами 0 и –М соответственно.
Таким образом, ЗЛП будет иметь следующий вид:
при
Базис системы составляют переменные: , , , (представлены в соответствии с уравнениями, предпочтительными переменными которых являются данные переменные). Следовательно, начальный опорный план ЗЛП имеет вид: (0, 23, 0, 0, 0, 34, 0, 17, 6).
Замечание: При составлении начального опорного плана для данной задачи учитывались все новые переменные в следующей последовательности: сначала переменные и , а затем и .