Получение оптимальных проектных решений и их анализ с использованием математических моделей. Литовка Ю.В. - 58 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

х
1
–х
3
= 10;
х
2
–х
4
= 5;
х
1
+х
2
+х
5
= 20;
–х
1
+4х
2
+х
6
= 20;
x
1
, x
2
, ..., x
6
≥ 0.
В этом примере две небазисные переменные (или четыре базисные) можно выбрать 15
2
6
==
−
CС
mn
n
спо-
собами. Из 15 базисных решений только четыре допустимы и соответствуют вершинам допустимой области.
Основная идея симплекс-метода состоит в направленном переборе вершин допустимой области (направ-
ленном переходе от одного допустимого базисного решения к другому). Особая проблема возникает при поиске
координат первой анализируемой вершины (поиске начального базисного решения).
Начальное допустимое базисное решение, с которого начинается применение симплекс-метода, легко най-
ти, если матрица коэффициентов системы ограничений с учетом дополнительных переменных содержит еди-
ничную подматрицу m × m. Рассмотрим процедуру построения начального допустимого базисного решения для
различных типов ограничений в постановке задачи ЛП.
Тип 1. Ограничения заданы в виде
iij
n
j
ij
bbxa ;
1
≤
∑
=
> 0; i = 1, ..., m.
Введением дополнительных неотрицательных переменных x
n+1
, x
n+2
, ..., x
n+m
система неравенств приводит-
ся к системе равенств вида
....,,1;
1
mibxxa
iin
n
j
jij
==+
+
=
∑
Матрица коэффициентов при дополнительных переменных образует единичную подматрицу требуемого
вида, и эти переменные используются для определения начального базисного решения. В этом случае началь-
ное допустимое базисное решение записывается в виде
x
j
= 0; j = 1, ..., n, x
n+i
= b
i
; i = 1, ..., m.
Тип 2. Ограничение заданы в виде ....,,1;0;
1
mibbxa
iij
n
j
ij
=>≥
∑
=
Введением дополнительных неотрицательных переменных x
n+1
, x
n+2
, ..., x
n+m
с коэффициентами –1 система
неравенств приводится к системе равенств вида
....,,1;
1
mibxxa
iinj
n
j
ij
==−
+
=
∑
Однако такое преобразование не позволяет получить единичной матрицы требуемого вида, и дополни-
тельные переменные не могут быть использованы для получения начального допустимого базисного решения.
Тогда поступают следующим образом. Вводятся вспомогательные неотрицательные переменные x
n+m+1
, x
n+m+2
,
..., x
n+m+m
с коэффициентами 1 и строится искусственная целевая функция
∑
=
++
=
m
i
imn
xW
1
.
Рассматривается вспомогательная задача ЛП вида
min
1
→=
∑
=
++
m
i
imn
xW
при условиях ,...,,1;
1
mibxxxa
iimninj
n
j
ij
==+−
+++
=
∑
для которой начальное базисное решение очевидно. Это x
j
= 0; j = 1, ..., n + m; x
n+m+i
= b
i
; i = 1, ..., m.
Вспомогательная задача решается тем же симплекс-методом. Решением задачи являются значения x
n+m+i
=
0, i = 1, ..., m (вспомогательные переменные), а среди остальных n + m переменных будут n нулевых и m нену-
левых. Ненулевые переменные, являющиеся базисными для последней итерации решения вспомогательной
задачи, и образуют начальное допустимое базисное решение для исходной задачи ЛП.
Тип 3. В ограничениях присутствуют равенства. В этом случае в каждое ограничение-равенство вводится
вспомогательная переменная, и дальнейшие действия аналогичны рассмотренным выше для ограничений типа
2.
Таким образом, алгоритм решения задачи ЛП симплекс-методом при задании ограничений в произвольной
форме должен предусматривать автоматический ввод дополнительных и вспомогательных неотрицательных
переменных и порождать начальное допустимое базисное решение.
Пусть в задачу входят n переменных и m ограничений, среди которых n
1
в виде неравенств со знаком ≤, n
e
– в виде равенств и n
g
– в виде неравенств со знаком ≥. Пусть ограничения расположены именно в таком поряд-
ке. Правые части при этом у всех ограничений положительны. Тогда исходная задача имеет следующий вид:

Страницы