Постановка задачи линейного программирования и свойства ее решений

Общие методические указания

Основной формой обучения студента-заочника является самостоятельная работа над учебным материалом, которая состоит из следующих элементов: изучение теоритического материала по учебникам, решение задач выполнение контрольных работ. В помощь студентам университет организуется чтение лекций и проведение практических занятий. Заверщающим этапом изучения курса прикладной математики является сдача экзамена в соответсвии с учебным планом.

Вопросы для подготовки к экзамену по курсу прикладной математики, изучаемые по программе в третьем семестре.

1.  Постановка задачи линейного программирования (ЛП). Геометрическая интерпретация решения. Классическая форма записи задачи линейного программирования (ЛП). Базис опорного плана. Базисные переменные.

2. Симплекс-метод. Идея симплекс-метода. Формулы и условия перехода. Признаки прекращения счета. Табличный симплекс-метод. Формирование опорного базисного решения. Симплекс-таблица. Пересчет элементов таблицы. Отыскание решения.

3. Двойственная задача ЛП. Структура и свойства двойственной задачи. Транспортная задача ЛП.

4. Опорные планы транспортной задачи. Методы нахождения опорных планов. Решение транспортной задачи. Метод потенциалов.

5. Постановка задачинелинейного программирования. Оптимизация без ограничений (классические методы поиска экстремума функции одной и нескольких переменных; градиентные методы поиска экстремума).

6. Оптимизация при наличии ограничений (общая теория оптимизации при ограничениях типа равенств и типа неравенств).

7. Задача о кратчайшем пути.

8. Задача коммивояжера

9. Предмет и задачи теории игр. Стратегические конечные матричные игры двух лиц с нулевой суммой. Преобразование матричных игр. Игры с седловой точкой. Понятие чистых стратегий.

10. Игры без седловой точки. Понятие смешанных стратегий. Метод решения конечных матричных игр с помощью линейного программирования

11. Временные ряды. Стационарные ряды. Белый шум. Автокорреляции и автоковариация

12. Детерминированные временные ряды. Виды трендов.

13. Разделение трендов и шума методами регрессионного анализа

14. Качество регрессионной модели. Сопоставление моделей через остаточную дисперсию. Критерий Фишера

15. Однофакторный дисперсионный анализ

16. Принципы распознавания образа

17. Модель авторегрессии, Марковский процесс

18. Модель авторегрессии, процесс Юла

19. Критерии случайности. Метод поворотных точек

20. Критерии случайности. Критерий Кэндела

21. Прогнозирование с учетом тренда и авторегрессии

22. Эргодические временные ряды. Определение автокорреляции по одной реализации.

Методы линейного программирования.

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику? Такие методы объединяются под общим названием — математическое программирование.

Основные понятия

Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:
1) совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);
2) целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант - из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.;
Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, технологического и вообще научного потенциала. Нередко потребности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область экономических возможностей). План, удовлетворяющий системе ограничений задачи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным. Оптимальное решение, вообще говоря, не обязательно единственно, возможны случаи, когда оно не существует, имеется конечное или бесчисленное множество оптимальных решений.
Один из разделов математического программирования - линейным программированием. Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.
Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходить к нехудшему опорному плану.

Постановка задачи линейного программирования и свойства ее решений

Линейное программирование — раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.
Формы записи задачи линейного программирования:
Общей задачей линейного программирования называют задачу

(1.1)

при ограничениях

(1.2)

(1.3)

(1.4)

(1.5)

 (1.6)

где  - заданные действительные числа; (1.1) – целевая функция; (1.1) – (1.6) –ограничения; -  план задачи.
Пусть ЗЛП представлена в следующей записи:

(1.7)

(1.8)

(1.9)

Чтобы задача (1.7) – (1.8) имела решение, системе, её ограничений (1.8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай  вообще невозможен. При  система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть . В этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные  переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .
Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).
Теорема.Если система векторов содержит m линейно независимых векторов , то допустимый план

(1. 10)

является крайней точкой многогранника планов.
Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.