- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 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.4. Понятие линейного программирования
Определение: Линейное программирование – это раздел математического, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные.
По типу решаемых задач его методы делятся на универсальные и специальные. С помощью универсальных методов могут быть решены любые задачи линейного программирования. Специальные же методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функций во внутренней точке области допустимых значений. Отсюда – необходимость разработки новых методов.
Математическая модель ЗЛП:
при
1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
Пусть некоторая производственная единица (цех, завод, объединение и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексами j . Предприятие при производстве этих видов продукции должно ограничиваться имеющими видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Пусть их число равно m, припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким образом,- вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчислимая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.д.
Примем в качестве такой меры, например, цену реализации (), т.е.- вектор цен. Известны также технологические коэффициенты, которые указывают, сколько единицi-го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов |||| называют технологической матрицей и обозначают А:
.
Обозначим через Х=- план производства, показывающий какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.
Так как - цена реализации единицыj-той продукции, цена реализации единиц будет равна, а общий объем реализации:
.
Это выражение – целевая функция, которую нужно максимизировать.
Так как - расходi-го ресурса на производство единицj-той продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить () единиц:
Чтобы искомый план Х=был реален, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемывыпуска продукции:
, ().
Таким образом, модель задачи о наилучшем использовании ресурсов имеет вид:
Найти:
,
при ограничениях
(),
, ().
Т.к. переменные входят в функциюZ(X) и систему ограничений только в первой степени, а показатели ,,являются постоянными в планируемый период, то задача является задачей линейного программирования.