Файл: Практикум Челябинск 2019.pdf

40
Рис. 2.1.7. Решение z=23,75; x
1
=3,75; x
2
=1,25
2. Выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи не является целочисленным.
Например, выбирая x
1
=3,75, замечаем, что область 3 < x
1
< 4 пространства допустимых значений не содержит целочисленных значений переменной x
1
и, следовательно, может быть исключена из рассмотрения, как бесперспективная.
Это эквивалентно замене исходной задачи ЛП0 двумя новыми задачами линейного программирования ЛП1 и ЛП2, которые определяются следующим образом:

пространство допустимых решений ЛП1 = пространство допустимых решений исходной задачи + (x
1

3),

пространство допустимых решений ЛП1 = пространство допустимых решений исходной задачи + (x
1

4).
Новые ограничения x
1

3 и x
1

4 взаимоисключаемы, следовательно, задачи ЛП1 и ЛП2 необходимо рассматривать как независимые задачи линейного программирования. В этом случае x
1
называется переменной
ветвления.
Оптимальное решение задачи целочисленного линейного программирования находится в пространстве допустимых решений либо задачи ЛП1, либо ЛП2. Следовательно, обе подзадачи должны быть решены.
2.1. Решаем сначала задачу ЛП1 (выбор произволен), имеющую дополнительное ограничение x
1

3: максимизировать z=5x
1
+4x
2
при ограничениях
.
x
,
x
,
x
,
x
x
,
x
x
0 3
45 6
10 5
2 1
1 2
1 2
1






Решение: z=23; x
1
=3; x
2
=2.

41
Оптимальное решение задачи ЛП1 удовлетворяет требованию целочисленности переменных x
1
и x
2
. В этом случае говорят, что задача
ЛП1 прозондирована. Это означает, что задача ЛП1 не должна больше зондироваться, т. к. она не может содержать лучшего решения задачи целочисленного линейного программирования.
Мы не можем в этой ситуации оценить качество целочисленного решения, полученного из рассмотрения задачи ЛП1, т. к. решение задачи
ЛП2 может привести к лучшему целочисленному решению (с большим значением целевой функции z).
Можно сказать, что значение z=23 является нижней границей оптимального (максимального) значения целевой функции исходной задачи целочисленного линейного программирования.
Это значит, что любая нерассмотренная подзадача, которая не может привести к целочисленному решению с большим значением целевой функции, должна быть исключена из рассмотрения, как бесперспективная.
Если же нерассмотренная подзадача может привести к лучшему целочисленному решению, то нижняя граница должна быть надлежащим образом изменена.
При значении нижней границы z=23 исследуем задачу ЛП2. Так как в задаче ЛП0 оптимальное значение целевой функции равно 23,75 и все ее коэффициенты являются целыми числами, то невозможно получить целочисленное решение задачи ЛП2 (пространство решений которой более узко, чем в задаче ЛП0), которое будет лучше существующего. В результате мы отбрасываем подзадачу
ЛП2 и считаем ее прозондированной.
Реализация метода ветвей и границ завершена, так как обе подзадачи
ЛП1 и ЛП2 прозондированы (рассмотрение первой привело к целочисленному решению, а второй – к заключению, что ее возможное целочисленное решение не может быть лучше существующего).
Следовательно, оптимальным решением задачи целчисленного линейного программирования является решение, соответствующее нижней границе, а именно z=23; x
1
=3; x
2
=2.
2.2. Теперь сначала решаем задачу ЛП2, имеющую дополнительное ограничение x
1

4: максимизировать z=5x
1
+4x
2
при ограничениях
.
x
,
x
,
x
,
x
x
,
x
x
0 4
45 6
10 5
2 1
1 2
1 2
1






Решение: z=23,33; x
1
=4; x
2
=0,83.

42
Так как значение переменой x
2
=0,83 не является целым числом, задача
ЛП2 исследуется далее.
Рассматриваем подзадачи ЛП3 и ЛП4, используя ветви x
2

0 и x
2

1.
Это означает, что

пространство решений ЛП3 = пространство решений ЛП2 + (x
2

0) =
= пространство допустимых решений ЛП0 + (x
1

4) + (x
2

0),

пространство решений ЛП4 = пространство решений ЛП2 + (x
2

1) =
= пространство допустимых решений ЛП0 + (x
1

4) + (x
2

1).
У нас есть три нерассмотренные подзадачи, которые должны быть решены,

ЛП1, ЛП3 и ЛП4.
Предположим, что мы произвольно выбрали первой задачу ЛП4:
.
x
,
x
x
,
x
,
x
x
,
x
x
max
x
x
z
0 1
4 45 6
10 5
4 5
2 1
2 1
2 1
2 1
2 1










Решение: нет
В качестве следующей выбираем подзадачу ЛП3:
.
x
,
x
x
,
x
,
x
x
,
x
x
max
x
x
z
0 0
4 45 6
10 5
4 5
2 1
2 1
2 1
2 1
2 1










Решение: z=22,5; x
1
=4,5; x
2
=0 .
Нецелочисленное значение переменной x
1
=4,5 порождает две ветви решений при x
1

4 и x
1

5 и соответствующие им подзадачи ЛП5 и ЛП6.
При этом

пространство решений ЛП5 = пространство решений ЛП0 + (x
1

4) +
+ (x
2

0) + (x
1

4) = пространство решений ЛП0 + (x
1
= 4) + (x
2

0),

пространство решений ЛП6 = пространство решений ЛП0 + (x
1

4) +
+ (x
2

0) + (x
1

5) = пространство решений ЛП0 + (x
1

5) + (x
2

0).
Подзадача ЛП6 не имеет решения:

43
.
x
,
x
,
x
,
x
,
x
,
x
x
,
x
x
max
x
x
z
0 5
0 4
45 6
10 5
4 5
2 1
1 2
1 2
1 2
1 2
1











Решение: нет.
Подзадача ЛП5 имеет целочисленное решение:
.
x
,
x
,
x
,
x
,
x
,
x
x
,
x
x
max
x
x
z
0 4
0 4
45 6
10 5
4 5
2 1
1 2
1 2
1 2
1 2
1











Решение: z=20; x
1
=4; x
2
=0
Следовательно, порождает нижнюю границу (z=20) оптимального решения целевой функции задачи целочисленного линейного программирования.
Теперь остается подзадача ЛП1, решение которой также является целочисленным (z=23; x
1
=3; x
2
=2).
Следовательно, нижнюю границу значений целевой функции полагаем равной 23.
Так как все подзадачи прозондированы, оптимальным решением задачи целочисленного линейного программирования является решение, соответствующее последней нижней границе, а именно z=23; x
1
=3; x
2
=2.

44
Вариант 3
F(X)=3x
1
+4x
2

max,
3x
1
+2x
2

7,
x
1
+4x
2

5,
2x
1

3x
2

3,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 4
F(X)=x
1
+2x
2

max,
4x
1
+3x
2

24,

x
1
+x
2

3,
2x
1

2x
2

3,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 5
F(X)=x
1
+x
2

max,
x
1
+2x
2

10,
2x
1
+x
2

10,
x
1
+2x
2

2,
4x
1

3x
2

12,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 6
F(X)=2x
1
+12x
2

max,

x
1
+ 2x
2

4,
7x
1
+ 4x
2

28,
4x
1

3x
2

3,
5x
1
+2x
2

10,
10x
1

8x
2

2,
x
1
, x
2

0, x
1
, x
2
– целые.
Вариант 7
F(X)=x
1
+x
2

max,
3x
1
+x
2

20,
2x
1
+3x
2

30,
4x
1

3x
2

13,
5x
1
+2x
2

10,
10x
1

8x
2

2,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 8
F(X)=7x
1
+6x
2

max,

3x
1
+2x
2

9,
3x
1
+4x
2

24,
2x
1
+x
2

8,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 9
F(X)=2x
1
+5x
2

min,
3x
1
+ 3x
2

15,
8x
1
+ 4x
2

32,
4x
1
+ 3x
2

12,
5x
1
+2x
2

11,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 10
F(X)=3x
1

3x
2

max,
x
1

4x
2

4,
3x
1
+2x
2

6,

x
1
+9x
2

7,
x
1
+2x
2

5,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 11 F(X)=10x
1
+12x
2

min,
x
1
+ 4x
2
≥ 80,
2x
1
+ 4x
2
≥ 60,
2x
1
+ x
2
≥ 30,
5x
1
+ 2x
2

45,
x
1
, x
2
, x
3

0,
x
1
, x
2
, x
3
– целые.
Вариант 12
F(X)=

2x
1
+4x
2

min,
x
1

3x
2
≤ 1,
x
1
+x
2
≤ 5,

x
1
+x
2

2,
5x
1
+ 2x
2

