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

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


является    матрицей        обратной   к    оптимальной   базисной    матрице
                 � 1 −1     0�
                  �              �
B =[A3 A1 A5 ] =� 0 1       0� .
                    � 0 1   1 ��
                     �


                      Задачи для самостоятельного решения
1. Составить двойственные задачи к следующим исходным и проверить
свойство 1 двойственных задач:
1) x1 −2 x 2 +3 x 3 −x 4 → max
   2 x1 −x 2 +2 x3 −3x 4 ≤5
     x1 +2 x 2 −x 3 +x 4 ≤3                3) 2 x1 −x 2 +x 3 −3 x 4 +x 5 → min
     x1 ≥0, x 2 ≥0, x 3 ≥0, x 4 ≥0 ;           2 x1 −x 2 +x 3 −3x 4 −x 5 =10
2)              3x 3 −x 4 → max                   x1 +2 x 2 −x 3 +2 x 4 +x 5 ≥8
     x1 −2 x 2       +x 4 =8                   2 x1 −x 2 +3 x3 −x 4 +2 x 5 ≤4
           x 2 +x 3 −3 x 4 =6                      x1 ≥0, x 3 ≥0, x 4 ≥0 .
x1 ≥0, x 2 ≥0, x 3 ≥0, x 4 ≥0
2. На основании графического анализа двойственной задачи исследовать раз-
решимость следующих задач и в случае разрешимости найти оптимальное
значение целевой функции:
1) 2 x1 −x 2 +4 x 3 −2 x 4 → max                 x1 +3 x 2 +x 3 ≤−2
    2 x1 −x 2 +2 x 3 −x 4 ≤5                   x1 −4 x 2 +4 x3 ≥1
      x1 −2 x 2 +2 x 3 −x 4 ≥4                  x1 ≥0, x 2 ≥0 ;
                                           4) 2 x1 +x 2 +2 x3 → min
2) x1 −x 2 +2 x 3 −6 x 4 → min                −x1 +x 2 +x 3 =2
     x1     +2 x 3 −x 4 =4                     x1 −3x 2 −2 x 3 =1
     x1 −x 2 +x 3 −3x 4 ≥8                     x1 ≥0, x 2 ≥0, x 3 ≥0 .
     x1 ≥0, x 3 ≤0, x 4 ≥0 ;
3) 3 x1 −12 x 2 +4 x 3 → min
3. Для каждой из пары двойственных задач возможны три варианта ответа:
задача разрешима (Р), функция не ограничена (Н), область пустая (П). Это
позволяет, вообще говоря, рассмотреть 9 ситуаций : РР (обе задачи разреши-
мы), РН (первая разрешима, во второй целевая функция не ограничена) и т.д.
Указать все возможные ситуации.
4. Привести примеры двойственных пар, обладающих следующими свойст-
вами.
1) обе задачи имеют оптимальные решения;
2) одна задача имеет неограниченную допустимую область, вторая - пустую
   область;


                                       38