Составители:
подчеркнем, что в отличие от метода перебора симплекс-метод дает возможность вести поиск
целенаправленно, уменьшая на каждом шаге значение целевой функции.
В качестве примера, иллюстрирующего симплекс-метод, рассмотрим задачу об использовании ресурсов.
4.5 Задача о ресурсах. В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м
2
стекла, 160 чел.-ч (человеко-часов) рабочего времени. Бригаде поручено изготовлять два наименования
изделий — А и Б. Цена одного изделия А 10 р., для его изготовления необходимо 4 кг металла, 2 м
2
стекла и 2
чел.-ч рабочего времени. Цена одного изделия Б 12 р., для его изготовления необходимо 5 кг металла, 1 м
2
стекла и 3 чел.-ч рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее
стоимость была максимальной.
Сначала сформулируем задачу математически. Обозначим через х
1
и х
2
количество изделий А и Б, которое не-
обходимо запланировать (т. е. это искомые величины). Имеющиеся ресурсы сырья и рабочего времени
зададим в виде ограничений-неравенств:
.16032
,1002
,30054
21
21
21
≤+
≤+
≤
+
xx
xx
xx
(9.38)
Полная стоимость запланированной к производству продукции выражается формулой
.1210
21
xxf
+
=
(9.39)
Таким образом, мы имеем задачу линейного программирования, которая состоит в определении оптимальных
значений проектных параметров х
1
, х
2
, являющихся целыми неотрицательными числами, удовлетворяющих
линейным неравенствам 9.38 и дающих максимальное значение линейной целевой функции (9.39).
Вид сформулированной задачи не является каноническим, поскольку условия(9.38) имеют вид неравенств, а
не уравнений. Как уже отмечалось выше, такая задача может быть сведена к канонической путем введения до-
полнительных переменных х
3
, х
4
, х
5
по количеству ограничений-неравенств (9.38). При этом выбирают эти
переменные такими, чтобы при их прибавлении к левым частям соотношений 9.38 неравенства превращались
в равенства. Тогда ограничения примут вид
.16032
,1002
,30054
521
421
321
=++
=++
=
+
+
xxx
xxx
xxx
(9.40)
При этом очевидно, что .0 ,0 ,0
443
≥≥≥ xxx Заметим, что введение дополнительных неизвестных не
повлияло на вид целевой функции (9.39), которая зависит только от параметров х
1
, х
2
. Фактически x
3
, x
4
, х
5
будут указывать остатки ресурсов, не использованные в производстве. Здесь мы имеем задачу максимизации,
т.е. нахождения максимума целевой функции. Если функцию 9.39 взять со знаком минус, т. е. принять
целевую функцию в виде
,1210
21
xxF
−
−
=
(9.41)
то получим задачу минимизации для этой целевой функции.
Примем переменные x
3
, x
4
, х
5
в качестве базисных и выразим их через свободные переменные х
1
, х
2
из урав-
нений (9.40). Получим
.32160
,2100
,54300
215
214
213
xxx
xxx
xxx
−−=
−−=
−
−
=
(9.42)
В качестве опорного решения возьмем такое, которое соответствует нулевым значениям свободных
параметров:
.160 ,100 ,300 ,0 ,0
)0(
5
)0(
4
)0(
3
)0(
2
)0(
1
===== xxxxx
(9.43)
Этому решению соответствует нулевое значение целевой функции 9.41:
.0
)0(
=F
(9.44)
Исследуя полученное решение, отмечаем, что оно не является оптимальным, поскольку значение целевой
функции (9.41) может быть уменьшено по сравнению с (9.44) путем увеличения свободных параметров.
Положим x
2
= 0 и будем увеличивать переменную x
1
до тех пор, пока базисные переменные остаются поло-
жительными. Из (9.42) следует, что х
1
можно увеличить до значения х
1
= 50, поскольку при большем его
значении переменная x
4
станет отрицательной.
Таким образом, полагая x
1
= 50, х
2
= 0, получаем новое опорное решение (значения переменных х
3
, х
4
, х
5
найдем по формуле (9.42):
.60 ,0 ,100 ,0 ,50
)1(
5
)1(
4
)1(
3
)1(
2
)1(
1
===== xxxxx
(9.45)
Страницы
- « первая
- ‹ предыдущая
- …
- 143
- 144
- 145
- 146
- 147
- …
- следующая ›
- последняя »
