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

В связи с расширение приложения математики в решении экономических задач основное внимание уделяется решению задач, которые в рамках классической математики оказалось затруднительным и в первую очередь это касается экстремальных задач в экономических моделях в такого рода задачах экстремум достигается, как правило, в граничных тачках изменения параметра.
В экономических задачах оптимального управления и планирования процесс решения сводится к выбору системы функций и параметров, которые называются характеристиками экономической системы. В настоящее время под характеристиками управления понимаются только системы параметров, т.о. проблемы управления и планирования сводятся к экстремальной задаче первого вида:
Требуется определить максимум и минимум функции f(x1 , … , xn ) при условиях:
1.) g(x1 , … , xn ) {≤, =, ≥} bi i=
2.) xj ≥0 j=
- показатель качества решения (целевая функция)
* - ограничения, которые определяют множество допустимых решений.
Для того чтобы решить задачу, достаточно найти её оптимальное значение (указать значение всех переменных, удовлетворяющих ограничениям задачи, которые доставляют функции f наибольшее или наименьшее значение среди всех значений функции на допустимых значениях переменных, или доказать что таких решений нет).
Процедура нахождения решений экстремальных задач называется процедурой оптимизации.
Задача № 1 называется неразрешимой, если она не имеет решения. Это возможно в случае, когда целевая функция неограниченно на допустимом множестве решений.
Решить задачу – это найти её оптимальное решение, либо установить её неразрешимость.
Математическая дисциплина, изучающая экстремальные задачи и разрабатывающая методы их решения при различных допущениях относительной функции f и gi называется математическим программированием или методом оптимизации..
Методы решения задач № 1 во многом зависят от вида и свойств множества допустимых значений переменных. Поэтому экстремальные задачи бывают линейные и нелинейные.
Для линейных задач существует универсальный алгоритм решения, для нелинейных – алгоритма нет.
Линейное программирование
Предметом изучения данного раздела является линейные экстремальные задачи, у которых целевую функция f и функция gi – линейны.
Общей задачей ЛП является задача нахождения max :
1.) ∑aij xj {} bi ; i= j=
2.) xj ≥0 j=
где aij , bi , cj – заданные постоянные, при этом целевая функция называется линейной формой.
Условие 1 – ограничение задачи
Условие 2 – условие неотрицательности переменных.
Стандартной (симметричной) задачей ЛП называется задача, в которой опред. экстремум целевой функции при выполнении условия 1 только ву одну сторону и условия 2 для всех переменных.
Каноническая задача ЛП называется задача, в которой:
1. функция цели исследуется на максимум и минимум
2. ограничение задач только типа равенство
3. все переменные неотрицательны
4. все элементы правых частей положительны
Совокупность чисел, удовлетворяющих допущения задачи называется допущением решения или планом задачи.
План х* при котором целевая функция достигает максимума, называется оптимальным => решение состоит в нахождении хотя бы одного оптимального плана.
Различные формы записи задачи ЛП:
1. векторная форма
=(x1 , … , xn )
=(x1 , … , xn )
Тогда векторная запись будет состоять в следующем:
Z=Cx→max
A1 x1 +…+An xn 0
2. матричная форма записи
Где А – матрица условий; Сх – скалярное произведение векторов; Ах – умножение матрицы на вектор.
Элементы выпуклого анализа.
Линейная комбинация векторов называется выпуклой, если выполняется условие
В двумерном случае линейная комбинация векторов есть отрезок, соединяющий эти точки.
Множество называется выпуклым, если вместе с каждой парой всех элементов оно содержит все их выпуклые комбинации.
Сглаживание линейных неравенств, образующих ОДЗ линейной задачи, определ. некоторое выпуклое множество, которое называется выпуклым многогранником решений.
Угловая точка многогранника решений – это точка, которая не является выпуклой комбинацией никаких других точек данного многогранника.
Если система ограничений содержи конечное число неравенств и имеется хотя бы одно допустимое решение, то угловых точек всегда конечно и не более чем число сочетаний из n элементов по m.
Угловые точки многогранника – вершины, а полуплоскости, проходящие хотя бы через 2 вершины называются гранями.
Вершины называются соседними, если существует грань их соединяющая.
Теорема № 1:
1. множество решений задач ЛП, если оно не пусто, - есть выпуклый многогранник.
2. целевая функция задач ЛП достигает своего максимума значение в одной или нескольких угловых точках многогранника. Если она принимает максимальное значение больше чем в одной из угловых точек, то она достигает такого же значения и в любой точке, являющейся выпуклой линейной комбинацией этих угловых точек (содержательно, это значит, что прямая соответствующая целевой функции параллельна одной из граней многогранника).
Любая точка многогранника решений является линейной выпуклой комбинацией его угловых точек.
Опорное или базисное решение.
Если система линейных уравнений имеет переменных больше, чем уравнений, то оно имеет бесконечное число решений, в каждом из которых некоторые переменные полагают как базисные (их столько, сколько уравнений) и остальные свободные.
Применительно к ЛП при переходе к канонической форме получается система уравнений, в которой переменных больше чем уравнений, при этом элемент столбца правых частей b, является линейными комбинациями векторов ???? и дополнительных векторов, которые получаются в результате данного преобразования, следовательно, в качестве базисных векторов выбирают только т. векторов (соответствующие им переменные называются базисными, а остальные переменные в силу условий неотрицательности полагаются равными 0, т.о. получаем опорное решение или опорный план.
Алгебраическая характеристика угловой точки.
Рассмотрим канонический вид задачи ЛП в векторной форме. Т.к. размерность векторов А1 , … , Аk = m то в системе уравнений можно выбрать m базисных переменных, которые определяют некоторое решение данной системы.
Теорема № 2:
Если система векторов А1 , … , Аk в каноническом разложении (*) линейно независима (k≤m) и такова, что А1 х1 , … , Аk хk =b, где все хj ≥0 j=, то точка х=(b1 ,bk ,0…0) является угловой точкой многогранника решений. Если точки х является угловой точкой многогранника решений, то система векторов А1 , … , Аk в разложении (*) является линейно независимой, образующий базис.
Следствия:
1.) т.к. вектора А1 , … , Аk имеют размерность m, то угловая точка многогранника решений имеет не более, чем m положительных координат, а в силу неотрицательности переменных остальные = 0.
2.) Для любой угловой точки в разложении (*) имеется не более чем m линейно независимых векторов.
Опорный план называется невырожденным, если он содержит ровно m положительных компонентов и вырожденным, если число положительных компонентов х и у надо выбирать так, чтобы величина потерь была наименьшей, а для этого достаточно план подобрать так, чтобы z(x) было как можно больше, а F(y) – как можно меньше. Отсюда возникает пара симметричных двойственных задач.
Из теоремы 1 двойственности следует, что оптимальному вектору оценок и оптимальному плану производства соответствуют нулевые производственные потери.
Из теоремы 2 двойственности следует, что если х*, у* - оптимальные решения прямой и двойственной задач соответственно, то справедливо соотношение:
Условие (*) интерпретируется: если оценка i-ого вида ресурса положительна в оптимальном плане, то ресурс используется полностью, если ресурс используется не полностью, то его оценка = 0.
Условие (**): если производство j-ого вида продукции включено в оптимальный план, то он в оптимальной оценке неубыточен. Если он убыточен (затратная оценка превосходит цену реализации) то этот продукт не производится в оптимальном плане.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию