- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 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. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
1.9. Основные виды записи задач линейного программирования
Определение: Общей задачей линейного программирования называют задачу:
при ограничениях
();
();
();
();
- произвольные (),
где , , - заданные действительные числа.
Определение: Симметричной формой записи задачи линейного программирования называют задачу:
при ограничениях
();
();
или задачу
при ограничениях
();
().
Определение: Канонической формой записи задачи линейного программирования называют задачу:
при ограничениях
();
().
Рассмотрим еще два вида записи- матричную и векторную.
Введем обозначения: ,
, ,,
где С – матрица-строка; А – матрица системы уравнений, Х – матрица-столбец переменных, - матрица-столбец свободных членов.
Каноническая форма записи примет вид:
или
max Z=CX
при ограничениях
,
или
, .
Запишем задачу линейного программирования в векторной форме:
, , ...,, ...,.
Тогда задача линейного программирования в канонической форме записи имеет вид:
при ограничениях
, ,
где - скалярное произведение векторови.
1.10. Способы преобразования
При необходимости задачу минимизации можно заменить задачей максимизации и наоборот. Для функции одной переменной это утверждение очевидно. В самом деле, если - точка максимума функцииy=f(x), то для функции y=-f(x) она является точкой максимума, так как графики функций f(x) и –f(x) симметричны относительно оси абсцисс (рис. 1).
Итак, min f() = max (-f()).
Рис. 1. Графики функций y=f(x) и y=-f(x).
То же самое имеет место в случае функции n переменных:
.
1.11. Переход к канонической форме
Из примеров задач линейного программирования следует, что большинство ограничений задается неравенствами. Основные же методы решения задач линейного программирования применяются лишь к задачам, записанным в канонической форме. Поэтому приходится переходить от любой формы записи задач линейного программирования к ее каноническому виду, причем, нужно быть уверенным, что эти формы эквивалентны.
Пусть исходная задача линейного программирования имеет вид:
при ограничениях:
(); (1)
(); (2)
().
Преобразуем ее к каноническому виду. Введем m дополнительных неотрицательных переменных (). Для того чтобы неравенства типа преобразовать в равенства, к их левым частям прибавим дополнительные переменные () после чего система неравенств (1) примет вид:
() (3).
Для того чтобы неравенства типа (2) преобразовать в равенства, из их левых частей вычтем дополнительные переменные (). Получим:
() (4).
Систему уравнений (3) и (4) с условием неотрицательности дополнительных переменных называют эквивалентной системе неравенств (1) и (2) соответственно.
Дополнительные переменные () в целевую функцию вводятся с коэффициентами, равными 0.
Получим задачу:
,
при ограничениях:
();
();
();().
Теорема 11.1 (о переходе к канонической форме записи) Каждому допустимому решению задачи
Соответствует вполне определенное допустимое решение задачи
И наоборот, каждому решению задачи (6) соответствует допустимое решениезадачи (5).
Пример 1. Привести к канонической форме записи задачу:
Найти:
при ограничениях:
, ,.
Решение.
при ограничениях
, , , , , .
Пример 2. Привести к канонической форме записи задачу:
Найти:
при ограничениях:
, ,.
Решение.
при ограничениях
, , , , , .
Отметим экономический смысл дополнительных переменных. Они в каждой задаче прямо связаны с ее экономическим содержанием. Например, для задачи о наилучшем использовании ресурсов:
(),
т.е. дополнительная переменная указывает величину неиспользованного ресурса. Для задачи о смесях:
(),
т.е. дополнительная переменная показывает потребление соответственного питательного вещества в оптимальном плане сверх нормы.
В ряде производственно-экономических ситуаций не на все переменные налагаются условия неотрицательности. В подобных ситуациях, даже если ограничения представлены в виде равенств, задача не будет канонической. Для представления такой задачи в каноническом виде каждую из переменных , на которые не наложено условие неотрицательности, заменим разностью двух неотрицательных переменныхи, т.е.
,
где 0 и 0 (этим приемом мы воспользуемся при изучении двойственных задач).