Файл: Говар В.М. Математическое программирование учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 29.06.2024
Просмотров: 140
Скачиваний: 0
|
|
|
*rt+I = |
* I |
- |
aT i X. |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
хЛ+2 = |
»2 |
- |
|
4 |
t |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
(4.8) |
|
x n+u |
= |
a i |
- |
|
4- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x n+t = |
bx. - |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
hm - a n r X : |
|
|
|
|
|
|
|
|
|
|
||||
|
Первой обратиться в нуль |
та из переменных |
x i l + |
I |
, x n |
+ 2 |
||||||||||||||
|
X + ( |
п |
, для которой |
отношение свободного |
члена к коэффициенту |
|||||||||||||||
при переменной, вводимой в базис, является наименьшим. Будем |
||||||||||||||||||||
обозначать |
эти отношения буквой 9 • |
|
|
|
|
|
|
|
|
|
||||||||||
|
Отыскиваем |
минимальное |
симплексное |
отношение, |
то есть пм.п Ѳ: |
|||||||||||||||
nu. Л3 |
m Lui |
f |
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
а- |
|
a-, |
|
|
|
а |
|
|
|
|
|
|
|
При этом отыскиваем отношения только к положительным коэффи |
|||||||||||||||||||
циентам, |
тан как, если |
какое-либо а £ ^ - ^ °> 1 0 |
увеличение |
х^ вы |
||||||||||||||||
зывает только |
лишь возрастание базисной |
переменной |
x n + |
t , |
а при |
|||||||||||||||
а ^ |
= 0, |
переменная .xn +t |
н |
е |
меняется. |
|
|
|
|
|
|
|
|
|||||||
|
Допустим, |
что наименьшее |
значение |
Q |
будет |
в і |
-том уравне- |
|||||||||||||
нии, то |
есть |
|
Піі-пѲ = |
^_ |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
а - |
|
|
|
|
|
|
|
|
|
|
|
|
Тогда |
коэффициент |
а-- |
будем называть |
генеральным |
элементом. |
||||||||||||||
|
Установив |
|
генеральный |
элеыент, |
нужно |
переходить |
ко второму |
|||||||||||||
базисному |
решению. Для этого Х' из свободных |
переменных |
нужно |
|||||||||||||||||
перевести |
в базисные, |
а х и + |
|
из базисных - в свободные. |
|
|
||||||||||||||
|
Для того,чтобы X |
из свободных |
переменных перевести в базис |
|||||||||||||||||
ные, нужно исключить его из остальных |
уравнений системы |
(4.5).При |
||||||||||||||||||
использовании метода Кордана-Гаусеа |
процесс исключения |
переменной |
||||||||||||||||||
х- |
из всех |
уравнений, |
кроме L - r o уравнения,системы |
(4.5) |
выпол- |
|||||||||||||||
няется без особых |
затруднений. |
|
|
|
|
|
|
|
|
|
||||||||||
Разделим все члены і-то |
уравнения |
системы |
(4,5) |
на генераль |
||||||||||
ный элемент: |
|
|
|
|
|
|
|
|
|
|
|
|
||
(4.9) |
Хт + |
X? + . . . .+ - - |
Х- т + |
I о х- + — а — х + т + . . . |
||||||||||
•*• + |
a |
|
n |
a-- п + "- |
|
а,- |
|
|
|
|
|
|||
Уравнение, |
полученное в результате деления обеих его частей « |
|||||||||||||
на генеральный |
элемент, |
будем называть |
направляющим. |
|
||||||||||
Например, |
для того,чтобы исключить х- |
из і |
-го уравнения, |
|||||||||||
нужно |
умножить |
направляющее |
уравнение |
(4.9) |
на |
(- a t . |
) : |
|||||||
|
|
а. |
а, . |
а 0 а т • |
|
а.- |
а>.; |
|
а^.і а*. |
|||||
(4.10) |
|
|
-Хт - |
« |
X? - |
••• |
1 |
— |
г |
- а г Х ; |
* |
|||
|
|
% |
|
1 |
a L > |
2 |
|
a . . |
|
|
t, k |
a |
||
|
a. |
a, |
|
|
а^і. |
|
в-. |
a t - |
|
|
|
|||
' X L+I |
a, , |
|
" |
|
a - |
V L |
" |
a ~ " |
" |
|
|
|
||
* |
|
LJ- |
|
|
|
Cj- |
|
|
|
|
|
|
|
|
Затем |
полученный |
результат |
(4.10) |
почленно складываем с соот |
||||||||||
ветствующими |
членами |
t, - го уравнения |
системы (4.5) и получаем: |
|||||||||||
Аналогично исключается х^ из остальных уравнений системы (4.5).
Далее, исключая х,- из функции цели (4.7), получим (4.12):
Г
! В результате вычислений получим второе базисное рѳшение(4.ІЗ).
- |
36 |
- |
_ |
*і а. |
|
|
а. |
|
- |
и ••J |
a.. |
a .
..-J.
- В;
(4.13) |
X- |
|
|
|
|
i |
4- |
|
|
|
V l + I |
= B. |
4 t Ii |
|
|
" |
LH |
|
|
|
|
B t |
- |
ft а ^ |
|
|
|
|
4 |
При этом функция цели принимает значение I ( X ) = с - с ' - Получив второе базисное решение, если оно не будет оптималь
ным,повторяем цикл вычислений аналогичным образом до тех пор,пока не получим оптимального (в рассматриваемом случае - максимального)
результата. |
|
|
|
|
|
|
При к пользовании метода последовательного улучшения плана |
|
|||||
для решения конкретных задач процесс решения проще выполнять а |
|
|||||
симплексных таблицах. |
|
|
|
|
|
|
Ознакомимся с- алгоритмом вычислений в симплексных |
таблицах. |
|
||||
I . |
Сосіавляѳм симплексную таблицу |
(таблица 4.1) , |
заполняя |
ее |
||
коэффициентами из системы ограничений |
(4.5) и функции цели (4.2). |
|||||
При этом |
коэффициенты функции цели |
(4.2) |
записываются в таблицу |
с |
||
противоположными знаками (кроме с 0 |
) , ю |
есть C j , с 2 , |
. . . , с ' |
|
||
• л - |
|
|
|
|
' |
|
Знаки коэффициентов системы ограничений (4.5) при заполнении |
||||||
таблицы |
не изменяются. |
|
|
|
|
|
'Базисные Свобод перемен ные
ные члены
Хп и |
e, |
|
. . . |
h |
... |
|
||
|
k-, |
|
|
h |
Ail |
Xil-L+I |
|
UL-w |
|
|
• • * |
|
êt |
|
" L ( x ) |
|
с, |
- 37 -
Таблица 4.1
|
... |
|
|
|
|
X - |
|
|
Ѳ |
й а |
|
|
1 |
0 ... |
0 |
|
0 |
0 |
|
Ö»a |
... |
a w |
0 |
I |
• -- |
0 ... |
0 ... |
0 |
|
ÖL2 |
... |
|
o" |
"Ô |
|
•1 |
- |
0 ... |
0 |
|
|
|
J . . ... ... ... ... ... ... |
|
|||||
... |
... |
|
0 |
0 .... |
0 ... |
0 |
0 |
||
|
... |
|
0 |
0 ... |
0 |
|
0 |
0 |
|
... |
|
|
.... ... ... |
|
... |
F |
... |
||
... |
... |
flmn 0 |
0 |
|
0 ... |
1 |
|||
г.. |
fltn |
0 |
0 |
• •• |
0 |
|
... |
0 |
|
с:. |
|
C'n |
0 |
|
|
o" r ; "b |
0 |
||
Строку сишілексной таблицы,содержащую коэффициенты функции
цели с 0 |
, |
с j |
, с'2 |
с^. |
c'a , будем называть индексной. |
2. |
h |
индексной строке анализируем коэффициенты C j , с£, . . . , |
|||
с': |
|
а'(\ . |
Если хотя |
бы один |
из этих коэффициентов отрицателен, |
я |
|
|
|
|
|
то полученное решение оптимальным не является (при решении на мак симум). Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине. Предположим, что этот коэффициент содержится в j_ -м столбце. Этот столбец таблицы будем называть клю чевым.
При решении задачи на минимум ключевой столбец содержит наиболь ший из положительных коэффициентов индексной строки.
3. Вычисляем симплексные отношение Q в последнем столбце таб лицы, при этом находим отношения свободных членов только к положи тельным коэффициентам -го столбца. Из всех значений 9 выбираем наименьшее. Строку, в которой находится минимальное значение Ѳ , будем называіь ключевой.
- 38 - 4. На пересечении ключевого столбца и ключевой строки нахо
дим генеральный элемент.
5. Определив гвнеральный элемент, переходим к составлению
второй симплексной таблицы, при этом выполняем следующие действия:
а) |
свободную |
переменную xj, |
переводим |
в базисные, а базисная |
||
переменная Х ц ^ |
перейдет |
в |
свободные; |
|
||
б) |
заполняем |
строку |
с |
вновь |
введенной |
базисной переменной Ху ; |
эту строку будем называть направляющей. Для этого все коэффициенты ключевой строки предыдущей симплексной таблицы делим на генераль ный элемент;
в) для перевода х- из свободных переменных в базисные нуяно исключить ее из всех строк, кроме I -той. Для этого накапливаем
нули во всех остальных клеткахJ.-го столбца таблицы ( 4 . 2 ) путем умножения всех коэффициентов направляющей строки на соответствую щие коэффициенты^ -го столбца, взятые с противоположным знаком,
предыдущей симплексной таблицы ( 4 . 1 ) и сложения полученных чисел
с соответствующими коэффициентами строк той же таблицы. Так,напри
мер, для получения нуля в |
строке t столбца j , умножаем направляю |
|||
щую строку на (- |
atу |
). |
|
|
В результате |
указанного выше алгоритма получим вторую симплек |
|||
сную таблицу (табл. 4 . 2 ) : |
(см.стр.37) |
|||
Процесс вычислений продолжаем в симплексных таблицах до по |
||||
лучения оптимального |
решения. |
|||
Прежде чем перейти к рассмотрению конкретного примера,рассмот |
||||
рим правила работы со |
столбцом контрольных сумм. Эти правила поз |
|||
воляют |
контролировать |
процесс вычислений на каждой итерации (одном |
||
цикле |
вычислений), то |
есть |
при переходе от одной симплексной таб |
|
лицы к другой.
Симплексные таблицы дополняются еще одним столбцом - столбцом контрольных сумм. В -том отолбцв я исходной симплексной таблице