Курс лекций по линейному программированию

Курс лекций по линейному программированию. 

Лекция № 1: «Предмет курса. Оптимизационные задачи. Основы линейного программирования». 

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

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

Требуется определить максимум и минимум функции f(x₁, … , x_n) при условиях:

1. g(x₁, … , x_n) {≤, =, ≥} b_i i=
2. x_j≥0 j=

 

- показатель качества решения (целевая функция)

* - ограничения,  которые определяют множество  допустимых решений. 

Для того чтобы  решить задачу, достаточно найти её оптимальное значение (указать значение всех переменных, удовлетворяющих ограничениям задачи, которые доставляют функции f наибольшее или наименьшее значение среди всех значений функции на допустимых значениях переменных, или доказать что таких решений нет).

Процедура нахождения решений экстремальных задач  называется процедурой оптимизации.

Задача № 1 называется неразрешимой, если она не имеет решения. Это возможно в случае, когда целевая функция неограниченно на допустимом множестве решений.

Решить задачу – это найти её оптимальное  решение, либо установить её неразрешимость.

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

Методы решения  задач № 1 во многом зависят от вида и свойств множества допустимых значений переменных. Поэтому экстремальные задачи бывают линейные и нелинейные.

Для линейных задач  существует универсальный алгоритм решения, для нелинейных – алгоритма нет. 

Линейное  программирование 

Предметом изучения данного раздела является линейные экстремальные задачи, у которых целевую функция f и функция g_i – линейны.

Общей задачей  ЛП является задача нахождения max :

1. ∑a_ijx_j {<, =, >} b_i ;  i= j=
2. x_j≥0 j=

где a_ij, b_i, c_j – заданные постоянные, при этом целевая функция называется линейной формой.

Условие 1 – ограничение  задачи

Условие 2 – условие  неотрицательности переменных.

Стандартной (симметричной) задачей ЛП называется задача, в  которой опред. экстремум целевой функции при выполнении условия 1 только ву одну сторону  и условия 2 для всех переменных.

Каноническая  задача ЛП называется задача, в которой:

1. функция цели исследуется на максимум и минимум
2. ограничение задач только типа равенство
3. все переменные неотрицательны
4. все элементы правых частей положительны

 

Совокупность  чисел, удовлетворяющих допущения  задачи называется допущением решения  или планом задачи.

План х^* при котором целевая функция достигает максимума, называется оптимальным => решение состоит в нахождении хотя бы одного оптимального плана.

Различные формы  записи задачи ЛП:

1. векторная форма

=(x₁, … , x_n)

=(x₁, … , x_n)

Тогда векторная  запись будет состоять в следующем:

Z=Cx→max

A₁x₁+…+A_nx_n<b  x>0

2. матричная форма записи

Где А – матрица  условий; Сх – скалярное произведение векторов; Ах – умножение матрицы  на вектор. 

Элементы выпуклого  анализа.

Линейная комбинация векторов называется выпуклой, если выполняется условие

В двумерном  случае линейная комбинация векторов есть отрезок, соединяющий эти точки.

Множество называется выпуклым, если вместе с каждой парой  всех элементов оно содержит все  их выпуклые комбинации.

Сглаживание линейных неравенств, образующих ОДЗ линейной задачи, определ. некоторое выпуклое множество, которое называется выпуклым многогранником решений.

Угловая точка  многогранника решений – это  точка, которая не является выпуклой комбинацией никаких других точек данного многогранника.

Если система  ограничений содержи конечное число  неравенств и имеется хотя бы одно допустимое решение, то угловых точек всегда конечно и не более чем число сочетаний из n элементов по m.

Угловые точки  многогранника – вершины, а полуплоскости, проходящие хотя бы через 2 вершины называются гранями.

Вершины называются соседними, если существует грань их соединяющая.

Теорема № 1:

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

Любая точка  многогранника решений является линейной выпуклой комбинацией его  угловых точек. 

Опорное или  базисное решение. 

Если система  линейных уравнений имеет переменных больше, чем уравнений, то оно имеет  бесконечное число решений, в  каждом из которых некоторые переменные полагают как базисные (их столько, сколько уравнений) и остальные  свободные.

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

Алгебраическая  характеристика угловой точки. 

Рассмотрим канонический вид задачи ЛП в векторной форме. Т.к. размерность векторов А₁, … , А_k = m то в системе уравнений можно выбрать m базисных переменных, которые определяют некоторое решение данной системы.

Теорема № 2:

Если система  векторов А₁, … , А_k в каноническом разложении (*) линейно независима (k≤m) и такова, что А₁х₁, … , А_kх_k=b, где все х_j≥0 j= , то точка х=(b₁,b_k,0…0) является угловой точкой многогранника решений. Если точки х является угловой точкой многогранника решений, то система векторов  А₁, … , А_k в разложении (*) является линейно независимой, образующий базис.

Следствия:

1. т.к. вектора А₁, … , А_k имеют размерность m, то угловая точка многогранника решений имеет не более, чем m положительных координат, а в силу неотрицательности переменных остальные = 0.
2. Для любой угловой точки в разложении (*)  имеется не более чем m линейно независимых векторов.

 

Опорный  план называется невырожденным, если он содержит ровно m положительных компонентов и вырожденным, если число положительных компонентов < m.

Заключение:

1. опорный план соот. угловой точке и число опорных планов всегда конечно.
2. Оптимальный план всегда существует, если множество решений не пусто и ограниченно.

 

Оптимальный план находится среди опорных, следовательно, перебирая все опорные планы, количество которых конечно, всегда может быть найден оптимальный план. 

Лекция № 2: «  Симплексный метод». 

Теорема № 1. Критерий оптимальности плана.

План оптимальный в линейной задаче на максимум (минимум), если все оценки индексной строки неотрицательны (неположительные).

Критерий неразрешимости задачи на максимум:

Если в индексной  строке есть неотрицательные оценки, но среди компонент разложения по базису нет положительных (нельзя вычислить τ), то задача неразрешима.

Теорема о не единственности оптимального плана:

Пусть х^* - оптимальный план. Если среди оценок индексной строки для небазисных векторов существуют нулевые, а среди коэффициентов разложения по базису вектора соответствующие данной нулевой оценке есть хотя бы один положительный, то существует ещё один оптимальный план (отличный от данного). Назначение целевой функции на котором такое же как и на данном.

Содержательно: плоскость, соответствующая целевой функции параллельна одной из плоскостей многогранника решений.

 

Теория двойственности 

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

Формально