ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.02.2026
Просмотров: 820
Скачиваний: 2
элементам |
|
|
|
|
|
|
|
|
|
|
|
|
разрешающего |
столбца: |
||||||||||
ì |
3 |
|
|
|
|
|
|
9 |
- |
9 |
ü |
- |
9 |
|
|
|||||||||
ï13 |
|
|
|
|
23 |
|
7 |
|
|
|
|
|
ï |
|
|
|
|
|||||||
11 |
|
|
11 |
11 |
11 |
. |
|
|||||||||||||||||
miní |
|
|
|
|
|
, |
|
, |
|
|
|
|
|
, |
|
|
|
ý |
= |
|
|
|
|
|
|
4 |
|
|
1 |
|
|
1 |
|
|
|
1 |
|
|
1 |
|
|||||||||
ï |
|
|
|
|
|
|
|
- |
ï |
- |
|
|
||||||||||||
ï |
11 |
|
|
|
|
11 |
11 |
ï |
11 |
|
|
|||||||||||||
î |
|
|
|
|
|
|
þ |
|
|
|
|
|||||||||||||
Базисную переменную X 6 переводим в свободные переменные, а свободную переменную X 4 - в базисные.
В результате преобразования симплекс-таблицы получим:
Базисные |
Свободные |
Свободные |
|
||||
переменные |
|
||||||
переменные |
члены |
|
|
|
|
|
|
x6 |
|
x5 |
|
||||
|
|
|
|
||||
x1 |
10 |
4 |
|
-3 |
|
||
x3 |
14 |
11 |
|
-8 |
|
||
x2 |
7 |
1 |
|
-1 |
|
||
x4 |
9 |
-11 |
|
|
9 |
|
|
|
|
|
|
|
|||
Z |
67 |
25 |
|
-19 |
|
||
Базисное решение X = (10; 7; 14; 9; 0;0) |
- допустимое, т.к. |
||||||
в столбце свободных членов нет ни одного отрицательного элемента, но неоптимальное (в строке целевой функции, кроме столбца свободных членов, элементы не одного знака). Целевая функция ограничена сверху, т.к. в столбце, не удовлетворяющем признаку оптимальности, есть положительные элементы.
Столбец, не удовлетворяющий признаку оптимальности ( X 5 ), принимаем в качестве разрешающего. Разрешающей
является строка X , т.к. minì9ü = 1.
4 í ý î9þ
Базисную переменную X 4 переводим в свободные переменные, а свободную переменную X 5 - в базисные.
50
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
Преобразуем симплекс-таблицу:
Базисные |
Свободные |
|
|
|
|
|
Свободные |
|
|
|
|
|||||||
|
|
|
переменные |
|
|
|
|
|||||||||||
переменные |
члены |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x6 |
|
x4 |
|
|||||||||||||||
|
|
|
|
|||||||||||||||
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
||||||
x1 |
13 |
|
3 |
|
|
|
|
|
|
|
3 |
|
|
|
||||
|
|
1 |
2 |
|
|
|
|
|
8 |
|
|
|
||||||
x3 |
22 |
9 |
|
|
|
|
9 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
||||||||||
|
|
− |
|
2 |
|
|
|
|
1 |
|
|
|
||||||
x2 |
8 |
9 |
|
|
|
9 |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|||||||||||
|
|
−1 |
2 |
|
|
|
1 |
|
|
|
||||||||
x5 |
1 |
|
|
9 |
|
|
|
|||||||||||
|
|
9 |
|
|
|
|
|
|||||||||||
|
|
1 |
7 |
|
|
|
|
2 |
1 |
|
|
|||||||
Z |
86 |
9 |
|
|
|
|
9 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||
Базисное решение X = (13; 8; 22; 0; 1; 0) |
- допустимое, |
|||||||||||||||||
т.к. в столбце свободных членов нет ни одного отрицательного элемента, и оптимальное (в строке целевой функции все элементы положительные (одного знака)).
Найденное оптимальное решение целочисленное, следовательно, задача целочисленного программирования решена.
Максимальное значение целевой функции Zmax = 86
при X * = (13; 8; 22; 0; 1; 0) .
9. Транспортная задача
П о с т а н о в к а т р а н с п о р т н о й з а д а ч и .
У m поставщиков A1, A2, ..., Am сосредоточен однородный груз в количествах соответственно a1, a2,...,am .
Имеющийся груз необходимо доставить n потребителям
51
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
B1, B2, ..., Bn , спрос которых равен соответственно b1, b2,...,bn . Известна стоимость перевозки единицы груза от i – го поставщика к j - му потребителю - сij . Требуется найти
оптимальный план перевозок, обеспечивающий минимальные затраты и вывоз грузов и удовлетворение потребностей.
Э к о н о м и к о - м а т е м а т и ч е с к а я |
м о д е л ь |
з а д а ч и . |
|
Пусть xij - количество единиц |
груза, которое |
необходимо доставить от i – го поставщика к j - му потребителю.
Целевая функция:
|
m |
n |
(1)- минимизация общих затрат |
Z = |
å |
å cij xij ® min |
|
|
j =1i =1 |
|
|
на реализацию плана перевозок. Ограничения на запасы поставщиков:
n |
|
|
(2) - все запасы должны быть |
å xij = ai ,i = 1, m |
|||
j=1 |
|
||
вывезены.
Ограничения на спрос потребителей:
m
å xij = b j , j =1, n (3) - все потребности должны быть i =1
удовлетворены.
Условия неотрицательности: xij ³ 0 i = 1, m j = 1, n) (4)
Модель транспортной задачи называют закрытой, если суммарный объём груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т.е. выполняется условие
|
m |
n |
|
Если |
это |
условие |
не |
выполняется |
|
å ai = |
å b j . |
|
|||||
i =1 |
j =1 |
|
|
|
|
|
|
|
( |
m |
n |
), |
то модель |
транспортной |
задач |
называется |
|
å ai ¹ |
å b j |
|||||||
|
i =1 |
j =1 |
|
|
|
|
|
|
открытой.
52
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
Если |
m |
n |
å ai > |
å b j , то открытая транспортная задача |
|
|
i =1 |
j =1 |
сводится к закрытой путем ведения фиктивного потребителя с
объемом |
потребностей |
m |
|
n |
|
и |
|
стоимостями |
|
bn+1 = å ai - |
å b j |
|
|||||||
|
|
i =1 |
|
j =1 |
|
|
|
|
|
перевозок, |
равными нулю. Если |
m |
|
n |
|
, |
то |
вводится |
|
å ai < |
å b j |
||||||||
|
|
|
i =1 |
|
j =1 |
|
|
|
|
фиктивный поставщик с объемом груза |
am+1 = |
n |
|
m |
|||||
å |
b j - å ai и |
||||||||
|
|
|
|
|
|
j =1 |
i=1 |
||
стоимостями перевозок, равными нулю.
Число переменных xij в транспортной задаче с m
поставщиками и n потребителями равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как предполагается, что
выполняется условие |
m |
n |
å ai = |
å b j , то число линейных |
|
|
i =1 |
j =1 |
независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонент равно n+m-1, то план является невырожденным, а если меньше – то вырожденным.
Транспортная задача является канонической задачей линейного программирования, и для ее решения в принципе можно использовать симплекс-метод. Однако, в силу специфичности транспортной задачи, используются более эффективные методы.
А л г о р и т м р е ш е н и я т р а н с п о р т н о й з а д а ч и ( м е т о д о м п о т ен ц и а л о в ) .
1.Определяется исходный план (метод северо- западного угла, метод минимальной стоимости и др.).
2.Производится оценка плана.
3.Осуществляется переход к следующему плану.
53
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com