Линейное программирование. Азарнова Т.В - 39 стр.

UptoLike

Рубрика: 

Линейное программирование
41
=
500000
69000
01336210
0001530
X
с o значением целевой функции равным 804.
Метод "северо-западного угла " может оказаться очень "далеким " от
оптимального, так как при построении начальной базисной точки этим мето-
дом мы совсем не реагируем на коэффициенты целевой функции
c
ij
. Важно
иметь простой метод , позволяющий строить начальную базисную точку во
многих случаях близкую к оптимальной. Таким методом является некоторая
модификация метода "северо-западного угла " - метод минимального элемен -
та.
Алгоритм метода минимального элемента
Шаг 0. Полагаем ∈=
=
),(, jibbaa
jjii
, где
{
}
njmiji ,1,,1:),( === .
Шаг 1. Определяем пару индексов
(
)
00
, ji
из условия
00
min
),(
jiij
ji
cc
=
.
Шаг 2. Полагаем
(
)
00
00
,min
ji
ji
bax
′′
=
. Если
0
00
i
ji
ax
=
, то переходим к шагу
3, в противном случае - к шагу 6.
Шаг 3. Полагаем
00
00
ji
jj
xbb
=
.
Шаг 4.
(
)
{
}
njji ,1:,\
0
== ΩΩ .
Шаг 5. Если множество
состоит из элементов одной строки
k
i , то полага -
ем
jji
bx
k
= для всех
(
)
ji
k
, . Решение закончено. В противном случае
переходим к шагу 1.
Шаг 6. Полагаем
00
00
ji
ii
xaa
=
.
Шаг 7.
(
)
{
}
miji ,1:,\
0
== ΩΩ .
Шаг 8. Если множество
состоит из элементов одного столбца
k
j , то по-
лагаем
iij
ax
k
= для всех
(
)
k
ji , . Решение закончено. В противном слу-
чае переходим к шагу 1.
Данным методом найдем исходную базисную точку для примера 1.
                                                              Линейное программирование


                                 � 30 15 0 0 0 �
                                  �                    �
                                    � 0 21 36 13 0 �
                             X =�
                                          0 0 0 9 6�
                                     ��                  ��
                                        � 0 0 0 0 50 �

сo значением целевой функции равным 804.
      Метод "северо-западного угла" может оказаться очень "далеким" от
оптимального, так как при построении начальной базисной точки этим мето-
дом мы совсем не реагируем на коэффициенты целевой функции cij . Важно
иметь простой метод, позволяющий строить начальную базисную точку во
многих случаях близкую к оптимальной. Таким методом является некоторая
модификация метода "северо-западного угла" - метод минимального элемен-
та.

                  Алгоритм метода минимального элемента

                                                                  {                  }
Шаг 0. Полагаем ai′ =a i , b ′j =b j (i, j ) ∈Ω , где Ω = (i, j ) : i =1, m, j =1, n .
Шаг 1. Определяем пару индексов (i 0 , j 0 ) из условия min cij =ci0 j0 .
                                                               ( i , j )∈Ω

                                 (        )
Шаг 2. Полагаем xi0 j0 =min ai′0 , b ′j0 . Если xi0 j0 =ai′0 , то переходим к шагу
3, в противном случае - к шагу 6.
Шаг 3. Полагаем b ′j0 =b ′j0 −xi0 j0 .
                 {               }
Шаг 4. Ω =Ω \ (i 0 , j ): j =1, n .
Шаг 5. Если множество Ω состоит из элементов одной строки i k , то полага-
ем xik j =b ′j для всех (i k , j )∈Ω . Решение закончено. В противном случае
переходим к шагу 1.
Шаг 6. Полагаем a i′0 =ai′0 −xi0 j0 .
                 {               }
Шаг 7. Ω =Ω \ (i, j 0 ): i =1, m .
Шаг 8. Если множество Ω состоит из элементов одного столбца j k , то по-
лагаем xijk =a i′ для всех (i, j k )∈Ω . Решение закончено. В противном слу-
чае переходим к шагу 1.

Данным методом найдем исходную базисную точку для примера 1.




                                         41