Транспортная задача линейного программирования. Бартеньев А.П - 6 стр.

UptoLike

ВУЗ: 

МичГАУ | Мичуринск

Составители: 

Рубрика: 

6
Таблица 2 – Первый вариант плана
Поля
Навозохранилище
В
1
β
1
=7
В
2
β
2
=6
В
3
β
3
=2
В
4
β
4
=2
В
5
β
5
=4
Наличие
навоза
А
1
α
1
= -4
3
450
2
550
5 3 1
1000
А
2
α
2
= 0
4
- 6
90
2
680
2
450
+ 4
280
1500
А
3
α
3
= -1
5
1
+
1
6
3
920
-
920
Потребность полей в
навозе
450
640
680
450
1200
3420
Определим объем перевозок навоза в тонно-километрах:
Z=450*3+550*2+90*6+680*2+450*2+280*4+920*3=9130.
Метод потенциалов
Алгоритм метода потенциалов заключается в следующем.
1. Строим первоначальный опорный план, содержащий (m+n-
1) занятых клеток.
2. Для полученого плана определяем систему потенциалов
α
i
(i= 1,2,…m) и β
j
(j= 1,2,…n), исходя из условия с
ij
= α
i
+β
j
(это
условие действительно для всех занятых клеток). Поскольку для
построения системы потенциалов используем только занятые
клетки, то число неизвестных (α
i
и β
j
), равное (m+n), на единицу
превышает число уравнений, равное (m+n-1). Поэтому для одно-
значного определения всех потенциалов одному из них придают
произвольное значение (как правило, тому, для которого в соот-
ветствующей ему строке или столбце находится наибольшее ко-
личество занятых клеток). Обычно в качестве такого произволь-
ного значения выбирается нуль. Затем из условия с
ij
= α
i
+β
j
по-
следовательно находят значения остальных потенциалов.
3. Исследуем систему потенциалов на оптимальность. План
оптимален, если для всех незанятых клеток выполняется условие
с
ij
≥ α
I
+β
j
, или с
ij
-(α
i
+β
j
) ≥ 0. То есть, разность между оценкой
незанятой клетки и суммой потенциалов строки и столбца, на пе-
ресечении которых находится эта клетка, является неотрицатель-
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
         Таблица 2 – Первый вариант плана

                                                      Поля
              Навозохранилище
                                      В1      В2      В3   В4          В5     Наличие
                                      β1=7    β2=6    β3=2 β4=2        β5=4    навоза
                                        3       2
                                                         5       3       1
              А1          α1= -4       450     550                             1000
                                                -6      2        2     + 4
                                        4
               А2          α2= 0                90     680      450    280     1500
                                                                        3
                                                1        1       6
                                        5                              920
              А3          α3= -1                +                               920
                                                                         -
             Потребность полей в
                   навозе              450     640     680      450    1200    3420

            Определим объем перевозок навоза в тонно-километрах:
         Z=450*3+550*2+90*6+680*2+450*2+280*4+920*3=9130.

                                 Метод потенциалов
              Алгоритм метода потенциалов заключается в следующем.
              1. Строим первоначальный опорный план, содержащий (m+n-
         1) занятых клеток.
              2. Для полученого плана определяем систему потенциалов
         αi (i= 1,2,…m) и βj (j= 1,2,…n), исходя из условия сij= αi+β j (это
         условие действительно для всех занятых клеток). Поскольку для
         построения системы потенциалов используем только занятые
         клетки, то число неизвестных (αi и β j), равное (m+n), на единицу
         превышает число уравнений, равное (m+n-1). Поэтому для одно-
         значного определения всех потенциалов одному из них придают
         произвольное значение (как правило, тому, для которого в соот-
         ветствующей ему строке или столбце находится наибольшее ко-
         личество занятых клеток). Обычно в качестве такого произволь-
         ного значения выбирается нуль. Затем из условия сij= αi+β j по-
         следовательно находят значения остальных потенциалов.
              3. Исследуем систему потенциалов на оптимальность. План
         оптимален, если для всех незанятых клеток выполняется условие
         сij ≥ αI+βj, или сij-(αi+βj) ≥ 0. То есть, разность между оценкой
         незанятой клетки и суммой потенциалов строки и столбца, на пе-
         ресечении которых находится эта клетка, является неотрицатель-


         6

PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com

Страницы