Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 40 стр.

Линейное программирование


                                 � 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. Полагаем a i′ =a i , b ′j =b j (i, j ) ∈Ω , где Ω = (i, j ) : i =1, m, j =1, n .
Шаг 1. Определяем пару индексов (i 0 , j 0 ) из условия min c ij =c i0 j0 .
                                                              ( i , j )∈Ω

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

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




                                          42