Симплексный метод решения задачи линейного программирования — КиберПедия 

История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...

Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...

Симплексный метод решения задачи линейного программирования

2017-10-16 618
Симплексный метод решения задачи линейного программирования 0.00 из 5.00 0 оценок
Заказать работу

Построение опорных планов.Доказано, что оптимальное решение задачи линейного программирования связано с угловыми точками многогранника решений, т. е. с опорными планами, каждый из которых определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2,..., Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Сnm. При больших m и n найти оптимальный план, перебирая все опорные планы задачи, очень трудно. Поэтому необходимо иметь схему, позволяющую осуществлять упорядоченный переход от одного опорного плана к другому. Такой схемой является симплексный метод, который позволяет, исходя из известного опорного плана задачи, за конечное число шагов получить ее оптимальный план. Каждый из шагов (или итераций) состоит в нахождении нового плана, которому соответствует меньшее значение линейной функции, чем значение этой же функции в предыдущем плане. Процесс продолжают до получения оптимального плана. Если задача не обладает планами или ее линейная функция не ограничена на многограннике решений, то симплексный метод позволяет установить это в процессе решения.

1. Построение опорных планов

Пусть поставлена задача линейного программирования.

Найти минимальное значение функции Z = C1x1 + C2x2 + … + Cnxn при ограничениях:

   


где bi і 0 (I=1,2,…,m).

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

(1.11)

При ограничениях:

 

(1.12)
(1.13)

 

Запишем систему в векторной форме:

(1.14)

 

где


 

Векторы А1, А2, …, Аm – линейно независимые единичные векторы m-мерного пространства. Они и образуют базис этого пространства. Поэтому в разложении (1.14) за базисные неизвестные выбираем х1, х2,..., хm, свободные неизвестные хm+1,..., хn приравниваем нулю и, учитывая, что bi і 0 (i=1,2,…,m), а векторы А1, А2,..., Аm – единичные, получаем первоначальный план:

Плану соответствует разложение

(1.15)

где векторы А12,…,Аm линейно независимы, следовательно, построенный первоначальный план является и опорным.

Рассмотрим, как, исходя из первоначального опорного плана, можно построить второй опорный план. Векторы А12,…,Аm образуют базис в m-мерном пространстве, поэтому каждый из данных векторов соотношения можно разложить по векторам базиса, причем единственным образом:

Предположим, что для некоторого вектора, не входящего в базис, например для вектора Аm+1, является положительным хотя бы один из коэффициентов хi,m+1 в разложении

(1.16)

Зададимся некоторой величиной q > 0 (пока неизвестной), умножим на нее обе части равенства (1.16) и вычтем результат почленно из равенства (1.15). Получаем

Таким образом, вектор

является планом, если его компоненты неотрицательны.

Так как q>0, то все компоненты вектора Х1, в которые входят неположительные xi,m+1, неотрицательны. Поэтому надо рассмотреть только компоненты, включающие положительные хi,m+1 (i=1, 2,...,m), т. е. необходимо определить такое q>0, при котором для всех хi, m+1і0.

Из неравенства хi-q xi,m+1і0 получаем qЈxi/xi,m+1, следовательно, вектор xi является планом задачи для любого q, удовлетворяющего условию

(1.17)

где минимум берется по i, для которых xi,m+1>0.

Опорный план не может содержать (m + 1) положительных компонент, поэтому в плане Х1 необходимо обратить в нуль по крайней мере одну из компонент. Положим в (1.17), что

тогда компонента плана X1, для которой достигается минимум, обращается в нуль. Пусть эта компонента стоит на первом месте, т. е.

Подставляя значение q0 в (7), получаем разложение

которому, соответствует новый опорный план:

где хi' = xi - q0xi,m+1 (i = 2, 3,..., m), х'm+1 = q0.

Исключение одного вектора из базиса и включение вместо него другого с помощью q0 соответствуют переходу от одного базиса к другому с помощью метода Жордана – Гаусса, поэтому система векторов А2, А3,…, Аm, Аm+1 линейно независима и является новым базисом.

