Составители:
Рубрика:
118
(3.17) исходной задачи и продолжить таким образом решение на минимум целевой
функции исходной задачи.
Если окажется, что минимум целевой функции вспомогательной задачи не равен
нулю, то опорного плана исходной задачи не существует, т. е. исходная задача не имеет
решения.
Рассмотрим сущность этого способа на решении приведенной здесь раскройной
задачи (первая, с условием
∑
=
=
n
j
ijij
bx
1
,
α
решается подобным же образом).
Итак, с целью отыскания одного из решений этой задачи, приступим к решению
вспомогательной задачи, ограничительные условия которой выражены симплексными
уравнениями (3.24), а целевая функция — выражением (3.25).
1
Симплексные уравнения исходных условий, применительно к первому примеру, примут
окончательную форму:
2=1х
1
-1х
2
+2х
3
-1х
4
+1y
1
+0y
2
+0y
3
;
6=2х
1
+1х
2
-3х
3
+1х
4
+0y
1
+1y
2
+0y
3
;
7=1х
1
+1х
2
+1х
3
+1х
4
+0y
1
+0y
2
+1y
3
.
Для этого составляем первую симплексную таблицу и проводим последовательные
вычисления и преобразования подобно тому, как было изложено в предыдущем параграфе.
С целью некоторого упрощения вычислений компоненты вектора свободных членов
разделим на общий коэффициент 100. В дальнейшем, после того как задача будет решена, и
будет найден оптимальный план, полученные значения базисных переменных умножим на
этот же коэффициент 100.
Поскольку читатель уже освоил технику вычислений решения задачи симплексным
методом, все итерации представим в одной общей табл. 3.6.
Отличительная особенность решения этой задачи от рассмотренной в предыдущем
параграфе заключается в том, что здесь определяется не максимум, а минимум целевой
функции. При решении этой задачи на минимум можно было поменять все знаки
двойственных оценок на обратные и дальше все операции производить тем же способом
как и ранее. Но можно сделать иначе. Оставим те знаки двойственных оценок, какие они
есть, а в качестве ключевого выберем такой столбец, у которого имеется наибольшая
положительная оценка, а не наименьшая, отрицательная как раньше. Решение будет
оптимально тогда, когда не останется ни одной положительной оценки, превышающей ноль,
т.е. когда все ∆
j
≤0. Так мы и будем решать эту задачу.
Первая программа оказалась не оптимальной. Переходим ко второй программе. Для
этого введем в базисные переменную x
1
, поскольку двойственная оценка в этом столбце
оказалась наибольшей из положительных. При переходе к «лучшему» решению это
обеспечивает наибольшее снижение целевой функции F' при ее минимизации. Принимая в
качестве базисной переменную x
1
, вместо уз, получим новую программу P
2
.
Однако эта 2-я программа, соответствующая 2-й итерации, так же как и первая,
оказалась не оптимальной. Поэтому переходим к следующей программе. Для этого в
качестве базисной примем переменную х
4
вместо y
4
, так как в столбце, соответствующем х
4
,
оказалась самая большая положительная двойственная оценка на этой 2-й итерации.
Программы, соответствующие 3-й, а затем и 4-й итерации, оказались также не
оптимальными. По табл. 3.6 нетрудно проверить это и проследить последовательные
переходы от одной итерации к другой с целью улучшения плана.
Программа P
5
, соответствующая 5-й итерации, оказалась оптимальной, так как нет
ни одной оценки
j
∆
более нуля. Целевая функция F
'
5
равна нулю. Следовательно, в
Страницы
- « первая
- ‹ предыдущая
- …
- 116
- 117
- 118
- 119
- 120
- …
- следующая ›
- последняя »
