Геометрическое решение ЗЛП с n>2

Геометрическим способом можно также решать задачи линейного программирования с числом переменных более двух, при условии, что в их канонической записи содержится не более двух свободных переменных п-т< 2.

Рассмотрим этот случай на примере:

xi - х2 + 4х3 - 2х4 = 2

< 3х! + 2х2 - х3 + 4х4 = 3 xi>0, i = l,4

(8)

z = 4xt2x2 + x3x4 max

Перепишем систему (8) в матричном виде:

Ax = b z = c>x—>max

(9)

Пусть хв =(xj х4)т - базисные переменные, a xF =(х2

х3) - свободные, при

этом обязательно, чтобы выполнялось условие det Ag ?*. 0.

AgXB + ApxF = b;

  • 4Yx2W2^
  • -1Ахз7

z = c• x = cRxR + cFx •

D O Г Г 7

( x A

z = (4 -1) 1 +(-2 lxJ

Выразим базисные переменные через свободные

AB-xB=b-AP-xF; хв = ДДЬ-АрХр)

4Y4

M-JY4 4xJ 10^-3

  • 4YXY
  • -Vlx3>

' 1,4 "

,-0,3,

' 0

,-0,5

  • -1,4V xV
  • 1,3 Дх-J
  • (10)

Учитывая неотрицательность переменных, из последнего выражения получим новую систему ограничительных неравенств относительно только свободных переменных

1,4 —1,4х3>0 [хз-1

< или <

-0,3-0,5х2 + 1,Зх3 >0 [-5х2+13х3>3

Подставив выражения (10) в целевую функцию (9), выразим ее также только через xF =(х2 х3)т

z СвАвЬ + (ср свАв А7) У

  • ( 1,4-1,4х3 "
  • (-2

ч-0,3-0, 5х2 +1,Зх3>

z = 5,9-1,5х2-5,9х3 —>шах (11)

Таким образом, исходная задача ЛП многих переменных сведена к задаче двух переменных

х3 < 1

<

—5х2 + 13х3 > 3

z = 5,9-1,2 -5,9х3 max, геометрическая интерпретация решения которой представлена на рисунке 8.

Согласно рисунку целевая функция принимает максимальное значение в точке А с координатами (0;0,23):

L2 = 0 -5х2 + 13х3=3 х3 =3/13 = 0,23

х2 = 0 I х2 = 0 I х2 = 0

Максимальное значение целевой функции

z = 5,9-5,9-0,23 «4,54.

Для отыскания оптимального плана исходной задачи подставляем в преобразованную систему (10) х2, х3.

Окончательно получаем хт =(1,078; 0; 0,23; 0,001).

Геометрическая интерпретация решения ЗЛП с п>2

Рисунок 8. Геометрическая интерпретация решения ЗЛП с п>2

Введение в симплекс-метод решения ЗЛП

Симплекс - простейший, выпуклый многогранник. На плоскости это треугольник, в пространстве - тетраэдр и т.д.

Графический метод решения ЗЛП имеет существенное ограничение по числу варьируемых переменных (свободных переменных в канонической системе ограничений). Таких переменных должно быть не более двух, чтобы имелась возможность рассматривать задачу на плоскости.

Симплекс-метод призван снять это ограничение.

Пусть требуется найти максимум целевой функции:

F =с1х12Хз +... + cnxn —>тах, (12)

а система ограничений содержит ш неравенств относительно п переменныхa11x1 + a12x2 + ... + a,„x111

a21Xl "*? а22Х2 +•••+ a2nXn — ^2 ........................... (13)

а .х + am9x? +... + amnx

xl...„

Добавив m неотрицательных переменных xn+1 >0,...,xn+in >0 по числу неравенств, приведем задачу к каноническому виду

a11x1+a12x2 + ... + alnxn + xn+1=b1

a21x1+a22x2 + ... + a2nxn + xn+2=b2

........................... (14) amlx + am?x? +... + axn + xn = b

V. ml 1 m2 z mn n n+m m

Xi . m > 0 l...n+т

Всего получается n+m переменных. Задача в этом случае принимает простейший матричный вид

Fmax=c-X’ где с=(с, с2 ... с„ 0п+1 ... 0п+ю); (15)

xi...n+m^°-

Основные положения ЛП для случая п переменных

  • — ОДР ЗЛП представляет собой выпуклое множество - многогранник в п-мерном пространстве (п - количество исходных переменных).
  • — Если ЗЛП имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений (ОДР).
  • Угловая точка многогранника в п-мерном пространстве является точкой пересечения п различных гиперплоскостей, каждая из которых задается одним уравнением системы ограничений (14) — в точности, как три плоскости образуют трехмерный угол.
  • В угловой точке п переменных равны нулю - эти переменные называются свободными xF =0, а само решение относительно оставшихся ненулевых m переменных хв > 0- базисным.
  • — Отыскать оптимальное решение можно перебором всех базисных допустимых (хп+1 п+гп >0) решений - угловых точек многогранника, вычисляя в них значение целевой функции z и выбирая наилучшее.
  • (п + т)!

Всего угловых точек достаточно много Cn+m = -----—, при этом лишь

n!m!

часть из них принадлежат многограннику допустимых решений.

Очевидно, что метод простого перебора - не самый лучший.

Симплекс-метод представляет собой алгоритм, по которому из некоторой начальной допустимой угловой точки многогранника осуществляется переход в соседний угол вдоль одного из п ребер.

Дж. Данциг предложил двигаться вдоль того ребра, которое гарантирует увеличение значения целевой функции. Постепенно двигаясь, достигнем особого угла, для которого уже все направления станут недопустимыми, a z примет оптимальное значение.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >