Составители:
Рубрика:
99
Глава 3. СИМПЛЕКСНЫЙ МЕТОД
Симплексный метод разработал американский ученый Дж.Б.Данциг в 1947 г. и
впервые опубликовал его в журнале «Эконометрика» во второй половине 1949 г., т.е.
ровно через 10 лет после выхода в свет первой работы в области линейного
программирования советского ученого Л. В. Канторовича, в которой был изложен метод
разрешающих множителей.
Эти два метода в основе своей схожи, однако симплексный метод был разработан
независимо от метода разрешающих множителей.
Название метода произошло от названия геометрической фигуры, уравнение которой
было использовано Дж. Б. Данцигом в одном из доказательств.
Идея метода содержит три существенных момента. Во-первых, указывается способ
вычисления исходной программы (опорного плана). Во-вторых, устанавливается признак,
позволяющий проверять выбранную программу на оптимальность. И, в-третьих, приводится
способ, позволяющий по выбранной неоптимальной программе построить другую программу,
более близкую к оптимальной. Таким образом, выполнив конечное число повторяющихся
математических вычислений (итераций), можно получить оптимальную программу (план).
Исходя из этого, в целом ряде книг этот метод называют методом последовательного
улучшения плана.
3.1. Основной алгоритм симплексного метода
К настоящему времени разработано и усовершенствовано несколько алгоритмов
симплексного метода. Сначала здесь нами рассматривается решение задачи с помощью
основного алгоритма симплексного метода.
Рассмотрим применение основного алгоритма симплексного метода на примере
задачи, которая нами была изложена и математически сформулирована в 1.2.
В результате проведенных преобразований была получена математическая модель
задачи, заключающаяся в максимизации целевой функции
F=3x
1
+4x
2
+6x
3
+0⋅x
4
+0⋅x
5
+0⋅x
6
+0⋅x
7
, при ограничениях, представляющихся в виде
системы линейных уравнений:
=+++
=+++
=+++
=+++
2200524
,1800323
,100024
,1500532
7321
6321
5321
4321
xxxx
xxxx
xxxx
xxxx
и при условии
x
j
≥
0
j
=1,2,…,7.
Далее перепишем значение целевой функции и ограничительные линейные
уравнения еще раз. При этом, во-первых, поменяем местами левые и правые части
уравнений. Во-вторых, в каждом уравнении укажем все до одного неизвестные и
коэффициенты, включая и те, значения которые равны нулю.
Итак:
max0000643
7654321
=++++++= xxxxxxxF (3.1)
++++++=
++++++=
++++++=
++++++=
.10005242200
,01003231800
,00102411000
,00015321500
7654321
7654321
7654321
7654321
xxxxxxx
xxxxxxx
xxxxxxx
xxxxxxx
(3.2)
Уравнения вида (3.2) принято называть симплексными n.
Страницы
- « первая
- ‹ предыдущая
- …
- 97
- 98
- 99
- 100
- 101
- …
- следующая ›
- последняя »
