ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1079
Скачиваний: 2
111
дополнительных
объемов
ресурсов
T
Т
=(t
1
,t
2
,t
3
).
Используя
найденные
двойственные
оценки
ресурсов
,
сформируем
условия
их
наличия
у
предприятия
,
а
именно
,
В
+ Q T
0,
где
матрица
Q
состоит
из
векторов
А
5
,
А
6
,
А
7
в
3-
й
симплекс
таблице
.
Задача
состоит
в
нахождении
вектора
дополнительных
объемов
ресурсов
T
Т
=(t
1
, 0, t
3
),
доставляющего
при
условии
сохранения
двойственных
оценок
ресурсов
Y
o
=(6, 0, 4)
наибольшее
значение
суммарному
приросту
производства
продукции
χ
= Y
o
T
= 6t
1
+ 4t
3
(1
Р
)
и
сохраняющего
структуру
выбранной
производственной
программы
0
0
0
0
5
4
1
5
3
5
2
0
5
4
1
0
1
20
13
27
3
1
t
t
.
(2
Р
)
Предполагается
,
что
дополнительно
можно
получить
не
более
10%
первоначального
объема
ресурса
каждого
вида
,
т
.
е
.
t
t
1
3
0
181
107
208
1
,
0
, (3
Р
)
по
смыслу
задачи
t
1
0, t
3
0. (4
Р
)
Переписав
неравенства
(2
Р
) , (3
Р
)
и
(4
Р
)
в
виде
:
20
5
4
5
3
13
5
2
5
4
27
3
1
3
1
3
1
t
t
t
t
t
t
(5
Р
)
0
≤
t
1
≤
20,8; 0
≤
t
2
≤
18,1, (6
Р
)
приходим
к
задаче
нахождения
наибольшего
значения
функции
(1
Р
)
при
условиях
(5
Р
), (6
Р
),
решением
которой
графическим
методом
(
рис
. 2)
является
точка
M(20,8; 18,1).
Программа
«
расшивки
»
имеет
вид
t
1
= 20,8, t
2
= 0, t
3
= 18,1
и
прирост
производства
продукции
составит
197,2.
t
3
27
18,1
grad
χ
W
20,8
0
16,25
27 33,3
t
1
Рис
.2
Т
0
=(20,8;18,1)
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
112
2.12.
Транспортная
задача
линейного
программирования
Ранее
была
рассмотрена
задача
,
в
которой
m
пунктов
-
поставщиков
производят
однородный
продукт
в
количествах
a
1
,…,a
i
,…,a
m
единиц
для
перевозки
в
другие
n
пунктов
-
потребителей
,
где
этот
продукт
используется
в
количествах
b
1
, …, b
j
, …, b
n
.
единиц
.
Стоимость
перевозки
(
тариф
)
одной
единицы
продукта
от
i
-
го
поставщика
(i = 1, 2, … m)
до
j
-
го
потребителя
(j = 1,
2, …, n)
равна
c
ij
стоимостных
единиц
.
Рассмотрим
закрытую
модель
транспортной
задачи
линейного
программирования
,
когда
количество
отправляемого
продукта
всеми
поставщиками
равно
количеству
получаемого
продукта
всеми
потребителями
,
т
.
е
.
m
i
1
a
i
=
n
j
1
b
j
.
Требуется
сформировать
план
перевозок
продукта
,
при
котором
все
потребности
в
продукте
будут
удовлетворены
с
наименьшими
затратами
на
перевозку
.
Определим
вектор
X = (x
11
,… ,x
ij
, … ,x
mn
),
как
план
перевозок
от
поставщиков
к
потребителям
,
где
x
ij
–
количество
единиц
продукта
,
которое
планируется
к
перевозке
от
i-
го
поставщика
к
j-
му
потребителю
,
при
чем
эта
перевозка
либо
имеет
место
,
либо
отсутствует
,
т
.
е
. x
ij
≥
0, i=1, 2,..,m; j = 1, 2, …, n,
Тогда
: f(X) =
m
i
1
n
j
1
c
ij
x
ij
–
суммарная
стоимость
всех
перевозок
.
От
i-
го
поставщика
вывозиться
весь
продукт
,
т
.
е
. x
i1
+ … +x
ij
+ … + x
in
= a
i
, i = 1, 2,
… m,
а
j-
й
потребитель
получает
столько
продукта
,
сколько
ему
необходимо
,
т
.
е
. x
1j
+ … +x
ij
+ … + x
mj
= b
j
, j = 1, 2, …, n.
Таким
образом
,
приходим
к
следующей
транспортной
задаче
линейного
программирования
(
ТЗЛП
)
на
минимум
:
(1) f(X) =
m
i
1
n
j
1
c
ij
x
ij
(min),
(2) x
i1
+ … +x
ij
+ … + x
in
= a
i
, i=1, 2, … m,
(3) x
1j
+ … +x
ij
+ … + x
mj
= b
j
, j = 1, 2, …,n,
(4) x
ij
≥
0 , i=1, 2, … m; j = 1, 2, …,n.
В
матрице
условий
транспортной
задачи
ЛП
обозначим
столбец
,
соответствующий
переменной
x
ij
,
через
A
ij
, (i = 1, 2, … m; j = 1, 2, …,n.).
Тогда
систему
векторов
условий
задачи
можно
записать
в
виде
таблицы
1,
а
систему
ограничений
(2) – (3) -
в
виде
m
i
1
n
j
1
А
ij
x
ij
=
В
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
113
Таблица
1
A
11
A
12
.. A
1n
A
21
.. A
2n
.. A
i1
.. A
ij
.. A
in
.. A
m1
A
m2
A
mn
B
1 1 .. 1 0 .. 0 .. 0 .. 0 .. 0 .. 0 0 .. 0 a
1
0 0 .. 0 1 .. 1 .. 0 .. 0 .. 0 .. 0 0 .. 0 a
2
… … .. … … .. … .. …
.. …
.. …
.. … … .. … …
0 0 0 0 0 1 1 1 0 0 0 a
i
… … .. … … .. … .. …
.. …
.. …
.. … … .. … …
0 0 0 0 0 0 0 0 1 1 1 a
m
1 0 0 1 0 1 0 0 1 0 0 b
1
0 1 0 0 0 0 0 0 0 1 0 b
2
… … .. … … .. … .. …
.. …
.. …
.. … … .. … …
0 0 0 0 0 0 1 0 0 0 0 b
j
… … .. … … .. … .. …
.. …
.. …
.. … … .. … …
0 0 1 0 1 0 0 1 0 0 1 b
n
Очевидно
,
что
транспортную
задачу
ЛП
можно
решить
симплекс
методом
.
Однако
размер
матрицы
условий
[(nm) x (m+n)]
указывает
на
то
,
что
для
решения
лучше
использовать
специальные
методы
,
одним
из
которых
является
метод
потенциалов
.
Для
использования
этого
метода
матрицу
условий
задачи
удобно
записывать
в
виде
транспортной
таблицы
2 (
ТТ
):
Таблица
2
с
11
… c
1j
… c
1n
a
1
… … … … … …
c
i1
… c
ij
… c
in
a
i
… … … … …
c
m1
… c
mj
… c
mn
a
m
b
1
… b
j
… b
n
Утверждение
1
.
Для
любых
x
ij
, (i = 1, 2, … m; j = 1, 2, …, n)
выполняется
равенство
A
ij
= A
i1
+ A
1j
– A
11
.
▲
Проверить
это
утверждение
следует
из
указанных
действий
с
соответствующими
столбцами
матрицы
условий
(
табл
. 1).
■
Определение
.
Циклом
в
транспортной
таблице
называют
замкнутую
ломаную
линию
,
удовлетворяющую
следующим
условиям
:
все
вершины
ломаной
находятся
в
клетках
транспортной
таблицы
;
все
ребра
ломаной
проходят
по
клеткам
транспортной
таблицы
и
расположены
либо
в
строке
,
либо
в
столбце
этой
таблицы
;
к
каждой
вершине
ломаной
подходят
два
ребра
,
одно
по
строке
,
другое
по
столбцу
.
Определение
.
Две
вершины
цикла
называют
соседними
,
если
их
соединяет
одно
и
то
же
ребро
.
Циклы
транспортной
таблицы
обладают
следующими
свойствами
:
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
114
каждая
вершина
цикла
имеет
единственную
соседнюю
вершину
,
как
в
строке
,
так
и
в
столбце
;
в
любой
строке
и
в
любом
столбце
транспортной
таблицы
содержится
четное
число
вершин
цикла
,
либо
их
там
нет
.
Определение
.
Набор
клеток
транспортной
таблицы
называется
ацикличным
,
если
не
существует
цикла
,
вершины
которого
находятся
в
клетках
данного
набора
.
Утверждение
2
.
Векторы
условий
транспортной
задачи
линейного
программирования
А
1
1
j
i
, …,
А
k
k
j
i
(
табл
. 1)
образуют
линейно
независимую
систему
тогда
и
только
тогда
,
когда
набор
клеток
(i
1
, j
1
), …, (i
k
, j
k
) (
табл
. 2)
является
ацикличным
.
Пример
.
Ацикличному
набору
клеток
в
транспортной
таблице
соответствует
система
линейно
независимых
векторов
условий
транспортной
задачи
,
т
.
е
.
линейно
независимая
система
векторов
А
12
,
А
15
,
А
23
,
А
32
,
А
34
,
А
41
.
Следствие
1
.
Ранг
системы
векторов
условий
транспортной
задачи
линейного
программирования
равен
m + n – 1 ,
где
m –
число
поставщиков
, n –
число
потребителей
.
▲
Рассмотрим
векторы
А
11
,
А
12
, …,
А
1n
,
А
21
, …,
А
m1
.
Эти
векторы
образуют
линейно
независимую
систему
,
так
как
соответствуют
ациклическому
набору
клеток
транспортной
таблицы
.
Кроме
того
,
любой
вектор
A
ij
(i = 1, 2, … m; j = 1, 2, …,n)
условий
транспортной
задачи
согласно
утв
.1
линейно
раскладывается
по
векторам
рассматриваемой
системы
.
Следовательно
,
рассматриваемый
набор
векторов
является
базисом
системы
векторов
условий
транспортной
задачи
.
Так
как
по
определению
ранг
системы
векторов
равен
числу
векторов
в
любом
его
базисе
,
то
ранг
системы
векторов
транспортной
задачи
совпадает
с
числом
векторов
в
рассматриваемой
системе
векторов
и
равен
m + n –1.
■
Пусть
вектор
α
0
=(x
ij
0
, …, x
mn
0
)
является
допустимым
решением
транспортной
задачи
линейного
программирования
.
Ненулевые
координаты
этого
вектора
,
т
.
е
.
х
ij
0
≠
0,
запишем
в
соответствующие
клетки
транспортной
таблицы
.
Следствие
2
.
Вектор
α
0
= (x
11
0
, …, x
mn
0
)
является
опорным
решением
транспортной
задачи
линейного
программирования
тогда
и
только
тогда
,
когда
х
12
х
15
х
23
х
32
х
34
х
41
х
11
х
12
х
1n
х
21
х
m1
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
115
набор
заполненных
клеток
является
ацикличным
.
Для
нахождения
базиса
опорного
решения
α
0
=(x
11
0
, …, x
mn
0
)
транспортной
задачи
линейного
программирования
необходимо
:
записать
все
ненулевые
координаты
вектора
в
соответствующие
клетки
транспортной
таблицы
;
в
некоторые
из
оставшихся
пустыми
клеток
транспортной
таблицы
дописать
«
жирным
»
шрифтом
нули
так
,
чтобы
образовать
ацикличный
набор
из
m + n – 1
заполненных
клеток
;
векторы
условий
транспортной
задачи
,
соответствующие
заполненным
клеткам
,
будут
являться
базисом
опорного
решения
α
0
=(x
11
0
, …, x
mn
0
).
Чтобы
решить
транспортную
задачу
линейного
программирования
методом
потенциалов
,
необходимо
,
как
и
в
симплекс
алгоритме
,
знать
начальное
опорное
решение
.
Для
нахождения
начального
опорного
решения
транспортной
задачи
линейного
программирования
воспользуемся
методом
минимальной
стоимости
.
Рассмотрим
транспортную
задачу
линейного
программирования
и
соответствующую
ей
транспортную
таблицу
.
Шаг
1
.
Выбираем
клетку
в
транспортной
таблице
с
наименьшим
тарифом
–
с
ij
.
Положим
,
что
x
ij
= min{a
i
, b
j
}
если
a
i
< b
j
,
то
x
ij
= a
i
,
это
равносильно
тому
,
что
от
i-
го
поставщика
вывезен
весь
продукт
,
а
j-
му
потребителю
осталось
завести
b
j
– a
i
= b
j
’
единиц
продукта
;
вычеркиваем
i-
ю
строку
;
если
a
i
> b
j
,
то
x
ij
= b
j
,
это
равносильно
тому
,
что
j-
му
потребителю
завезли
весь
продукт
,
а
от
i-
го
поставщика
осталось
вывести
a
i
– b
j
= a
i
’ ,
вычеркиваем
j-
й
столбец
;
если
a
i
= b
j
,
то
x
ij
= a
i
= b
j
,
это
равносильно
тому
,
что
от
i-
го
поставщика
вывезен
весь
продукт
и
j-
му
потребителю
завезен
весь
продукт
;
вычеркиваем
i-
ю
строку
и
j-
й
столбец
.
Шаг
2
.
Повторяем
шаг
1
с
оставшейся
частью
транспортной
таблицы
и
т
.
д
.
Через
конечное
число
шагов
получим
опорное
решение
.
Замечание
.
Выбор
наименьшего
тарифа
осуществляется
пометкой
наименьшего
тарифа
в
каждой
строке
,
а
затем
пометкой
наименьшего
тарифа
в
каждом
столбце
.
Наименьший
тариф
окажется
в
клетке
с
двумя
пометками
.
После
вычеркивания
строки
или
столбца
на
каждом
шаге
расстановка
пометок
c
ij
a
i
b
j
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.