Оптимальное управление в экономике. Матвейкин В.Г - 11 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

где .1,0,1,
1
k=i=
i
k
=i
i
≥λλ
∑
1.4.4. Задача со многими переменными
Задачу со многими переменными можно решить графически, если в её канонической записи присутствуют
не более двух свободных переменных. Чтобы решить такую задачу, необходимо:
1) выделить некоторый базис переменных в системе ограничительных уравнений;
2) опустить базисные переменные и перейти к эквивалентной системе неравенств;
3) выразить целевую функцию через свободные переменные;
4) полученную двумерную задачу рушить обычным графическим способом;
5) найдя две координаты оптимального решения, подставить их в ограничительные уравнения и опреде-
лить остальные координаты оптимального плана.
2. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Одним из универсальных методов решения задач ЛП является симплекс-метод или метод последователь-
ного улучшения плана. Если задача разрешима, то ее оптимальный план совпадает, по крайней мере, с одним из
опорных решений системы ограничений. Именно этот опорный план и отыскивается симплекс-методом в ре-
зультате упорядоченного перебора опорных решений. Упорядоченность понимается в том смысле, что при пе-
реходе от одного опорного плана к другому соответствующие им значения целевой функции возрастают (или,
по крайней мере, не убывают). Так как общее число опорных решений конечно, то через определённое число
шагов будет либо найден оптимальный опорный план, либо установлена неразрешимость задачи. Чтобы полу-
чить новый опорный план, первоначальный базис преобразовывают в новый. Для этого из первоначального
базиса удаляют некоторую базисную переменную и вместо неё вводят другую из группы свободных.
С геометрической точки зрения перебор опорных планов можно толковать как переход по ребрам от одной
вершины многогранника решений к другой по направлению к вершине
opt
X , в которой целевая функция дос-
тигает оптимального значения.
2.1. ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ
Решение задачи ЛП складывается из нескольких этапов:
1. Задача должна быть приведена к каноническому виду, притом все элементы столбца свободных членов
должны быть неотрицательными.
2. Найден начальный опорный план задачи.
3. Целевая функция выражена через свободные переменные и максимизирована.
4. По симплексному методу находится оптимальный план задачи.
2.2. НАХОЖДЕНИЕ ОПТИМАЛЬНОГО ОПОРНОГО ПЛАНА
Пусть система ограничений имеет предпочтительный вид, т.е. найден начальный опорный план задачи. Не
ограничивая общности, предположим:
max...
2211
→
nn
xc++xc+xc=z ;
,...
..............................................
;...
;...
11
221112
111111
mnmn+m+mmm
nn+m+m
nn+m+m
b=xa++xa+x
b=xa++xa+x
b=xa++xa+x
(
)
(
)
.1,0,,1,0, m=ibn=jx
ij
≥≥
Исключим базисные переменные из целевой функции. Для этого выразим их через свободные переменные
из системы ограничительных уравнений:
(
)
,1,0,,)...(
1
n=jxxaxsbx
jninmimii
≥++−=
+
и подставим в выражение функции z. Получим приведенные коэффициенты целевой функции
.xcxcxcz=z
n+mnm+mm+mm
max...
22110
→
′
−
−
′
−
′
−
+++

Страницы