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

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

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

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

Т.С. Образована пересечением прямых L2 и L3 2-е и 3-е ограничение модели выполняются как точные равенства, являются активными, это означает, что оптимальным планом ресурсы II и III типа исчерпываются полностью, т.е. имеют статус дефицита.

Т.С. лежит ниже прямой L1, т.е. первый ресурс является не дефицитным, т.е. имеется в избытке.

 

Можно написать пример

 

 

7. Формы записи задач линейного программирования: общая задача линейного программирования в развернутой, матричной и векторной форме. Правила преобразования общей задачи линейного программирования в каноническую.

Общей задачей линейного программирования называется задача следующего типа:

F(Х1, Х2,…Хn) = → max (min)

≤bi           i=…

= bi, i=

≥ bi,, i=

Xj ≥0, j=

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

F(Х1, Х2,…Хn) = → max

=bi,           i=

Xj≥0, j=

Особенности:

1. Целевая функция задается на мах

2. Все ограничения имеют форму точных равенств

3. Все переменные подчиненные требованиям не отрицательны

Каноническая задача может быть записана в векторной и матричной форме.

Векторная форма:

Введем  мерных вектора,

n – мерных

=  ,          =

Перемен.Хт             Сn коэф.

n - мерные

=     = = =

В веденных обозначениях каноническая задача записывается:

F() = * → max     

*  - скалярное произведение векторов

Х1* +Х2* +Хn*  =

≥0

А=

 

Х= В =       С=(С1 С2…Сn)

F(x) = * → max

A*x=B произведение матриц

X≥0

 

9 Основная теорема линейного программирования. Построение первого опорного плана, его содержательный смысл. Алгоритм симплекс метода.

Алгоритм симплекс метода базируется:

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

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

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

 

Алгоритм симплекс метода начинается с построения 1-го дополнительного плана, который соответствует одной из вершин, такой дополнительный план называется опорным. Эта задача решается наиболее просто, если среди векторов ограничений aj имеется m векторов образующих единый базис в пространстве ограничений.

Переменные дополненные базисным вектором называются базисными переменными, остальные объявлены свободными

Базисные переменные имеют положительные значения, совпадающие с правыми частями ограничений, значения свободных переменных = 0.

, ,  - базис

Х4, Х5, Х6 – базисные переменные

Х1,Х2,Х3 – свободные переменные

Х1=Х2=Х3=0

Первый опорный план соотв. Бездействию, ни какая п…. не производится, резервы ресурсов равны запасам.

В верхнюю строчку записываются коэффициенты целевой функции, в столбец Хбаз – значение базисных переменных, в столбец Сбаз – коэффициенты целевой функции при базисных переменных, записываются названия векторов и их координаты.

 нач. целевой функции на рассматриваемом опорном плане

Fj=

Проверка опорного плана на оптимальность:

Если все оценки Aj ≤0, то записаны в таблице опорный план является оптимальным, значения его базисных переменных беруться из столбца Хбаз, остальные являются свободными, их значения = 0.

Проверка целевой функции на неограниченность:

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

Построение нового базиса:

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

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