19,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 13 F(X)=2x
1
+x
2

max,
2x
1
+ 3x
2
≤ 12,
4x
1
+ x
2
≥ 20,

x
1
+3x
2

2,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 14
F(X)=4x
1
+3x
2

max,
3x
1
+ 2x
2
≤ 8,
x
1
+ 4x
2

10,
5x
1
+2x
2
≥ 7,
x
1
, x
2

0,
x
1
, x
2
– целые.

45
Вариант 15
F(X)=8x
1
+6x
2

max,
2x
1
+5x
2
≤ 12,
3x
1
+ x
2
≤ 6,
2x
1

3x
2
≤ 12,
x
1
, x
2

0,
x
1
, x
2
– целые.
Вариант 16
F(X)=6x
1
+4x
2

min,
3x
1
+ 2x
2
≥ 16,
2x
1

3x
2
≥

6,
x
1

x
2
≤ 4,
x
1
, x
2

0,
x
1
, x
2
– целые.
Контрольные вопросы
1. Какие задачи называются задачами целочисленного (дискретного) программирования?
2. Сформулируйте задачу линейного целочисленного программирования.
3. Какие методы используются для решения задач дискретного программирования?
4. Опишите алгоритм метода ветвей и границ.
5. Какие особенности решения в MS Office Excel целочисленных задач линейного программирования?
Практическая работа 3. ТРАНСПОРТНАЯ ЗАДАЧА. РЕШЕНИЕ
ТРАНСПОРТНОЙ ЗАДАЧИ С ПОМОЩЬЮ ПРОГРАММЫ
MICROSOFT OFFICE EXCEL
КРАТКАЯ СПРАВКА
Транспортная задача– одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанных с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Рассмотрим модель транспортной задачи на примере прикрепления пунктов производства к пунктам назначения. В m пунктах производства А
1
, А
2
, … А
m
имеется однородный груз в количестве соответственно a
1
, a
2
, … a
m
. Этот груз необходимо доставить в n пунктов назначения В
1
, В
2
, … В
n
в количестве соответственно b
1
, b
2
, … b
n
. Стоимость перевозки единицы груза (тариф) из пункта А
i
в пункт В
j
равна с
ij
. Требуется составить оптимальный план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость. При
этом потребности каждого потребителя должны быть удовлетворены в
соответствии с возможностями поставщиков.
Обозначим количество груза, перевозимого из пункта А
i в пункт В
j
,через x
ij
.
Тогда целевая функция задачи (совокупные транспортные расходы по системе поставщиков – потребителей) будет иметь вид
 





m
i
n
j
ij
ij
min
x
c
X
F
1 1
при ограничениях

46
,
b
x
,
a
x
j
m
i
ij
i
n
j
ij






1 1
n
,
j
,
m
,
i
,
x
ij
1 1
0



В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.
Если





n
j
j
m
i
i
b
a
1 1
, то транспортная задача называется закрытой.
Если





n
j
j
m
i
i
b
a
1 1
, то транспортная задача называется открытой.
Если дана открытая задача, то ее необходимо привести к закрытой форме. В том случае, когда потребности по пунктам назначения превышают запасы пунктов производства, вводится фиктивный пункт производства с недостающим объемом отправления, а если запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.
Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.
Транспортная задача как задача линейного программирования может быть решена симплексным методом, однако, наличие большого числа переменных и ограничений делает вычисления громоздкими.
Поэтому для решения транспортных задач разработан специальный алгоритм, имеющий те же этапы, что и симплексный метод:
1. Нахождение исходного опорного решения.
2. Проверка этого решения на оптимальность.
3. Переход от одного опорного решения к другому.
Исходное опорное решение можно найти: методом Северо-Западного угла или методом минимальных затрат (методом минимального элемента).
Для проверки плана на оптимальность можно применить один из двух методов: метод испытания пустых клеток или метод потенциалов.
Пример 3. Сельскохозяйственные кооперативы (m=4) выращивают зерно. В качестве пунктов потребления выступают зерновые склады или элеваторы для хранения зерна (n=3). Объемы производства зерна следующие: кооператив № 1 – 155,5 т, кооператив № 2 – 250 т, кооператив
№ 3 – 170 т, кооператив № 4 – 134,5 т. Требуемые объемы хранения зерна следующие: склад № 1 – 350 т, склад № 2 – 250 т, склад № 3 – 400 т.
Стоимость транспортировки 1 т зерна между кооперативами и складами задана в таблице 3.