Задачи линейного программирования транспортного типа. Горячев Л.В. - 12 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

12
ская модель задачи:
m
i=1
n
j=1
c
ij
x
ij
− min
n
j=1
x
ij
≤ a
i
,i=1, 2,...,m
m
i=1
x
ij
= b
j
,j=1, 2,...,n
x
ij
≥ 0
Сформулированная Т.З., отличающаяся от классической постановки (6)–(9) наличием условий-
неравенств, легко сводится к предыдущей введением фиктивного пункта потребления (n +1)–
го с объемом потребления b
n+1
=
m
i=1
a
i
−
n
j=1
b
j
. Полагая, что стоимость перевозок c
i, n+1
,
(i =1, 2,...,m) между i – ым пунктом производства и фиктивным пунктом потребления равна
нулю, открытую Т.З. сводим к классической постановке
m
i=1
n
j=1
c
ij
x
ij
− min
при условиях
n+1
j=1
x
ij
= a
i
,i=1, 2,...,m
m
i=1
x
ij
= b
j
,j=1, 2,...,n+1
x
ij
=0,i=1, 2,...,m, j =1, 2,...,n+1
Если условие баланса нарушено в другую сторону, то полное удовлетворения всех потребителей
невозможно. В этом случае поступают следующим образом: вводится фиктивный производитель
A
m+1
с объемом производства a
m+1
=
n
j=1
b
j
−
m
i=1
a
i
. Стоимости перевозок от пункта a
m+1
к
потребителям b
j
,j=(1,n) полагаются достаточно большими числами.
К Т.З. приводятся задачи, математическая модель которых имеет вид
m
i=1
n
j=1
c
ij
x
ij
− min
n
j=1
x
ij
= a
i
,i=1, 2,...,m
m
i=1
α
i
x
ij
= b
j
,j=1, 2,...,n
x
ij
≥ 0,i=1, 2,...,m, j =1, 2,...,n
Замена переменной y
ij
= α
i
x
ij
приводит задачу к стандартному типу.
Дальнейшее обобщение Т.З. связано с рассмотрением многоиндексных задач. Например, требу-
ется составить план транспортировки некоторого однородного продукта от центра производства к
центрам потребления с использованием транспортных средств различных типов, реализация ко-
торого обеспечивала бы минимальные транспортные затраты. Формальная запись условий задачи
12

ская модель задачи:
                                        m 
                                         n
                                                    cij xij − min
                                        i=1 j=1
                                        n
                                              xij ≤ ai ,      i = 1, 2, . . . , m
                                        j=1
                                        m
                                              xij = bj ,      j = 1, 2, . . . , n
                                        i=1
                                        xij ≥ 0


Сформулированная Т.З., отличающаяся от классической постановки (6)–(9) наличием условий-
неравенств, легко сводится к предыдущейm       введением
                                                  n          фиктивного пункта потребления (n + 1) –
го с объемом потребления bn+1 =          i=1 ai −   j=1 b j . Полагая, что стоимость перевозок ci, n+1 ,
(i = 1, 2, . . . , m) между i – ым пунктом производства и фиктивным пунктом потребления равна
нулю, открытую Т.З. сводим к классической постановке

                                               m 
                                                n
                                                           cij xij − min
                                                 i=1 j=1


при условиях

                             n+1
                             
                                    xij = ai ,      i = 1, 2, . . . , m
                             j=1
                             m
                                    xij = bj ,      j = 1, 2, . . . , n + 1
                              i=1
                             xij = 0,      i = 1, 2, . . . , m, j = 1, 2, . . . , n + 1


Если условие баланса нарушено в другую сторону, то полное удовлетворения всех потребителей
невозможно. В этом случае поступают    следующимm образом: вводится фиктивный производитель
                                          n
Am+1 с объемом производства am+1 = j=1 bj − i=1 ai . Стоимости перевозок от пункта am+1 к
потребителям bj , j = (1, n) полагаются достаточно большими числами.
     К Т.З. приводятся задачи, математическая модель которых имеет вид

                               m 
                                n
                                          cij xij − min
                               i=1 j=1
                               n
                                      xij = ai ,       i = 1, 2, . . . , m
                               j=1
                               m
                                      αi xij = bj ,      j = 1, 2, . . . , n
                                i=1
                               xij ≥ 0,          i = 1, 2, . . . , m, j = 1, 2, . . . , n


Замена переменной yij = αi xij приводит задачу к стандартному типу.
   Дальнейшее обобщение Т.З. связано с рассмотрением многоиндексных задач. Например, требу-
ется составить план транспортировки некоторого однородного продукта от центра производства к
центрам потребления с использованием транспортных средств различных типов, реализация ко-
торого обеспечивала бы минимальные транспортные затраты. Формальная запись условий задачи

Страницы