Теоретические основы оптимизации по симплекс-методу

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

Каждое из линейных неравенств на переменные ограничивает полупространство в соответственном линейном пространстве. В итоге все неравенства ограничивают некий полиэдр (может Теоретические основы оптимизации по симплекс-методу быть, нескончаемый), именуемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (либо минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задачка приобретает последующую формулировку — требуется отыскать такое наибольшее c, что гиперплоскость L(c) пересекает полиэдр хотя бы в одной точке. Скрещение Теоретические основы оптимизации по симплекс-методу хорошей гиперплоскости и полиэдра будет содержать хотя бы одну верхушку, причём, их будет более одной, если скрещение содержит ребро либо k-мерную грань. Потому максимум функционала можно находить в верхушках полиэдра

Метод решения Симплекс-методом оптимизационной задачки линейного программирования осуществляется оковём перебора вершин выпуклого полиэдра в многомерном Теоретические основы оптимизации по симплекс-методу пространстве. Методика линейного программирования была разработана Д. Данцигом в 1947 году.

Мысль симплекс-метода заключается в том, что выбирается одна из вершин полиэдра, после этого начинается движение по его рёбрам от верхушки к верхушке в сторону роста значения функционала. Когда переход по ребру из текущей верхушки в другую верхушку с более высочайшим Теоретические основы оптимизации по симплекс-методу значением функционала неосуществим, считается, что среднее значение c найдено.

Последовательность вычислений симплекс-методом можно поделить на два шага:

1) нахождение начальной верхушки огромного количества допустимых решений,

2) поочередный переход от одной верхушки к другой, ведущий к оптимизации значения мотивированной функции.

При всем этом в неких случаях начальное решение разумеется либо его определение Теоретические основы оптимизации по симплекс-методу не просит сложных вычислений, к примеру, когда все ограничения представлены неравенствами вида «меньше либо равно» (тогда нулевой вектор однозначно является допустимым решением, хотя и, не всегда, далековато не хорошим).

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

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

В качестве задачки многомерной Теоретические основы оптимизации по симплекс-методу оптимизации будем рассматривать задачку линейного программирования в канонической форме:

, (2.1)

, (2.2)

, (2.3)

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

Имеем независящих переменных, которые назовем свободными, другие – зависимые либо базовые. Выразим базовые переменные через свободные:

, , (2.4)

где – составляющие вектора после простых преобразований матрицы . Формула (2.4) является решением системы Теоретические основы оптимизации по симплекс-методу уравнений (2.2). При всем этом, если , тогда – базовое решение задачки (2.1)-(2.3), если все , .

Будем считать, что , тогда каждому выбору базовых переменных системы (2.2) соответствует свое базовое решение. Потому число базовых решений равно числу различных базовых миноров матрицы , но не превосходит .

Допустим огромное количество задачки (2.1)-(2.3) представляет собой выпуклый полиэдр в пространстве . И всякую его внутреннюю Теоретические основы оптимизации по симплекс-методу точку можно представить в виде линейной композиции угловых точек огромного количества :

, . (2.5)

Аксиома 1. Базовое решение задачки (2.1)-(2.3) является угловой точкой области допустимых решений .

Аксиома 2. Об рациональном решении. Пусть – огромное количество допустимых решений не пустое ограниченное огромное количество. Тогда существует среднее решение задачки (2.1)-(2.3) и оно достигается в одной из угловых точек Теоретические основы оптимизации по симплекс-методу огромного количества допустимых решений.


teoreticheskie-i-metodicheskie-osnovi-rascheta-effektivnosti-sistemi-upravleniya-personalom-predpriyatiya.html
teoreticheskie-i-metodologicheskie-osnovi-formirovaniya-i-realizacii-eksportnogo-potenciala-promishlennih-predpriyatij-stranica-2.html
teoreticheskie-i-metodologicheskie-problemi-istochnikovedeniya.html