Общая задача линейного программирования (ОЗЛП) формулируется следующим образом – найти переменные задачи x 1 , x 2 , ..., x n , которые обеспечивают экстремум целевой функции
Допустимым решением (планом) задачи линейного программирования (ЗЛП) называется любой n -мерный вектор X =(x 1 , x 2 , ..., x n), удовлетворяющий системе ограничений равенств и неравенств. Множество допустимых решений задачи образует область допустимых решений D .
Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение, при котором целевая функция Z (X ) достигает экстремума.
Каноническая задача линейного программирования (КЗЛП) имеет вид
(1.2)
Она отличается от ОЗЛП тем, что её система ограничений является системой только уравнений и все переменные неотрицательные.
Приведение ОЗЛП к каноническому виду ЗЛП:
Чтобы заменить исходную задачу минимизации на задачу максимизации (или наоборот задачу максимизации на задачу минимизации) достаточно целевую функцию умножить на «-1» и искать максимум (минимум) полученной функции;
Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных x n +1 ≥ 0 они преобразуются в равенства:
неравенство a i 1 x 1 +…+a in x n ≥ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ,
неравенство a i 1 x 1 +…+a in x n ≤ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ;
Если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательны-ми переменными: x k = x " k – x ” k , где x " k ≥ 0. x ” k ≥ 0.
Графический метод решения ЗЛП с двумя неизвестными
ЗЛП с двумя неизвестными имеет вид:
Метод основан на возможности графического изображения области допустимых решений и нахождении среди них оптимального решения.
Область допустимых решений (ОДР) задачи является выпуклым многоугольником и строится как пересечение (общая часть) областей решений каждого из неравенств ограничений задачи.
Областью решения неравенства a i 1 x 1 +a i 2 x 2 ≤ b i является одна из двух полуплоскостей, на которые прямая a i 1 x 1 +a i 2 x 2 = b i , соответствующая этому неравенству, делит координатную плоскость. Чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на разделяющей прямой подставить в неравенство:
Если неравенство справедливо, то областью решений является полуплоскость, содержащая эту точку;
Если неравенство не справедливо, то областью решений является полуплоскость, не содержащая эту точку.
Для нахождения среди допустимых решений оптимального используются линии уровня.
Линией уровня называется прямая с 1 x 1 +с 2 x 2 = l , где l = const, на которой целевая функция задачи принимает постоянное значение. Все линии уровня параллельны между собой.
Градиент целевой функции grad Z (X ) задает вектор нормали C = (c 1 , c 2) линий уровня. Целевая функция на линиях уровня возрастает, если линии уровня перемещать в направлении их нормали, и убывает – в противоположном направлении.
Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с ОДР и по отношению к которой ОДР находится в одной из полуплоскостей. ОДР задачи имеет не более двух опорных прямых.
Оптимальное решение ЗЛП лежит на опорной прямой в угловой точке многоугольника ОДР. ЗЛП имеет единственное решение, если опорная прямая проходит через одну угловую точку ОДР, бесконечное множество решений, если опорная прямая проходит через ребро многоугольника ОДР. ЗЛП не имеет решения, если ОДР является пустым множеством (когда система ограничений несовместна) и если ОДР неограниченна в направлении экстремума (целевая функция неограниченна).
Алгоритм графического метода решения ЗЛП с двумя неизвестными:
Построить ОДР.
Построить вектор нормали C = (c 1 , c 2) и линию уровня с 1 x 1 +с 2 x 2 = 0, проходящую через начало координат и перпендикулярную вектору С .
Передвигать линию уровня до опорной прямой в направлении вектора С в задаче на max, или в противоположном направлении – в задаче на min.
Если при перемещении линии уровня в направлении экстремума ОДР уходит в бесконечность, то ЗЛП не имеет решения ввиду неограниченности целевой функции.
Если ЗЛП имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих ОДР и имеющих общие точки с опорной прямой. Если экстремум достигается в двух угловых точках, то ЗЛП имеет бесконечное множество решений, принадлежащих ребру ОДР, ограниченному этими угловыми точками. В данном случае вычисляются координаты обеих угловых точек.
Вычислить значение целевой функции в точке экстремума.
Симплекс-метод решения ЗЛП
Симплекс-метод основывается на следующих положениях:
ОДР задачи линейного программирования является выпуклым множеством с конечным числом угловых точек;
Оптимальным решением ЗЛП является одна из угловых точек ОДР. Угловые точки ОДР алгебраически представляют некоторые базисные (опорные) решения системы ограничений ЗЛП.
Базисным (опорным) решением ЗЛП называется такое допустимое решение X 0 =( x 10 , x 20 , ..., x m 0 , 0,…0), для которого векторы условий (столбцы коэффициентов при неизвестных в системе ограничений) линейно независимы.
Ненулевые координаты x 10 , x 20 , ..., x m 0 решения X 0 называются базисными переменными, оставшиеся координаты решения X 0 - свободными переменными. Число отличных от нуля координат опорного решения не может быть больше ранга r системы ограничений ЗЛП (числа линейно независимых уравнений в системе ограничений ЗЛП). Далее считаем, что система ограничений ЗЛП состоит из линейно независимых уравнений, т.е. r = m .
Смысл симплекс-метода заключается в целенаправленном переходе от одного опорного решения ЗЛП к другому (т.е. от одной угловой точки ОДР к другой) в направлении экстремума и состоит в последовательности этапов:
Найти начальное опорное решение;
Осуществить переход от одного опорного решения к другому;
Определить критерий достижения оптимального решения или сделать заключение об отсутствии решения.
Алгоритм выполнения Симплекс-метода ЗЛП
Алгоритм симплекс-метода осуществляет переход от одного опорного решения ЗЛП к другому в направлении экстремума целевой функции.
Пусть ЗЛП задана в каноническом виде (1.2) и выполнено условие
b i ≥ 0, i =1,2,…,m , (1.3)
соотношение (1.3) всегда можно выполнить, домножив соответствующее уравнение на «-1» в случае отрицательности b i . Также считаем, что система уравнений в ограничениях задачи (1.2) линейно независима и имеет ранг r = m . При этом вектор опорного решения имеет m ненулевых координат.
Пусть исходная задача (1.2), (1.3) приведена к виду, где базисные переменные x 1 , x 2 , ..., x m выражены через свободные переменные x m + 1 , x m + 2 , ..., x n
(1.4)
На основе этих соотношений построим таблицу 1
Таблица 1.
Таблица 1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменениями содержания этой таблицы.
Алгоритм с имплекс-метода :
1. В последней строке Z симплекс-таблицы в задаче на min находят наименьший положительный элемент (в задаче на max - наименьший отрицательный элемент), не считая свободного члена. Столбец, ответствующий этому элементу, называется разрешающим.
2. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс - отношений, оно соответствует разрешающей строке.
3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.
4. Если имеется несколько одинаковых по величине симплекс - отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симлекс - таблицы.
5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс - таблица преобразуется следующим образом (таблица 2):
Таблица 2
6. Элемент таблицы 2, соответствующий разрешающему элементу таблицы 1, равен обратной величине разрешающего элемента.
7. Элементы строки таблицы 2, соответствующие элементам разрешающей строки таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент.
8. Элементы столбца таблицы 2, соответствующие элементам разрешающего столбца таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент и берутся с противоположным знаком.
9. Остальные элементы вычисляются по правилу прямоугольника : мысленно вычерчиваем прямоугольник в таблице 1, одна вершина которого совпадает с разрешающим элементом (Рэ), а другая – с элементом, который мы ищем; обозначим элемент в новой таблице 2 через (Нэ), а элемент, стоящий на этом же месте в старой таблице 1 – через (Сэ). Остальные две вершины А и В дополняют фигуру до прямоугольника. Тогда искомый элемент Нэ из таблицы 2 равен Нэ = Сэ – А*В/Рэ.
10. Критерий оптимальности. Как только получится таблица, у которой в последней строке в задаче на min все элементы отрицательны (в задаче на max все элементы положительны), считается, что экстремум найден. Оптимальное значение целевой функции равно свободному члену в строке Z, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные полагаются равными нулю.
11.Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).
Метод искусственного базиса решения ЗЛП
Алгоритм симплекс-метода применим, если выделено какое-либо опорное решение ЗЛП, т. е, исходная ЗЛП (1.2) приведена к виду (1.4). Метод искусственного базиса предлагает процедуру построения такого опорного решения.
Метод искусственного базисаоснован на введении искусственных базисных переменных y 1 , y 2 ,…, y m , с помощью которых система ограничений ЗЛП (2.2)
(1.5)
может быть преобразована к виду
(1.6)
Системы (1.5) и (1.6) будут эквивалентны в том случае, если все y i будут равны нулю. Как и раньше мы считаем, что все b i ≥ 0. Для того чтобы у i были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные базисные переменные y i перешли в свободные переменные. Такой переход можно сделать алгоритмом симплекс метода относительно дополнительной целевой функции
F (y ) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)
Исходная симплекс таблица для данного метода имеет вид
Сначала симплекс таблица преобразуется относительно целевой функции F (y ) до получения опорного решения. Опорное решение найдено, когда выполнен следующий критерий: F (y ) = 0 и все искусственные переменные у i переведены в свободные переменные. Затем из симплекс таблицы вычеркивается строка для F (y ) и столбцы для у i и решают задачу для исходной целевой функции Z (x ) до получения оптимального решения.
Задача линейного программирования (ЗЛП) − это задача нахождения наибольшего (или наименьшего) значения линейной функции на выпуклом многогранном множестве.
Симплекс метод − это метод решения задачи линейного программирования. Суть метода заключается в нахождении начального допустимого плана, и в последующем улучшении плана до достижения максимального (или минимального) значения целевой функции в данном выпуклом многогранном множестве или выяснения неразрешимости задачи.
Рассмотрим следующую задачу линейного программирования в канонической форме:
| (1) |
| (2) |
| (3) |
Метод искусственного базиса
Как было паказано выше, для задачи, записанной в канонической форме, если среди векторов столбцов матрицы A есть m единичных и линейно независимых , можно непосредственно указать опорный план. Однако для многих задач линейного программирования, записанных в канонической форме и имеющих опорные планы, среди векторов столбцов матрицы A не всегда есть m единичных и линейно независимых. Рассмотрим такую задачу:
Пусть требуется найти максимум функции
при условиях
где первы n
элементы нули. Переменные 
называются искусственными
. Векторы столбцы
  | (28) |