Для определения следующего опорного плана необходимо любой вектор, не входящий в базис А2, А3,..., Аm, Аm+1, разложить по векторам этого базиса, а затем определить такое q0 > 0, при котором исключался бы один из векторов этого базиса.

Таким образом, процесс получения новых опорных планов заключается в выборе вектора, который подлежит включению в базис, и определении вектора, подлежащего исключению из базиса. Критерий, используемый для определения вектора, который включается в базис, является одним из основных элементов симплексного метода. Заметим, что если вектор Аm+1 подлежит включению в базис, а в его разложении все xi,m+1Ј0, то, очевидно, нельзя выбрать такое q > 0, которое исключало бы один из векторов разложения. В этом случае план Х1 содержит m + 1 положительных компонент, а система векторов А1, А2, А3,..., Аm, Аm+1 является линейно зависимой и определяет не угловую, а внутреннюю точку многогранника решений, в которой линейная функция не может достигать минимального значения. Это указывает на то, что гиперплоскость, соответствующая линейной функции, не может стать опорной к многограннику решений, как бы далеко ни перемещать ее в направлении, обратном вектору N, т. е. линейная функция не ограничена на многограннике решений.

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

 

1.4. Отыскание оптимального плана. Условия оптимальности

Предположим, что задача линейного программирования (1.11)-(1.13) обладает планами и каждый ее опорный план невырожден. В этом случае для опорного плана (1.15) имеем:

где все Xi > О, а Z (Хо) - значение линейной функции, соответствующее этому плану.

Разложение любого вектора Аj по векторам данного базиса А1, А2,..., Аm единственное:

поэтому разложению вектора Аj в базисе соответствует и единственное значение линейной функции

где Zj – значение линейной функции, если в нее вместо неизвестных подставить соответствующие коэффициенты разложения j-го вектора по векторам базиса.

Обозначим через Cj коэффициент в линейной функции, соответствующий вектору Аj. Тогда справедлива следующая теорема:

Если для некоторого вектора Aj выполняется условие Zj-Cj>0, то план Х0 не является оптимальным, и можно построить такой план X, для которого выполняется неравенство Z(Х) < Z(X0).

Доказательство. Умножая на q>0 и вычитая результаты соответственно, получим:

(1.18)
   
(1.19)

 

В соотношении (1.19) к обеим частям прибавлена величина qCj для j = 1, 2,..., n. В (11) x1, х2,..., хm положительны, поэтому всегда можно выбрать такое q > 0, чтобы все коэффициенты при векторах А1, А2,..., Аm, Аj были неотрицательными, т. е. получить новый план задачи: X = (х1 - qх1j, х2 - qх2j,..., хm - qхmj, q, 0,…, 0) которому согласно соответствует значение линейной функции

(1.20)

Так как по условию теоремы Zj-Cj>0 и q > 0, то

Z(X)<Z(X0).

С л е д с т в и е. Если для некоторого плана Х0 разложения всех векторов Аj (j=1, 2,..., n) в данном базисе удовлетворяют условию

Zj-Cj Ј 0 (1.21)

то план Х0 является оптимальным.

Неравенства (1.21) являются условием оптимальности плана задачи, решаемой на отыскание минимального значения линейной функции, а значения Zj-Cj называются оценками плана.

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

Для задачи линейного программирования (1.11)-(1.13), заключающейся в отыскании максимального значения линейной функции, справедлива следующая теорема:

Если для некоторого вектора Аj выполняется условие Zj-Cj < 0, то план Х0 не является оптимальным и можно построить такой план X, для которого выполняется условие Z(X) > Z(X0).

Доказательство аналогично доказательству предыдущей теоремы.

С л е д с т в и е. Если для некоторого плана Х0 разложения всех векторов Аj (j=1, 2,...,n) в данном базисе удовлетворяют условию

Zj-Cj і 0 (1.22)

то план Х0 является оптимальным.

Неравенства (1.22) являются условием оптимальности плана задачи на отыскание максимального значения линейной функции.

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

 


Поделиться с друзьями:

Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.019 с.