Дискретная оптимизация. Чернышова Г.Д - 5 стр.

UptoLike

Рубрика: 

                                          n
                                         � aij x j � 1 ,                                   (1.19)
                                         j �1
                                          n
                                         � x j � min .                                     (1.20)
                                         j �1
    ������� A, ��������� �� ����� � ������, ����� �������� �������
��������. ��������� ������ ������� � ������ ������������ ����������
��������, ����������� ������� ��������� ��� ������ ������� (� ������
������ ������� �� ������� ���� ���� �������).
    ����� ������ ���������, ��������, ��� ������������, �����������.

III. ������ � ��������� ������� �������� (������������ ������ � �����-
��������� ���������).
                              xij � 0 ,                          (1.21)
                                          n
                                         � xij � ai ,      i � 1,2,..., m ,                (1.22)
                                         j �1
                                         m
                                         � xij � b j ,       j � 1,2,..., n ,              (1.23)
                                         i �1
                                          m n
                                         �� cij �xij � � min ,                             (1.24)
                                         i �1 j �1

                                                      ��0, xij � 0,
                                         cij �xij � � �                                    (1.25)
                                                       ��cij xij � d ij , xij � 0.

    ������ ������ ���������� �� ����������� ������������ ����������-
���� � ���, ��� �������� �� ��������� ������� �� ������ � �����������
������������ ������, �� ����� � ��������������� ���������, ��������-
���� � ������, ���� ��������� ����� ����� �� �����.
    ���������� � ������ ����������� ������� ��������������� �������-
���. ������ ����� �������� ����� ���������� (�������) ��� ����� ����
���������� ��� ������ ����������� ����������������.
                 �� �c             xij � d ij yij � � min,
                 m�     n

                              ij                                                           (1.26)
                 i �1 j �1
                  n
                 � xij � ai ,           i � 1,2,..., m ,                                   (1.27)
                 j �1
                  m

                 �x
                 i �1
                        ij
                             � bj ,      j � 1,2,..., n,                                   (1.28)
                 xij � M ij yij ,                                                          (1.29)
                 ��� M ij � min�ai ,b j �,               xij � 0,    yij � �0,1� �i, j .   (1.30)


                                                     5