Файл: Падалко Л.П. Математические методы оптимального планирования развития и эксплуатации энергосистем учеб. пособие.pdf

Глава I

Л И Н Е Й Н О Е П Р О Г Р А М М И Р О В А Н И Е

З а д а ч а линейного программирования формулируется следующим образом: требуется найти значения п пере­

ского метода означает здесь то, что целевая функция и ограничения задачи находятся в линейной зависимости от переменных.

§ 1.1. Геометрическая интерпретация задачи линейного программирования

Рассмотрим геометрическую интерпретацию на кон­ кретном числовом примере. Пусть рассматривается за­ д а ч а :

max {2х1 + 3*,};

16

Система ограничении рассматриваемой задачи обра­ зует область допустимых решений, среди которых требу­

соответствующие этим уравнениям . Область допустимых решений д л я к а ж д о г о из неравенств находится по одну сторону прямой, соответствующей уравнению. Пересече­

стеме ограничений задачи .

К а к видно, число допустимых решений равно бесчис­ ленному множеству. Понятно, что решение задачи на ос­ нове прямого перебора крайне неэффективно и для за­ дач с большим числом переменных практически нереали-

з у е мо д а ж е при использовании самых быстродействую­ щих вычислительных машин . Необходим такой метод ре­ шения, который, не перебирая всех вариантов, позволял бы отыскивать оптимальное решение. Такие методы, ос­ нованные на целенаправленном переборе ограниченного числа вариантов, и составляют содержание линейного программирования .

венстве решение этой системы однозначно, и, следователь­

соответствует для двумерного пространства прямой, для трехмерного — плоскости и для многомерного — гипер­ плоскости. Пересечение этих плоскостей определяет гео­ метрическое место точек, удовлетворяющих системе ог­ раничений, т. е. область допустимых решений, внутри ко­ торой отыскивается оптимальное решение.

П р и д а д и м целевой функции какое-либо произвольное

раллельно самой себе в сторону увеличения функции, мы

Аналогичную наглядную геометрическую интерпрета­ цию можно д а т ь и д л я задачи с тремя .переменными. В этом случае многогранник будет определять пространство допустимых решений, а геометрическое место точек, в ко ­ торых целевая функция приобретает одинаковое значе­ ние, располагается на плоскости.

18

И з приведенной геометрической интерпретации видно, что оптимальное решение достигается в вершине много­

П р и числе переменных более трех д а т ь аналогичное наглядное геометрическое истолкование не представля ­

ременных. П р и этом многогранником допустимых реше­ ний будет являться /г-мерное пространство, границы ко­ торого определяются гиперплоскостями, и оптимальное решение, т а к ж е как и в предыдущих случаях, достига­ ется в вершине многогранника.

§ 1.2. Симплексный метод

Геометрическая интерпретация з а д а ч линейного про­ граммирования может быть использована д л я обосно­ вания численного метода решения этих задач . Использо ­

равенствам осуществляется путем введения дополнитель­ ных переменных. Например, из неравенства

п

с помощью дополнительной переменной х п + \ получают следующее равенство:

п

i=i

И д е ю вычислительной схемы симплексного метода поясним для рассмотренной ранее задачи с двумя пере­ менными. После сведения задачи к канонической форме получим:

max {2хх + Зх 2 };