Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
8.5.4. Симплекс-метод. Допустимым решением задачи (8.5.1) —
(8.5.3) назовем вектор х = (х1, ..., хп), удовлетворяющий ограничениям (8.5.2), (8.5.3). Допустимое решение, минимизирующее Ф(х), является оптимальным. Напомним, что ранг матрицы А равен т.
/
/
4)
*77774*. (С„С2) 1
340
Предположим, что решение задачи существует и единственно. Тогда оптимальное решение может быть получено из каких-то п^т уравнений (8.5.2) и каких-то п—т равенств
хк = 0, 1^к^п.
Но каких именно, неизвестно. Симплекс-метод представляет собой алгоритм решения этого вопроса.
1-й шаг: выбор базисного решения. Выберем п—т свободных неизвестных в (8.5.2), а остальные т переменных (базисные) выразим через них. Пусть отличный от нуля минор т-то порядка расположен в левом верхнем углу матрицы А. Тогда из (8.5.2) можно найти
Х1 +а1,т+1Хт+1+ ••• +а1,вХя = Р1>
х2 + а2,т+1хт+1 + — +а2,(Л = Р2>
(8.5.5)
1 ^m+ 1 “К"' ^m,n^n ?m*
Предположим, что
0, (8.5.6)
Подставляя (8.5.5) в (8.5.1), получим
Ф(^т + 1» •••» ^и) Ут + 1 хт+1 “Ь ... “Ь Упхп “Ь Ф() 5 (8.5.7)
где константы у*, Ф0 вычисляются по ch c/iij, ?*. Условие (8.5.6)
позволяет принять вектор х с компонентами
‘fi;"; (8.5.8)
(О, т+1 v 7
в качестве допустимого базисного решения.
Выбор таких базисных переменных, чтобы выполнялось условие
(8.5.6), нетривиален. Соответствующая процедура описана ниже. Если в (8.5.7) все yt>0, m+K/^л, то (8.5.8)—единственное оптимальное решение, оптимальное значение Ф = Ф0.
Пусть среди коэффициентов yt есть отрицательные числа, у3 минимальное из них. Тогда выполняется второй шаг.
2-й шаг: замена допустимого базисного решения (8.5.8) новым с уменьшением целевой функции.
Рассмотрим числа
—, 1 ^ ^ га, ra+l^/^w.
a;,j
Выберем из них положительные, а среди положительных—наибольшее. Пусть это число
(8.5.9)
a/,J
Новое базисное решение определяется формулой (8.5.9) (xj вводится в базисные переменные) следующими соотношениями:
$?i-u>i,jXj> 0, 1 </<га,
Заметим, что ^ = 0 (х1 выводится из базисных переменных). Целевая функция на этом решении равна
Ф = Ф0+Уу— <Ф0
и в силу выбора /, / ее значение на новом базисном решении меньше, чем на старом.
Вводя в (8.5.5) строку
х -i1
xJ—~
получаем каноническую форму задач^ “относительно новых базисных переменных.
Повторяем второй шаг до тех пор, пока все коэффициенты при свободны^ неизвестных в целевой функции не примут положительные значения.
8.5.5. Первый шаг симплекс-метода. Симплекс-метод, как указывалось выше, предполагает на первом шаге выбор базисных переменных jcjl , ..., хт таким образом, чтобы выполнялись условия
(8.5.6). Для такого выбора можно вводить дополнительные переменные. Этот подход позволяет установить существование допустимых решений. Однако для его реализации требуется решать еще одну задачу линейной оптимизации тем же симплекс-методом.
Рассмотрим исходную задачу (8.5.1)—(8.5.3). Для нее построим вспомогательную задачу: найти
mini|/fo+i, хп+т)=хп+1+хп+2 + ...+хп+т для неизвестного вектора хеш дополнительными переменными x = (xi, ..., Хп, Хп+1, ..., хп + т)
и условиями
а1ЛХ1+а1.2Х2+-+а1,пХп + Хп+1=Ь19
а2,1Х1+а2,2Х2+ ••• +a2,nXn + Xn + 2:=b2,
ат,1Х1+ат,2Х2+ — + ат,пХп +Хп + т =
х^О, 1^/^л + го.
Принимая jcjl, х2, хп за свободные переменные, а хп+1, хп+2, •••> хп+т—за базисные, получаем базисное допустимое решение вспомогательной задачи:
xn+s = bs> 0, 1
xf = 0,
Затем, применяя последовательно второй шаг симплекс-метода, находим оптимальное решение вспомогательной задачи. Если это решение таково, что оптимальное значение \|/ = 0, то оно определяет
\
допустимое решение исходной задачи; если v|/>0, то исходная задача не имеет допустимых решений.
8.5.6. Применение программы В1А0. Решим задачу линейной оптимизации
тахФ(х) = 10*! — х2 —9х3 — 8х4
при ограничениях
—2ху + х2 + Зх3+х4=2,
— 5xj+2х2+Зх4 = 5,
7xj— 4х2+х3+4х4 <1,
Зх2 + 2х2 + 5х3 + 6х4 <10, х;^0, 1<г<4.
Предварительно приведем задачу к каноническому виду, дополнив вспомогательными переменными х5, х6. Получим
min®!(x)= — 10хх +х2+9х3 + 8х4+0 -х5+0-х6
при ограничениях
—2ху +х2 + Зх3+х4+0х5+0хб = 2,
— 5xt+2х2+0х3+Зх4+0х5+0хб = 5, 7х1-4х2+х3+4х4+х5+0х6= + 1,
Зх1+2х2 + 5х3+6х4+0х5+х6 = 10,
Х;^0, l<i'<6.
Зададим абсолютную точность выполнения неравенств х; ^ 0, равную 10~5. Программа может иметь следующий вид:
REAL W(24), U(36),Х(6), Е, V(6), А(4,6)
REAL В(4),С(6)
INTEGER M,N,K(4),I
DATA A/—2., — 5.,7.,3.,1.,2., —4.,2.,3.,0.,1.,5., *1.,3.,4.,6.,0.,0.,1.,0.,0.,0.,0.,1./
DATA B/2.,5.,1.,10./,E/1.E—5/
DATA C/-10.,l.,9.,8.,0.,0./
DATA M,N,I/6,6,0/
С ОБРАЩЕНИЕ К ПРОГРАММЕ В1А0
CALL В1 A0(W, M, U, N,X, К, I, E, V, А, В, С)
С ВЫВОД НА ТЕРМИНАЛ ЗНАЧЕНИЙ ОПТИМАЛЬНЫХ
С КООРДИНАТ,
С НОМЕРОВ КООРДИНАТ, ОПТИМАЛЬНОГО ЗНАЧЕ-
С НИЯ ЦЕЛЕВОЙ ФУНКЦИИ
WRITE (5,1) (X(L),L= 1,4)
1 FORMAT (2Х,6Е12.5)
WRITE (5,2) К
2 FORMAT (2X,4(I2,2X))
WRITE (5,3) X(5)
3 FORMAT (2X,'FI1=',E12.5)
END
Глава 9
НЕЛИНЕЙНЫЕ УРАВНЕНИЯ. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ
#9.1. Введение
9.1.1. Сравнение линейных и нелинейных уравнений. Важнейшим свойством линейных функций у=/(х) является следующее: /(х) удовлетворяют принципу суперпозиции. Принцип суперпозиции заключается вктом, что если аргумент х есть линейная суперпозиция (комбинация) двух точек