образуют так называемый искусственный базис m -мерного векторного пространства.
Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом.
Теорема 4.
Если в оптимальном плане 
расширенной задачи (24)−(26) значения искусственных переменных 
, то 
является оптимальным планом задачи (21)−(23).
Таким образом, если в найденном оптимальном плане расширенной задачи, значения искусственных переменных равны нулю, то получен оптимальный план исходной задачи. Остановимся более подробно на нахождении решения расширенной задачи.
Значение целевой функции при опорном плане (27):
Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M , а другая − нет.
После вычисления F(X) и их значения, а также исходные данные расширенной задачи заносят в симплекс таблицу, как было показано выше. Разность заключается лишь в том, что данная таблица содержит на одну строку больше, чем обычная симплекс таблица. При этом в (m +1)-ю строку помещают коэффициенты, не содержащие M , а в (m +2)-ю строку − коэффициенты при M .
При переходе от одного опорного плана к другому, в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m +2) строки. Искусственный вектор, исключенный из базиса не имеет смысла вновь ввести в базис. При переходе к другому опорному плану, может случится так, что ни один из искусственных векторов из базиса не будет исключен. Пересчет симплекс таблицы при переходе от одного опорного плана к другому производят по обычным правилам симплекс метода (смотри выше).
Итерационный процесс ведут по m
+2 строке до тех пор, пока элементы m
+2 строки, соответствующие переменным 
не станут неотрицательными. При этом, если искусственные переменные исключены из базиса, то найденный план расширенной задачи отвечает некоторому опорному плану исходной задачи.
m +2 строки, столбца x 0 отрицателен, то исходная задача не имеет решения.
Если же не все искусственные переменные исключены из базиса и элемент m +2 строки, столбца x 0 равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.
Если исходная задача содержит несколько единичных векторов, то их следует включить в искусственный базис.
Если в ходе итераций m +2 строка больше не содержит отрицательных элементов, то итерационный процесс продолжают с m +1 строкой, до тех пор, пока не найден оптимальный план расширенной задачи или не выявлен неразрешимость задачи.
Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:
- Составляют расширенную задачу (24)−(26).
- Находят опорный план расширенной задачи.
- Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
- Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.
Для решения задач линейного программирования онлайн, пользуйтесь калькулятором
Данному случаю соответствует взаимная противоречивость ограничений, входящих в задачу.
2) Допустимое множество - выпуклый ограниченный многогранник.
Допустимое множество - выпуклое неограниченное многогранное множество.
Два последних случая достаточно легко представить в двух- или трехмерном измерении. В пространстве большей размерности понятие многогранника (многогранного множества) вводится абстрактно как пересечение гиперплоскостей и гиперполуплоскостей, определяемых соответствующими линейными уравнениями и неравенствами, входящими в состав ограничений задачи. Характерным свойством многогранника является наличие в нем особых точек - вершин .
Возможные случаи оптимальных решений (планов) задачи линейного программирования.
1) Задача не имеет оптимальных решений .
Данный случай может возникнуть: либо тогда, когда допустимое множество решений пусто ("не из чего выбирать" оптимальный план),
либо когда допустимое множество представляет собой неограниченное многогранное множество, и целевая функция на нем неограниченно возрастает (если L max) или неограниченно убывает (при L min).
2) Задача имеет единственное решение (единственный оптимальный план).
Это решение обязательно совпадает с одной из вершин допустимого множества.
3) Задача имеет бесконечное множество оптимальных решений, заданное некоторым линейным образованием - ребром, гранью, гипергранью и т.д. Среди точек этого линейного образования имеются и вершины допустимого множества.
Таким образом, основное утверждение теории линейного программирования, в конечном итоге определяющее специфические способы его решения, можно сформулировать следующим образом:
Если задача линейного программирования имеет хотя бы один оптимальный план, то его следует искать среди вершин допустимого множества решений.
В следующем параграфе рассмотренные общие положения будут проиллюстрированы на примере задачи линейного программирования с двумя переменными.
Графоаналитический способ решения задач линейного программирования
Графоаналитический (графический) способ решения задач линейного программирования обычно используется для решения задач с двумя переменными, когда ограничения выражены неравенствами, а также задач, которые могут быть сведены к таким задачам.
Пусть задача линейного программирования имеет вид:
(1.7)
где с 1 , с 2 , а i 1 , а i 2 , b i - заданные действительные числа; знаки в неравенствах произвольны; целевая функция либо максимизируется, либо минимизируется.
Каждое из
неравенств (1.7) системы ограничений
задачи геометрически определяет
полуплоскость соответственно с граничными
прямыми
;i
=1,…,m
.
В том случае, если система неравенств
(1.7) совместна, допустимая область решений
задачи есть множество точек, принадлежащих
всем указанным полуплоскостям. Так как
множество точек пересечения данных
полуплоскостей – выпуклое, то областью
допустимых значений является выпуклое
множество, которое называютмногоугольником
решений. Стороны этого многоугольника
лежат на прямых, уравнения которых
получаются из исходной системы ограничений
заменой знаков неравенств на знаки
равенств.
Множеством допустимых решений для данной частной задачи может быть:
пустая область;
выпуклый многоугольник, включая вырожденные случаи - отрезок и единственную точку;
выпуклая многоугольная неограниченная область, включая вырожденные случаи - луч и прямую.
Практическая реализация решения задачи линейного программирования (1.6) – (1.7) на основе ее геометрической интерпретации включает следующие этапы:
1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (1.7) знаков неравенств на знаки равенств.
2. Найти полуплоскости, определяемые каждым из ограничений.
Соответствующая полуплоскость может быть найдена подстановкой в неравенство координат какой-нибудь «простой» точки - (0,0), (0,1) или (1,0). Главное - чтобы эта точка не принадлежала границе полуплоскости. Если после подстановки неравенство окажется справедливым, то выбирается та полуплоскость, где содержится эта точка. Если неравенство не справедлива, то выбирается альтернативная полуплоскость.
3. Определить многоугольник решений, как пересечение найденных полуплоскостей.
4.
Построить градиент целевой функции,
т.е. вектор
,
координатами которого служат
коэффициенты целевой функцииL
.
Этот вектор определяет направление наискорейшего возрастания целевой функции.
5. Построить ряд линий уровня целевой функцииL , т.е. прямых перпендикулярных градиентуL . При этом построение линий уровня следует вести в направлении градиента, если решается задача на максимум, и в противоположном направлении (в направлении «антиградиента»), если решается задача на минимум. В результате отмечается точка (точки), в которой линии уровня в последний раз касаются допустимого множества.
Если допустимое
множество неограниченно, то точки
последнего касания может и не быть.
Линии уровня уходят в бесконечность,
соответственно значение
или
,
и задача не имеет оптимальных планов.
Определить координаты отмеченной точки аналитически, решая соответствующую систему линейных уравнений. Затем вычислить значение целевой функции в этой точке. Тем самым, определяется оптимальный план и оптимальное значение целевой функции задачи.
Заканчивая рассмотрение геометрической интерпретации задачи (1.6) – (1.7), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1.1 – 1.3. Рис. 1.1 характеризует такой случай, когда целевая функция принимает оптимальное значение в единственной точке А, одной из вершин допустимого множества. На рис. 1.2 оптимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 1.3 изображен случай, когда оптимальное значение целевой функции недостижимо.
Рис. 1.1. Оптимум функции L достижим в точке А
Рис.
1.2. Оптимум функцииL
достигается в любой точке отрезка
АB
Рис. 1.3. Оптимум функции L недостижим
Симплексный метод является универсальным экономико-мате-
матическим методом. Для его использования условия задачи необходимо представить в виде уравнений и неравенств, количественно описывающих особенности функционирования изучаемого объекта.
Существенным достоинством метода является его универсальность, т. е. возможность использования для решения любых задач, условия которых записаны в виде системы уравнений и неравенств. Наряду с этим симплекс-метод обладает тем достоинством, что при приближении полупространства, выражающего целевую функцию, к экстремальной крайней угловой точке, он позволяет пропускать целый ряд промежуточных крайних угловых точек.
Метод получил свое название из геометрической интерпретации условий задачи. Они позволяют получить многогранник решений или симплекс, крайняя угловая точка которого, будучи равна значениям переменных, превращает функцию в максимум или минимум.
Имеется несколько вариантов алгоритма симплекс-метода: обычный, m -метод (искусственного базиса) и др.
Рассмотрим вариант, позволяющий осуществлять наиболее
простые вычисления.
Алгоритм симплекс-метода включает несколько этапов:
1) подготовка информации (включает введение переменных
и формирование ограничений);
2) преобразование ограничений и запись их в матрицу;
3) поиск опорного решения;
4) поиск оптимального решения.
К примеру, имеем следующую экономико-математическую
задачу:
Преобразование ограничений связано, в первую очередь, с превращением неравенств в уравнения. Если при этом ограничения приведены к типу , то процедура вычислений значительно
упрощается. Для этого ограничения типа умножим на (-1).
Превращение неравенств в уравнения связано с введением
дополнительных переменных. В ограничениях типа дополнительные переменные обозначают величину недоиспользования
ресурсов, в ограничениях типа - величину превышения ресурсов над минимумом потребности в них.
В уравнения дополнительные переменные не вводятся (или вводятся равными нулю):
При этом всякое решение осуществляется из допущения, что
Решение получаем поиском опорного и оптимального решений.
Опорное решение получим при значениях переменных, когда ограничения задачи выполняются. Признаком выполнения ограничений является отсутствие 0-значений среди базисных переменных и отрицательных свободных членов.
При этом переменные, исходя из значений которых начинаем решение, будут базисными.
В первой симплексной таблице (таблица 5.1) такими базисными будут дополнительные переменные, т. е. вектор дополнительных переменных. Остальные переменные, обозначающие вектор-столбцы, будут небазисными. В таблице 5.1 небазисными будут основные переменные.
Таблица 5.1 - Симплексная таблица № 1
| Базисные переменные | Свободные члены | Небазисные переменные | ||||
| … | ||||||
| … | ||||||
| … | ||||||
| … | ||||||
| ……………………………………………… | ||||||
| … | ||||||
| … |
Если в столбце дополнительных переменных есть 0, то это свидетельствует об искаженности базиса, т. е. отсутствии опорного решения. Таким образом, полученная запись при свидетельствует, что базисное решение отсутствует по двум признакам,
а именно:
– имеются отрицательные свободные члены;
– имеются 0-значения среди базисных переменных.
Всю информацию при допущении, что заносим в таблицу. Таблица 5.1 содержит т + 2строк (где т - число строк ограничений) и п + 2 столбцов (где п - число небазисных переменных).
Коэффициенты целевой функции в таблице 5.1 записываются
с противоположным знаком.
Нахождение опорного решения предполагает замену базисных переменных небазисными или поиск нового базиса. Чтобы исключить 0 с вектора базисных переменных необходимо в 0-строке найти такой коэффициент, от деления на который коэффициента А т
,получим наименьшее положительное частное. Для этого вектор-столбец свободных членов делим на соответствующие коэффициенты столбцов .
Допустим, что при делении
на коэффициенты первого столбца, т. е. отношение . Это означает, что требование не выполняется. В другом случае (при ) .
Допустим, что при делении отношение меньше всех других значений.
Тогда коэффициент можно принять за разрешающий.
Он указывает на то, что 0-значение и коэффициент поменяются местами. Эта замена означает, что целевая функция (или полупространство F
) переместилась параллельно самой себе и поэтому значение коэффициентов изменяется. Замена значений требует
вычислений, которые всегда осуществляются по одним и тем же правилам.
Для записи формул, по которым определяются коэффициенты новой симплексной таблицы (таблица 5.2), введем условные обозначения, в частности, - коэффициент, стоящий в строке i
и столбце j
. При этом F
-строка будет иметь значение i
+ 1, а столбец свободных членов j
= 0.
Таблица 5.2 - Симплексная таблица № 2
| Базисные переменные | Свободные члены, | Небазисные переменные | |||
| ………………………………………………………….. | |||||
Допустим, что коэффициент - разрешающий, т. е. стоит
в строке r
и столбце k
при .
При делении значений столбца свободных членов на соответствующие коэффициенты столбца k
частное от деления на было наименьшим.
Условимся, что коэффициент следующей таблицы будем обозначать со штрихом, т. е. .
Правила:
1. Новый коэффициент (вместо разрешающего) равен обратному от него, т. е. или в данном случае .
2. Новые коэффициенты столбца разрешающего элемента равны коэффициентам предыдущей таблицы, деленным на разрешающий коэффициент с противоположным значением:
т. е. в данном случае - при .
3. Новые коэффициенты строки разрешающего элемента равны коэффициентам предыдущей таблицы этой строки, деленным
на разрешающий коэффициент:
(при ) или , при .
4. Остальные коэффициенты, не стоящие в строке и столбце разрешающего элемента определяются по правилу прямоугольника, т. е. в числителе от произведения коэффициентов главной диагонали, среди которых находится разрешающий, вычитаем произведение побочной диагонали и результат делим на разрешающий коэффициент:
Перебросив 0-значения из базисных значений в небазисные, получим в n
-мерном пространстве т
независимых векторов. Затем вычеркиваем 0-столбец, который в дальнейших расчетах участия не принимает. Просматривая столбец свободных членов, находим среди них отрицательные члены. Чтобы получить опорное решение, превращаем отрицательные свободные члены в положительные. Для этого базисные переменные с отрицательными свободными членами необходимо перевести в небазисные. При этом делаем столько шагов (таблиц), сколько имеется отрицательных свободных членов. За основу принимаем любую строку с отрицательным свободным членом. Лучший вариантом является та строка, среди коэффициентов которой имеется больше единиц или целых чисел. Случается, что все свободные члены являются отрицательными
и им соответствуют отрицательные коэффициенты в каком-то из столбцов. В этом случае опорное решение можно получить за один шаг, взяв в качестве разрешающего коэффициента отрицательный коэффициент, от деления на который получается наибольшее положительное частное. Таким образом, за один шаг все отрицательные свободные члены будут превращены в положительные.
С точки зрения геометрической интерпретации (выпуклых множеств) это будет означать, что из мнимого многогранника решений мы переместились на реальный многогранник, но находимся
не в самой лучшей выпуклой угловой точке.
Чтобы найти разрешающий коэффициент, делим значения столбца свободных членов на соответствующие коэффициенты столбцов небазисных переменных.
Если , то получим меньшее значение, чем от деления других частных .
Допустим, что в данном случае частное - меньше всех других. Следовательно, коэффициент () является разре-
шающим.
Меняем местами и , после чегопроводим расчеты
по приведенным выше четырем правилам (таблица 5.3).
Таблица 5.3 - Симплексная таблица № 3
| Базисные переменные | Свободные члены | Небазисные переменные | ||
| ……………………………………………….. | ||||
В этой таблице содержится опорное решение. Оно получено
при следующих значениях переменных:
После того, как было получено опорное решение (т. е. все ограничения выполняются), находим оптимальное, признаком которого является наличие положительных значений коэффициентов целевой функции при ее решении на максимум и отрицательных -
на минимум.
Чтобы найти оптимальное решение, выбираем разрешающий столбец. Им будет тот, в F -строке которого стоит наибольшее по модулю отрицательное значение при решении задачи на максимум и наибольшее положительное - на минимум.
Допустим, что . Следовательно, вектор-стол-
бец является разрешающим. При этом разрешающим элементом является тот коэффициент, от деления свободного члена
на который будет получено наименьшее положительное частное, т. е. .
Допустим, что от деления С 3 на с 32 было получено наименьшее положительное частное. Следовательно, х 2 и х 1 меняются местами, и мы находим новое решение по четырем правилам.
Вычисления будем продолжать до тех пор, пока в F
-строке
не получим положительные значения (при решении задачи на максимум) или отрицательные (при решении задачи на минимум).
Затем целесообразно проверить выполнение требований каждого из ограничений. Для этого переменные подставляются в каждое из ограничений. Если нарушения отсутствуют, то расчеты верны, если присутствуют - имеется ошибка в арифметических действиях.
При использовании симплекс-метода возможны следующие четыре особых случая:
1. Вырожденность.
2. Альтернативные оптимальные решения.
3. Неограниченные решения.
4. Отсутствие допустимых решений.
Выясним причины возникновения таких ситуаций и способы их интерпретации в реальных задачах.
Вырожденность . Если хоть одна базисная переменная нулевая, то базисное решение называют вырожденным. Такая ситуация вполне может возникнуть в процессе решения задачи. Тогда может случиться, что переход к новому базису не обеспечивает улучшения значения функционала. Как правило, при последующих итерациях вырожденность исчезает. Дело в том, что на практике ее возникновение объясняется наличием в исходной постановке задачи избыточных ограничений. В этом случае, когда искусственная переменная, соответствующая одному из таких ограничений, выводится из базиса, функционал может и не улучшаться. Такая ситуация показана на рис. 2.4.
Из двух ограничений ресурсного типа второе является избыточным. При графическом решении (рис. 2.4) это очевидно, но из данных симплексной таблицы такой вывод сделать не удается. При исключении из базиса дополнительной переменной, соответствующей второму ограничению, значение функционала не возрастет. В итоге получим точку A , как оптимальное решение, которое не перестает быть верным от того, что оно вырожденное.
Рис. 2.4
Можно вообразить ситуацию, когда последовательность итераций при вырожденном базисе приведет к повторению уже имевшей место итерации, т. е. возникнет зацикливание. Искусственные примеры такого рода существуют, однако в реальных задачах зацикливание столь мало вероятно, что в большинстве программ, реализующих симплекс-метод, средства защиты от зацикливания не предусматриваются, так как они значительно замедляют процесс вычислений. Во-первых, нужно контролировать возникновение зацикливания, во-вторых, реализовать алгоритм для изменения порядка выбора разрешающих строк и столбцов.
Если подобные затруднения все же возникнут при компьютерном расчете, то можно попробовать произвести незначительные изменения отдельных коэффициентов модели (в пределах точности их определения) и повторить расчет. Если ранее имело место зацикливание, то порядок выбора разрешающих элементов, скорее всего, изменится.
Альтернативные оптимальные решения. Согласно основной теореме линейного программирования, если целевая функция достигает экстремального значения более чем в одной угловой точке, то она принимает это же значение в любой точке, являющейся их выпуклой линейной комбинацией. Графическая иллюстрация для случая двух переменных приведена на рис. 2.5. Максимальное значение целевая функция получает в угловых точках A и B . Предположим, что при использовании симплекс-метода получена точка A как оптимальный план. Тогда небазисной переменной будет соответствовать нулевая оценка, так как при ее введении в базис с последующим переходом к точке B значение функционала не изменится.
Рис. 2.5
Таким образом, признаком существования альтернативных планов является наличие нулевых оценок для небазисных переменных. На практике существование альтернативных решений можно использовать для учета дополнительных соображений при выборе плана действий. Если рассмотренный пример интерпретировать как задачу об оптимальном производственном плане, то лучше выбрать точку B , чтобы меньше зависеть от изменений рыночной конъюнктуры.
Если все оценки небазисных переменных строго больше нуля, то найденный оптимальный план является единственным.
С практической точки зрения, малые положительные значения оценок не очень существенно отличаются от нулевых хотя бы потому, что большая часть используемых данных определена с некоторой погрешностью. Следовательно, есть основания выполнить расчеты дополнительных вариантов, чтобы оценить реальный эффект от введения таких переменных в принимаемый план.
Неограниченные решения. Неограниченное возрастание переменных без нарушения ограничений – это явный признак ошибки. Например, в задаче о производственном плане каждый ресурс ограничен. Мало вероятно, что при записи модели такие ограничения пропущены, но при их вводе возможна ошибка в знаках. При использовании компьютерных программ, если не указать требование неотрицательности переменных, придавая формально одной из переменных отрицательное значение, программа может получать ресурсы для неограниченного роста других переменных.
Если ошибку не удается быстро обнаружить, то можно ввести дополнительные ограничения, например, на минимальные и максимальные значения переменных, задавая их с большим допуском по отношению к реально возможным значениям. Ошибка выявится при анализе ограничений, в которых участвуют переменные, значения которых вышли за пределы допустимого.
Отсутствие допустимых решений. Такая ситуация возникает при несовместности ограничений задачи, что можно считать ошибкой в ее постановке или в используемых данных. На рис 2.6 показаны ограничения по минимальным объемам производства каждого из двух видов продукции. Видно, что третье ограничение, определяющее максимально допустимое использование некоторого ресурса, позволяет удовлетворить любое из этих требований, но не оба одновременно.
Рис. 2.6
Такие противоречия, естественно, возникают в условиях плановой экономики при разных целевых установках центрального планирующего органа и руководителей производства. Первый, как правило, – стремится к увеличению объема плановых заданий, – последним же предпочтительнее такой план, который легче выполнить и получить поощрения за перевыполнение. Когда с этой целью искажаются фактические данные, то может случиться, что ретроспективный расчет плана по отчетным данным покажет, что допустимые решения отсутствуют.
Рыночная экономика также не свободна от подобных проблем. Данные могут целенаправленно искажаться, например, для того, чтобы повлиять на текущий курс акций. В любом случае оптимизационная модель становится эффективным средством контроля и анализа всей совокупности статистической отчетности.
Однако причина отсутствия допустимых решений может быть и весьма тривиальна - неправильно поставленная десятичная запятая, или ошибочное занесение правильного числового значения, но не в ту ячейку. Чем больше размерность задачи, тем вероятнее подобные ошибки и тем труднее их искать. Для выявления таких ошибок можно рекомендовать вводить в модель переменные, которые показывали бы, сколько и какого именно ресурса недостает. Разумеется, таким переменным в функционале должны соответствовать некоторые штрафы иначе недостающие ресурсы войдут в решение, что не имеет смысла. Величины штрафов произвольны, но достаточно велики для того чтобы соответствующие переменные (будем называть их штрафными) могли войти в решение только тогда когда иначе невозможно выполнить остальные ограничения задачи. Слишком большие штрафы будут только способствовать росту ошибок округления. В соответствии с принципом “разумной достаточности” можно, например, ориентировочную цену реального ресурса увеличить на порядок.
В технике оптимальный (вариант, решение, выбор и т. д.) - наилучший (вариант, решение, выбор, …) среди допустимых при наличии правила предпочтения одного другому. Такое правило называется критерием оптимальности , а мерой предпочтения будут служить показатели качества . Можно говорить об оптимальном варианте только при удовлетворении двух условий:
- наличия хотя бы одного критерия,
- наличия не менее двух сравниваемых вариантов (необходимость осуществления выбора).
Каждый выбор лучшего варианта конкретен, поскольку производится на соответствие определённым критериям. Следовательно, говоря об оптимальном варианте, всегда нужно указывать эти критерии (то есть «оптимальный по …»). И то, что может быть оптимальным при одном критерии, не обязательно будет таковым при другом. Например, сцена, «оптимальная по площади», не обязательно будет «оптимальной по акустике».
Оптимальное решение является результатом одного из видов выбора (критериального выбора). Изучением проблем, связанных с выбором оптимальных решений, занимаются теория исследования операций и теория принятия решений .
Примечания
Wikimedia Foundation . 2010 .
- Оптиконевромиелит
- Оптиматы (фема)
Смотреть что такое "Оптимальное решение" в других словарях:
Оптимальное решение - решение, которое минимизирует или максимизирует (в зависимости от характера задачи) критерий качества оптимизационной модели (критерий оптимальности) при заданных условиях и ограничениях, представленных в этой модели. Но… … Экономико-математический словарь
оптимальное решение - Решение, которое минимизирует или максимизирует (в зависимости от характера задачи) критерий качества оптимизационной модели (критерий оптимальности) при заданных условиях и ограничениях, представленных в этой модели. Но поскольку модель никогда… … Справочник технического переводчика
Оптимальное управление - Оптимальное управление это задача проектирования системы, обеспечивающей для заданного объекта управления или процесса закон управления или управляющую последовательность воздействий, обеспечивающих максимум или минимум заданной… … Википедия
решение - вынести новое решение действие вынести решение действие выносить решение действие выполнять решение реализация ждать решения модальность, ожидание зависит решение субъект, зависимость, причина следствие заниматься решением действие …
решение - сущ., с., употр. часто Морфология: (нет) чего? решения, чему? решению, (вижу) что? решение, чем? решением, о чём? о решении; мн. что? решения, (нет) чего? решений, чему? решениям, (вижу) что? решения, чем? решениями, о чём? о решениях 1. Решением … Толковый словарь Дмитриева
оптимальное - найти оптимальное решение существование / создание … Глагольной сочетаемости непредметных имён
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПОЗИЦИОННОЕ - решение задачи оптимального управления математической теории, состоящей в синтезе оптимального управления в виде стратегии управления по принципу обратной связи, как функции текущего состояния (позиции) процесса (см. ). Последнее… … Математическая энциклопедия
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПРОГРАММНОЕ - решение задачи оптимального управления математической теории, в к рой управляющее воздействие u=u(t).формируется в виде функции времени (тем самым предполагается, что по ходу процесса никакой информации, кроме заданной в самом начале, в систему… … Математическая энциклопедия
Оптимальное планирование - совокупность методов и средств, позволяющих выбрать из множества возможных вариантов развития экономической системы вариант, обеспечивающий наиболее эффективное использование ресурсов. Основу оптимального планирования составляет решение задачи… … Финансовый словарь
Оптимальное управление - летательным аппаратом раздел динамики полёта, посвящённый развитию и использованию методов оптимизации для определения законов управления движением летательного аппарата и его траекторий, обеспечивающих максимум или минимум выбранного критерия… … Энциклопедия техники
Книги
- Оптимальное использование ресурсов, обеспечивающих жизненный цикл предмета , Катульский Август Александрович. Важность увеличения отношения качества предмета к его стоимости сознавалась давно и научная мысль всегда стремилась к наиболее полному и простому решению этой задачи. Однако, когда необходимо…
