Наиболее оптимальное решение в случае. Определение оптимального решения задачи линейного программирования. Прибыль от продажи пакета
Если в только что рассмотренной задаче первое же полученное базисное решение оказалось допустимым, то в других случаях его можно найти не сразу, а через некоторое число шагов.
При этом надо помнить, что на первом этапе симплексного метода, т. е. при нахождении какого-либо допустимого решения, линейная форма в расчет не берется, а все преобразования относятся только к системе ограничений.
Пусть задача линейного программирования задана в общем виде, т.е. системой m линейных уравнений с n переменными (m Следовательно, этому способу разбиения переменных на основные и неосновные соответствует базисное решение …; 0; 0;…;0. Рассмотрим общий случай, когда это решение является недопустимым. От полученного базисного решения следует сначала перейти к какому-нибудь допустимому базисному решению, причем не обязательно, чтобы этот переход осуществлялся сразу, в один шаг. Если система ограничений не противоречива, то через конечное число шагов будет осуществлен переход к допустимому базисному решению. По предположению, исходное базисное решение является недопустимым. Следовательно, среди свободных членов системы ограничений имеется хотя бы один отрицательный (число отрицательных свободных членов этой системы совпадает с числом отрицательных компонент исходного базисного решения). Пусть им является свободный член k i
i-ro уравнения, т. е. основная переменная x i
в соответствующем базисном решении отрицательна. Для перехода к новому базисному решению необходимо решить два вопроса: 1) установить, какая неосновная переменная должна быть переведена в число основных; 2) выбрать переменную, которую из основных следует перевести в неосновные на место выбывшей в основные переменной. При переводе неосновной переменной в основные она не убывает, а, как правило, возрастает: вместо нуля в исходном базисном решении она примет положительное значение в новом базисном решении (исключение имеет место только при вырождении). Поэтому для решения вопроса о том, какие неосновные переменные можно перевести в основные, нужно уметь находить неосновные переменные, при увеличении которых возрастает основная переменная, отрицательная в исходном базисном решении. Вернемся к i-му уравнению системы, в котором свободный член k i
отрицателен. Оно показывает, что переменная x i
возрастает при возрастании тех неосновных переменных, коэффициенты которых в этом уравнении положительны. Отсюда следует, что в основные можно переводить те неосновные переменные, которые в уравнении системы с отрицательным свободным членом имеют положительные коэффициенты. Здесь могут представиться три случая. 1. В i-м уравнении системы нет неосновных переменных с положительными коэффициентами, т. е. все коэффициенты b i , j
отрицательны (как и свободный член k i).
В этом случае данная система ограничений несовместна – она не имеет ни одного допустимого решения. Действительно, вследствие неотрицательности всех переменных, в том числе x m + l ,...,x n ,
i -го уравнения, в котором свободный член k i
и все коэффициенты b i , m + l ,...,b i , n
отрицательны, следует, что переменная x i
- не может принимать неотрицательных значений. Но если нет ни одного допустимого решения системы ограничений, то нет и оптимального. 2. В i-м уравнении имеется одна переменная х т+ j
,коэффициентпри которой положителен. В этом случае именно эта переменная переводится в основные. 3. В i-м уравнении имеется несколько переменных с положительными коэффициентами. В этом случае в основные можно перевести любую из них. Далее необходимо установить, какая основная переменная должна быть переведена в число неосновных. Для этого следует воспользоваться правилом: находят отношения свободных членов к коэффициентам при переменной, переводимой в основные, из всех уравнений, где знаки свободных членов и указанных коэффициентов противоположны, а затем рассматривают абсолютную величину этих отношений и из них выбирают наименьшую (если в некоторых уравнениях знаки свободных членов и коэффициентов совпадают или в каких-то уравнениях переменная, переводимая в основные, отсутствует, то отношение считают равным ∞). Уравнение, из которого получено наименьшее отношение, выделяют. Выделенное уравнение показывает, какая из основных переменных должна быть переведена в неосновные. Выразив новые основные переменные через неосновные, переходят к следующему базисному решению. В результате получается аналогичная системе система уравнений, в которой число отрицательных свободных кленов либо совпадает с их числом в системе, либо на единицу меньше. Это зависит от того, положителен или отрицателен свободный член в выделенном уравнении. Если в выделенном уравнении свободный член отрицателен, то в новом базисном решении число отрицательных компонент окажется на единицу меньше, чем в исходном. Если же в выделенном уравнении свободный член положителен (или равен нулю), то в новом базисном решении число отрицательных компонент останется таким же, как и в исходном. Итак, получается новое, улучшенное базисное решение, которое ближе к области допустимых решений системы ограничений. Если оно окажется недопустимым, то к нему следует применить ту же схему еще раз. В результате через конечное число шагов получится допустимое базисное решение. Продолжения примера 4.1.
Нужно найти такое допустимое базисное решение этой системы ограничений, которое бы максимизировало линейную форму . Так как система ограничений есть система четырех независимых уравнений с шестью переменными, то число основных переменных должно равняться четырем, а число неосновных - двум. Для решения задачи симплексным методом, прежде всего, нужно найти любое базисное решение. В данном случае это легко сделать. Для этого достаочно взять в качестве основных добавочные переменные х
3 , х
4 , х
5 , х
6 . Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель. Считая неосновные переменные х
1 , x
2 равными нулю, получим базисное решение (0; 0; 120; 160; 120; 80), которое к тому же оказалось допустимым. Поэтому здесь отпадает надобность в применении первого этапа симплексного метода. Переходим сразу ко второму этапу, т. е. к поискам оптимального решения. 1 шаг. Основные переменные: х 3 , х 4 , х 5 , х 6 ; неосновные переменные: х
1 , x
2 . В системе основные переменные выразим через неосновные. Для того чтобы судить, оставить ли неосновные переменные в числе неосновных или их выгоднее с точки зрения приближения к оптимальному решению перевести в основные, следует выразить через них и линейную форму (в данном случае она уже выражена через переменные х
1 , x
2) Тогда получим: При х
1 = х
2 = 0 имеем х
3 = 120, х
4 = 160, х
5 = 120, х
6 = 80, что дает базисное решение (0; 0; 120; 160; 120; 80), которое мы приняли за исходное. При этом базисном решении значение линейной формы =0. Когда мы полагали х
1 = х
2 = 0 (производство ничего не выпускает), была поставлена цель - найти первое, безразлично какое, базисное решение. Эта цель достигнута. Теперь от этого первоначального решения нужно перейти к другому, при котором значение линейной формы увеличится. Из рассмотрения линейной формы видно, что ее значение возрастает при увеличении значений переменных х
1 и х
2 . Иными словами, эти переменные невыгодно считать неосновными, т. е. равными нулю, их нужно перевести в число основных. Это и означает переход к новому базисному решению. При симплексном методе на каждом шаге решения предполагается перевод в число основных только одной из свободных переменных. Переведем в число основных переменную х
2 , так как она входит в выражение линейной формы с большим коэффициентом. Как только одна из свободных переменных переходит в число основных, одна из основных должна быть переведена на ее место в число неосновных. Какую же из четырех основных переменных нужно вывести? Ответить на этот вопрос помогут следующие рассуждения. Значение х
2 необходимо сделать как можно большим, так как это соответствует конечной пели - максимизации F
. Однако оказывается, что увеличение х
2 может продолжаться только до известных границ, а именно до тех пор, пока не нарушится требование неотрицательности переменных. Так, из первого уравнения системы следует, что переменная х 2 не должна превышать числа 120/4, т. е. х
2 ≤30, поскольку только при этих значениях х
2 переменная х
3 остается положительной (если х
2 = 30, то х
3 = 0; если же х
2 >30, то х
3 < 0). Из третьего уравнения системы следует, что х
2 ≤ 120/2, т. е. х
2 ≤ 60, из четвертого - что х
2 ≤ 80/2, т. е. х
2 ≤ 40 (во второе уравнение переменная х
2 не входит). Всем этим условиям удовлетворяет х
2 ≤ 30. Иными словами, для ответа на вопрос, какую переменную нужно перевести в число неосновных, нужно принять х
2 = min {120/4; 120/2; 80/2} = min {30; 60; 40} = 30. Тогда х
3 = 0 и х
3 переходит в число неосновных переменных, а х 4 и х 5 останутся положительными, 2 шаг. Основные переменные: х
2 , х
4 , х
5 , х
6 неосновные переменные: х
1 и х
3 . Выразим основные переменные и линейную форму через неосновные. В системе берем то уравнение, из которого получено минимальное значение отношения свободного члена к коэффициенту при х
2 . В данном случае это первое уравнение. Выразив из этого уравнения х
2 , имеем, х
2 = 30 - 0.25 · х
3 . Подставим это выражение х
2 во все остальные уравнения системы (4.4) и в линейную форму F
и, приведя подобные члены, получим При х
1 = х
3 = 0 имеем F =
90. Это уже лучше, чем на 1 шаге, но не искомый максимум. Дальнейшее увеличение функции F
возможно за счет введения переменной х
1 в число основных; так как эта переменная входит в выражение F
с положительным коэффициентом, поэтому ее увеличение приводит к увеличению линейной формы и ее невыгодно считать неосновной, т.е. равной нулю. Для ответа на вопрос, какую переменную вывести из основных в неосновные, примем х
1 = min {160/4; 60/2; 20/1} = 20. Тогда х
6 = 0 и х
6 переходит в число неосновных переменных, а х
4 и х
5 , остаются при этом положительными. Первое уравнение не используется при нахождении указанного минимума, так как х
] не входит в это уравнение. 3 шаг. Основные переменные: х
1 ,х 2 , х 4 ,
х 5 ; неосновные переменные: х 3 , х 6 . Выразим основные переменные и линейную форму через неосновные. Из последнего уравнения системы (4.5) (оно выделено) имеем х
1 = 20 + 0.5 · х
3 - х
6 . Подставляя это выражение в остальные уравнения и в линейную форму, получим Из выражения линейной формы следует, что ее максимальное значение еще не получено, так как возможно увеличение F
за счет введения в основные переменной х
3 (она имеет положительный коэффициент). Полагаем х
3 = min {∞; 30/0,25; 80/2; 20/0,5} =40. Здесь мы впервые встречаемся с двумя положениями, которые требуют дополнительных разъяснений. Во-первых, хотя переменная х
3 и входит в выражение для х
1 (первое уравнение системы (4.6), но имеет положительный коэффициент и при любом возрастании х
3 переменная х
1 не может стать отрицательной. Иными словами, в первом уравнении никаких ограничений на возрастание переменной х
3 не накладывается, поэтому мы условно пишем ∞. Условимся в дальнейшем пользоваться этим же обозначением, если переменная, вновь вводимая в число основных, не входит в какое-либо уравнение системы ограничении. Во-вторых, мы получим два одинаковых минимальных значения, равные 40. Если х
3 = 40, то х
4 =
0 и х 5 =
0, т. е. напрашивается вывод, что вместо одной переменной нужно перевести в число неосновных сразу две: х
4 и х 5 .
Но число основных переменных не должно быть меньше четырех. Для этого поступают следующим образом. Одну из переменных (х
4 или х
5 .) оставляют в числе основных, но при этом ее значение считают равным нулю, т. е. полученное на следующем шаге базисное решение оказывается вырожденным. Оставим, например, х
4 в числе основных переменных, а х
5 переведем в число неосновных. 4 шаг. Основные переменные: х
1 , х 2 , х
3 , х
4 ; неосновные переменные: х 5 , х 6 . Выразим основные переменные и линейную форму F
через неосновные, начав это выражение из четвертого уравнения системы (4.6). В итоге получим Так как в выражение линейной формы переменные х
5 и х
6 входят с отрицательным коэффициентами, то никакое увеличение F
за счет этих переменных невозможно. Отсутствие на каком-то шаге симплексного метода в выражении линейной формы F, максимум которой ищется, неосновных переменных с положительными коэффициентами является критерием оптимальности.
Следовательно, на 4 шаге критерий оптимальности достигнут и задача решена. Оптимальным служит решение (40; 20; 40; 0; 0; 0), при котором F
max =140. Таким образом, для получения наибольшей прибыли, равной 140 ден. ед., из данных ресурсов необходимо получить 40 единиц продукции с сенокосов и 20 с пашни. При этом ресурсы II, III и IV видов окажется использованной полностью, а 40 ед. I вида останутся неизрасходованными. Пример 4.2.
Найти максимум функции F = х
1 + 2·х
2 при ограничениях Вводим добавочные неотрицательные переменные х
3 , х
4 , х
5 , х
6 и сводим данную систему неравенств к эквивалентной ей системе уравнений Введенные добавочные переменные принимаем за основные, так как в этом случае базисное решение системы легко находится. Тогда х
1 и х
2 - неосновные переменные. 1 шаг. Основные переменные: х
3 , х
4 , х
5 , х
6 ; неосновные переменные; х
1 и х
2 . Выразив основные переменные через неосновные, получим Следовательно, данному разбиению переменных на основные и неосновные соответствует базисное решение (0; 0; - 2; - 4; 2; 6), которое является недопустимым (две переменные отрицательны), а поэтому оно не оптимальное. От этого базисного решения перейдем к улучшенному. Чтобы решить, какую переменную следует перевести из неосновных в основные, рассмотрим любое из двух имеющихся уравнений последней системы с отрицательными свободными членами, например второе. Оно показывает, что в основные переменные можно перевести х
1 и х
2 , так как в этом уравнении они имеют положительные коэффициенты (следовательно, при их увеличении, что произойдет, если переведем любую из них в основные переменные, переменная х
4 увеличится). Попробуем перевести в основные переменную х
1 . Чтобы установить, какую переменную следует перевести из основных в неосновные, найдем абсолютную величину наименьшего отношения свободных членов системы к коэффициентам при х
1 ,
имеем х
1 = min (∞; 4/1; 2/1; ∞) = 2. Оно получено из третьего уравнения, показывающего, что в неосновные нужно перевести переменную х
5 , которая в исходном базисном решении положительна. Следовательно, полученное базисное решение, как и исходное, содержит две отрицательные компоненты, т. е. при переходе к такому базисному решению улучшения не произойдет. Если же перевести в основные переменную х
2 ,
то наименьшее отношение свободных членов к коэффициентам при х
2 составит х
2 -
min (2/2; 4/1; ∞; 6/1) = 1. Оно получено из первого уравнения, в котором свободный член отрицателен. Следовательно, переводя х
2 в основные, а х
3 в неосновные переменные, мы получим базисное решение, в котором число отрицательных компонент на единицу меньше, чем в исходном. Поэтому остановимся на этой возможности: переводим х
2 в основные, а х
3 в неосновные переменные; тогда выделенным окажется первое уравнение. 2 шаг. Основные переменные: х
2 , х
4 , х
5 , х
6 ; неосновные переменные: х
1 и х
3 . Выразим новые основные переменные через новые неосновные, начиная это делать с выделенного на 1 шаге уравнения. В результате получим Следовательно, имеем новое базисное решение (0; 1; 0; -3; 3; 5), которое также является недопустимым, а поэтому не оптимальным. Но в нем, как мы и предвидели, только одна переменная отрицательна (а именно х
4). От полученного базисного решения необходимо перейти к другому. Рассмотрим уравнение с отрицательным свободным членом, т.е. второе уравнение. Оно показывает, что в основные переменные можно перевести х
1 и х
3 . Переведем в основные переменные х
1 .
Найдем наименьшее из абсолютных величин отношений свободных членов системы к коэффициентам при х
1 ; имеем х
1 =
min (∞; 3/1,5; 3/0,5; 5/0,5) = 2. Значит, в неосновные переменные нужно перевести х
4 . Так как наименьшее отношение получено из второго уравнения, то его выделяем. В новом базисном решении уже не окажется отрицательных компонент, т. е. оно является допустимым. 3 шаг. Основные переменные: х
1 , х
2 , х
5 , х
6 ; неосновные переменные: х
3 , х
4 . Выразив основные переменные через неосновные, получим Новое базисное решение имеет вид (2; 2; 0; 0; 2; 4). Является ли оно оптимальным, можно установить, если выразить линейную форму через неосновные переменные рассматриваемого базисного решения. Сделав это, получим . Таким образом, к линейной форме обращаемся только тогда, когда базисное решение является допустимым. Так как мы ищем максимум линейной формы, то полученное базисное решение не оптимальное. Переводим в число основных переменную х
4 имеющую больший положительный коэффициент. Находим х
4 = min (∞; ∞; 2: (1/3); 4/(1/3)) = 6. Это наименьшее отношение получено из третьего уравнения системы, которое и выделяем. Оно показывает, что при х
4 =6 переменная х
5 = 0 и поэтому перейдет в число неосновных. 4 шаг. Основные переменные: х
1 , х
2 , х
4 , х
6 ;неосновные переменные: х
3 , х
5 . Выразив основные переменные через неосновные, получим Линейная форма, выраженная через те же неосновные переменные, примет вид . Следовательно, базисное решение (6; 4; 0; 6; 0; 2), к которому мы перешли, не является оптимальным. Увеличение линейной формы возможно при переходе к новому базисному решению, в котором переменная х 3 является основной. Находим х
3 = min {∞; ∞; со; 2/1} = 2. Это наименьшее отношение получено из четвертого уравнения системы и показывает, чго при х
3 = 2 переменная х
6 = 0 и переходит в число неосновных. 5 ш а г. Основные переменные: х
1 , х
2 , х
3 , х
4 неосновные переменные х
5 , х
6 .Выразив основные переменные через неосновные, получим Линейная форма, выраженная через неосновные переменные нового базисного решения, имеет вид . Критерий оптимальности для случая максимизации линейной формы выполнен. Следовательно, базисное решение (8; 6; 2; 10, 0; 0) является оптимальным, а максимум линейной формы F
max =
20. 4.5 Графическое решение задач линейного программирования Графический способ решения задач линейного программирования целесообразно использовать для: Решения задач с двумя переменными, когда ограничения выражены неравенствами; Решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных. Запишем задачу линейного программирования с двумя переменными: целевая функция: ограничения: Каждое из неравенств (4.8) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ; . В том случае, если система неравенств (4.8) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей - выпуклое, то областью допустимых решений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств. Областью допустимых решений системы неравенств (4.8) может быть: Выпуклый многоугольник; Выпуклая многоугольная неограниченная область; Пустая область; Отрезок; Единственная точка. Целевая функция (4.7) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение Z. Вектор c координатами и , перпендикулярный этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор - направление убывания Z. Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (4.8) и семейство параллельных прямых (4.7), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня проходящую через начало координат и перпендикулярную вектору , и будем передвигать ее в направлении вектора до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты указанной точки и определяют оптимальный план данной задачи. Рисунок 4.1 - Оптимум функции Z достижим в точке А
Рисунок 4.2 - Оптимум функции Z достигается в любой точке [АВ]
Заканчивая рассмотрение геометрической интерпретации задачи (4.7) - (4.8), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 4.1 - 4.4. Рисунок 4.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рисунка 4.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. Рисунок 4.3 - Оптимум функции Z недостижим
Рисунок 4.4 - Область допустимых решений - пустая область
На рисунке 4.3 изображен случай, когда максимум недостижим, а на рисунке 4.4 - случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора , а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения. Для практического решения задачи линейного программирования (4.7) - (4.8) на основе ее геометрической интерпретации необходимо следующее. 1.Построить прямые, уравнения которых получаются в результате замены в ограничениях (4,4) знаков неравенств на знаки равенств. 2.Найти полуплоскости, определяемые каждым из ограничений задачи. 3.Определить многоугольник решений. 4.Построить вектор . 5.Построить прямую , проходящую через начало координат и перпендикулярную вектору . 6.Передвигать прямую в направлении вектора , в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов. 7.Определить координаты точки максимума функции и вычислить значение целевой функции в этой точке. Пример 4.3.
Предприятие изготавливает два вида продукции П и Р, которая поступает в оптовую продажу. Для производства продукции используют два вида сырья А и Б. Максимально возможные запасы сырья в сутки составят 9 и 13 единиц соответственно. Расход сырья вида А на производство продукции П и Р составят 2 и 3 единицы соответственно, вида Б 3 и 2 единицы. Опыт работы показал, что суточный спрос на продукцию П никогда не превышает спроса на продукцию Р более чем на 1 единицу. Кроме того известно, что спрос на продукцию Р никогда не превышает 2 единицы в сутки. Оптовые цены единицы продукции равны 3 единицы для П, и 4 единицы для Р. Какое количество продукции каждого вида должно произвести предприятие, чтобы доход от реализации был максимальным. Решить задачу геометрическим способом. Решение. Построим многоугольник решений (рис. 7.5). Для этого в системе координат X 1 OX 2 на плоскости изобразим граничные прямые: Взяв какую-либо точку, например начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Полуплоскости, определяемые неравенствами, на рис. 7.5 показаны стрелками. Областью решений является многоугольник OABCD. Для построения прямой строим вектор-градиент и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z= 0 перемещаем параллельно самой себе в направлении вектора . Из рисунок 4.5 следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L 1 и Z 3 . Для определения ее координат решим систему уравнений: Оптимальный план задачи = 2,4; =1,4. Подставляя значения и в линейную функцию, получим: 3 2,4 + 4 1,4 = 12,8. Полученное решение означает, что объем производства продукции П должен быть равен 2,4 ед., а продукции Р - 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д. е. Рисунок 4.5 - Решение задачи линейного программирования геометрическим способом
5. ДВОЙСТВЕННЫЕ ЗАДАЧИ Составление двойственной задачи. Рассмотрим две задачи линейного программирования: Максимизировать функцию при ограничениях Минимизировать функцию при ограничениях Эти задачи обладают следующими свойствами: 1. В одной задаче ищется максимум линейной формы, а в другой – минимум. 2°. Коэффициенты при переменных в линейной форме одной задачи являются свободными членами системы ограничений другой задачи, наоборот, свободные члены системы ограничений одной задачи – коэффициентами при переменных в линейной форме другой задачи. 3°. В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла, а именно: при нахождении максимума линейной формы эти неравенства имеют вид, а при нахождении минимума – вид 4°. Коэффициенты при переменных в системах ограничений описываются матрицами которые являются транспонированными относительно друг друга. 5°. Число неравенств в системе ограничений одной задачи совпадает с числом переменных другой задачи. 6 е. Условия неотрицательности переменных сохраняются в обеих задачах. Две задачи линейного программирования, удовлетворяющие указанным выше условиям, называются симметричными взаимно двойственными задачами. Мы будем изучать только симметричные двойственные задачи, а поэтому будем называть их короче – двойственными задачами. Таким образом, каждой задаче линейного программирования можно поставить в соответствие двойственную ей задачу. Первоначальную задачу будем называть исходной (или прямой). Прямая и двойственная ей задача, взятые вместе, образуют пару взаимно двойственных задач, причем любую из них можно рассматривать как исходную, тогда другая окажется двойственной ей. Из сказанного вытекают следующие правила составления задачи, двойственной по отношению к исходной: 1. Приводят все неравенства системы ограничений исходной задачи к неравенствам одного смысла: если в исходной задаче ищется максимум линейной формы – к виду ≤, если же минимум – к виду ≥. Для этого неравенства, в которых это требование не выполняется, умножают на - 1. 2. Выписывают матрицу А коэффициентов при переменных исходной задачи, полученных после преобразования п. 1, и составляют матрицу А", транспонированную относительно матрицы А. 3. Составляют систему ограничений двойственной задачи, взяв в качестве коэффициентов при переменных элементы матрицы А", а в качестве свободных членов – коэффициенты при переменных в линейной форме исходной задачи, и записывают неравенства противоположного смысла по сравнению с неравенствами, полученными в п. 1. 4. Составляют линейную форму двойственной задачи, приняв за коэффициенты при переменных свободные члены системы ограничений исходной задачи, полученные в п. 1. 5. Указывают, что необходимо найти при решении двойственной задачи, а именно: минимум линейной формы, если в исходной задаче ищется максимум, и максимум, если в исходной задаче ищется минимум. 6. Записывают условие неотрицательности переменных двойственной задачи. Пример 5.1. Составить задачу, двойственную следующей: найти максимум функции при ограничениях Третье неравенство системы (*) не удовлетворяет п. 1 правил составления двойственной задачи. Поэтому умножим его на –1: Для облегчения составления двойственной задачи лучше пользоваться расширенной матрицей В, в которую наряду с коэффициентами при переменных системы ограничений исходной задачи запишем свободные члены и коэффициенты при переменных в линейной форме, выделив для этой цели дополнительные столбец и строку. Матрицу В транспонируем и, используя транспонированную матрицу В / , составляем задачу двойственную данной. Двойственная задача сводится к нахождению минимума функции при ограничениях Основные теоремы двойственности
Теория двойственности в линейном программировании строится на следующих основных теоремах. Теорема 1. Если одна из задач линейного программирования имеет конечный оптимум, то и двойственная к ней также имеет конечный оптимум, причем оптимальные значения линейных форм обеих задач совпадают, т. е. F max = Z min
или F min = Z max .
Если же линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы. Прежде чем сформулировать следующую теорему, установим соответствия между переменными в исходной и двойственной задачах. При решении симплексным методом исходной задачи для сведения системы неравенств к эквивалентной ей системе уравнений нужно ввести т добавочных неотрицательных переменных (по числу неравенств в системе ограничений) где i =
1, 2,…,т означает номер неравенства, в которое была введена добавочная переменная . Система ограничений двойственной задачи состоит из п неравенств, содержащих т переменных. Если решать эту задачу симплексным методом, то следует ввести п добавочных неотрицательных переменных где j = 1, 2,…,т означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная . Установим следующее соответствие между переменными в исходной и двойственной задачах: Иными словами, каждой первоначальной переменной исходной Теорема 2.
Компоненты оптимального решения одной из задач (прямой или двойственной) равны абсолютным величинам коэффициентов при соответствующих переменных в выражении линейной формы другой задачи (двойственной или прямой) при достижении ею оптимума и при условии, что полученное оптимальное решение не является вырожденным. Из теорем 1 и 2 следует, что если решить одну из взаимно двойственных задач, т. е. найти ее оптимальное решение и оптимум линейной формы, то можно записать оптимальное решение и оптимум линейной формы другой задачи. Пример 5.2. Решить симплексным методом прямую и двойственную задачи, приведенные в предыдущем примере. Решение прямой задачи. Сведем систему ограничений неравенств (см. с. 268) к системе уравнений, введя неотрицательные добавочные переменные: Добавочные переменные х 3 , x 4 , х 5 , x 6 примем за основные на I шаге решения. 1 шаг. Основные переменные: х 3 , x 4 , х 5 , x 6 ; неосновные переменные: х 1 , х 2 . Выразим основные переменные через неосновные (линейную форму на этом шаге решения не рассматриваем, так как соответствующее базисное решение не является допустимым): Для получения допустимого базисного решения переменную переведем в основные. Находим = min {2/1; ∞; 1/1; 5/1} = 1. При этом переменная х 5
переходит в неосновные. 2 шаг. Основные переменные: х 1 , х 3 , х 4 , х 6 неосновные переменные; х 2 , х 5
. Выразим основные переменные и линейную форму через неосновные: Переведем в основные переменную х 5
. Полагая х 5
=min {∞; 1/1; ∞; 4/1} = 1, заключаем, что переменную х 3 нужно перевести в неосновные. 3 шаг. Основные переменные: х 1 , х
4 , х 5 , х 6 , неосновные переменные х 3 ,х 2 . Имеем Переменную x 2 переводим в основные. Находим х 2 = min {∞; ∞;∞; 1/1}=1. Тогда переменная х 6 переходит в неосновные. 4 ш а г. Основные переменные:: х 1 , х 2 , х
4 , х 5 , ; неосновные переменные: х 2 , х 6 . Имеем Критерий оптимальности выполнен. Оптимальное решение имеет вид (4; 1; 0; 5; 4; 0); при этом решении F max = 13. Продолжение примера 5.1. Систему ограничений двойственной задачи сводим к системе уравнений: Добавочные переменные y 5 y 6 примем за основные на 1 шаге решения. 1 шаг. Основные переменные: y 5 , y 6 ; неосновные переменные: y 1 , у 2 , у 3 , у 4 . Выразим основные переменные через неосновные: Переведем в основные переменную у 4 . Находим у 4 = mm (3/1: 1/1 = 1. Переменная y 6 переходит в неосновные. 2 шаг. Основные переменные: у 4 , y 5 неосновные переменные: y 1 , у 2 , у 3 , у 6 . Имеем Переменную y 1 переведем в основные. Так как y 1 = min (∞; 2/3) = 2/3, то переменная y 5 переходит в неосновные. 3 шаг. Основные переменные y 1 , у 4 , неосновные переменные: у 2 , у 3 , y 5 , у 6 . Так как соответствующее базисное решение задачи является допустимым, то выразим через неосновные переменные не только основные, но и линейную форму: Критерий оптимальности (для случая минимизации линейной формы) выполнен. Оптимальное решение имеет вид (2/3; 0; 0; 7/3; 0; 0), при этом Z min = 13. Решив двойственную задачу, убеждаемся в справедливости первой части теоремы 1: двойственная задача тоже имеет конечный оптимум, причем Z min =
=F max = 13. Убедимся, что справедливо также и утверждение теоремы 2. Для этого запишем переменные прямой и двойственной задачи, соблюдая их соответствие; Линейную форму, полученную на последнем шаге решения двойственной задачи, выразим через все переменные этой задачи: Рассматривая коэффициенты при переменных y j в этой линейной форме и учитывая их соответствие с коэффициентами при переменных x i ,
получим решение (4; 1; 0; 5; 4; 0), совпадающее с оптимальным решением прямой задачи. Замечание. Решив прямую задачу, можно сразу получить решение двойственной задачи. Если выразить линейную форму F, полученную на 4 шаге решения прямой задачи, через все переменные этой задачи, то получим На основании теоремы 2, учитывая соответствие между переменными в прямой и двойственной задачах и взяв абсолютную величину коэффициентов при переменных, найдем оптимальное решение двойственной задачи (2/3; 0; 0; 7/3; 0; 0). При этом Z min =F max = 13. 6 ТРАНСПОРТНАЯ ЗАДАЧА Задача линейного программирования (ЗЛП) − это задача нахождения наибольшего (или наименьшего) значения линейной функции на выпуклом многогранном множестве. Симплекс метод − это метод решения задачи линейного программирования. Суть метода заключается в нахождении начального допустимого плана, и в последующем улучшении плана до достижения максимального (или минимального) значения целевой функции в данном выпуклом многогранном множестве или выяснения неразрешимости задачи. Рассмотрим следующую задачу линейного программирования в канонической форме: Как было паказано выше, для задачи, записанной в канонической форме, если среди векторов столбцов матрицы A
есть m
единичных и линейно независимых , можно непосредственно указать опорный план. Однако для многих задач линейного программирования, записанных в канонической форме и имеющих опорные планы, среди векторов столбцов матрицы A
не всегда есть m
единичных и линейно независимых. Рассмотрим такую задачу: Пусть требуется найти максимум функции при условиях где первы n
элементы нули. Переменные образуют так называемый искусственный
базис m
-мерного векторного пространства. Так как расширенная задача имеет опорный план, то ее решение можно найти симплекс методом. Теорема 4.
Если в оптимальном плане Таким образом, если в найденном оптимальном плане расширенной задачи, значения искусственных переменных равны нулю, то получен оптимальный план исходной задачи. Остановимся более подробно на нахождении решения расширенной задачи. Значение целевой функции при опорном плане (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) методом искусственного базиса включает следующие основные этапы: Для решения задач линейного программирования онлайн, пользуйтесь калькулятором Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам и обращающие в максимум линейную функцию этих переменных Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении. Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение. Всегда ли эта задача имеет решение? Нет, не всегда. ЗЛП неразрешима (не имеет оптимального решения): Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1. Рисунок 1 - Несовместность системы ограничений Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2. Рисунок 2 - Неограниченность целевой функции на множестве решений ЗЛП разрешима: Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3. Рисунок 3 - Множество решений состоит из одной точки Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4. Рисунок 4 - Единственное оптимальное решение Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5. Рисунок 5 - Оптимальное решение не единственно Симплекс-метод - алгоритм решения задачи ЛП, реализующий перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции С. Симплекс-метод является основным в линейном программировании. Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами: Метод является универсальным, применимым к любой задаче линейного программирования в канонической форме; Алгоритмический характер метода позволяет успешно программировать и реализовать его с помощью технических средств. Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если «да», то задача решена. Если «нет», то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции . Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен, то возможно выбрать неизвестных, которые выражают через остальные неизвестные. Для определенности обычно полагают, что выбраны первые, идущие подряд, неизвестные. Эти неизвестные (переменные) называются базисными, остальные свободными. Количество базисных переменных всегда равно количеству ограничений. Присваивая определенные значения свободным переменным, и вычисляя значения базисных (выраженных через свободные), получают различные решения системы ограничений. Особый интерес представляют решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Оно соответствует всем ограничениям. Имея систему ограничений, находят любое базисное решение этой системы. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении линейная форма если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным. Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, пока на каком-то шаге решения базисное решение окажется допустимым, либо можно сделать вывод о противоречивости системы ограничений. Таким образом, применение симплексного метода распадается на два этапа: Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; Нахождение оптимального решения в случае совместности системы ограничений. Алгоритм перехода к следующему допустимому решению следующий: В строке коэффициентов целевой функции выбирается наименьшее отрицательное число при отыскании максимума. Порядковый номер коэффициента - . Если такового нет, то исходное базисное решение является оптимальным; Среди элементов матрицы с номером столбца (этот столбец называется ведущим, или разрешающим) выбираются положительные элементы. Если таковых нет, то целевая функция неограничена на области допустимых значений переменных и задача решений не имеет; Среди выбранных элементов ведущего столбца матрицы выбирается тот, для которого величина отношения соответствующего свободного члена к этому элементу минимальна. Этот элемент называется ведущим, а строка, в которой он находится - ведущей; Базисная переменная, отвечающая строке ведущего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу ведущего элемента, вводится в число базисных. Строится новое решение, содержащее новые номера базисных переменных. Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов . Управление производством предполагает постоянное принятие решений. Каждое принятое решение выбирается из определенного множества допустимых альтернатив. Задача менеджмента в данном случае состоит в том, чтобы выбрать оптимальное решение, то есть то решение, которое по определенным признакам предпочтительнее остальных. Решение будет считаться оптимальным, если оно приведет к максимально возможному положительному эффекту (например, росту прибыли предприятия).
Одним из методов, позволяющих найти оптимальное решение среди всего множества допустимых решений, является исследование операций
. Исследование операций — один из разделов прикладной математики, суть которого заключается в поиске максимума (минимума) целевой функции, с учетом всех имеющихся ограничений. Суть экономики предприятия
заключается в максимизации прибыли, с учетом ограниченности ресурсов, которыми располагает организация. Этим обусловлена применимость методов исследования операций в решении задач организации производственного процесса на предприятии. В экономике предприятия такие задачи называются задачами распределения ресурсов
(или задачами оптимизации
). Рассмотрим пример, как можно применять методы исследования операций для решения производственных задач и как можно ускорить данный процесс путем применения встроенных возможностей MS Excel
. Предположим, автосервисное предприятие разработало для клиентов сезонные стимулирующие акции, суть которых заключается в том, что клиент, заплатив фиксированную сумму, получает целый пакет услуг по подготовке автомобиля к летнему сезону. Всего клиентам предложено два вида пакетов услуг
: 1) пакет «Чистое стекло
» стоимостью 3600 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, очистка внутренней поверхности стекол автомобиля с применением специального спрея (плюс один флакон спрея в подарок); заливка в омывательный бачок стеклоочищающей жидкости (плюс одна бутыль стеклоочищающей жидкости в подарок); 2) пакет «Свежий воздух
» стоимостью 4300 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, включая работы по очистке и дезинфекции кондиционера автомобиля с применением специального средства; очистка внутренней поверхности стекол автомобиля с применением специального спрея; заливка в омывательный бачок стеклоочищающей жидкости. В табл. 1 представлен комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов). Таблица 1. Комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов)
Работа
Пакет
«Чистое стекло»
Пакет
«Свежий воздух»
Проверка уровня моторного масла Проверка уровня и плотности охлаждающей жидкости Проверка уровня тормозной жидкости Проверка состояния салонного фильтра Визуальный контроль герметичности агрегатов Визуальная проверка состояния тормозных дисков и колодок Проверка тормозной системы на испытательном стенде Корректировка давления в шинах Функциональная проверка стеклоочистителей и стеклоомывателей Проверка резиновых щеток стеклоочистителя на износ и наличие трещин Проверка состояния радиатора охлаждения на предмет загрязнения Проверка и корректировка фар Проверка заряда аккумуляторной батареи Короткий тест с помощью диагностической программы Очистка и дезинфекция кондиционера Итого
Таким образом, данные два пакета услуг отличаются друг от друга тем, что в первый пакет дополнительно входит подарок в виде одного флакона спрея для внутренней очистки стекол и одной бутыли стеклоочищающей жидкости, а во второй — проведение работ по очистке и дезинфекции кондиционера с применением специального средства. Проведение сезонных акций позволяет предприятию решить целый ряд задач
: 1. Привлечение клиентов. 2. Сбыт залежавшихся сезонных товаров (автохимия). 4. Получение дополнительной прибыли. По задумке менеджмента организации, количество пакетов ограничено
: во-первых
, акция будет продолжаться до тех пор, пока не кончатся складские остатки участвующей в акции автохимии; во-вторых
, срок проведения акции органичен одним месяцем (апрелем); в-третьих
, на выполнение сервисных мероприятий могут быть задействованы только четыре механика. Таким образом, ресурсы, выделяемые на проведение данной акции, ограничены. Ограничения по ресурсам на проведение сезонной акции представлены в табл. 2. Таблица 2. Ограничения по ресурсам на проведение сезонной акции
Задействованные ресурсы
Расход ресурсов
Запас
ресурсов
пакет
«Чистое стекло»
пакет
«Свежий воздух»
Работа механика, ч Спрей для очистки внутренней поверхности стекла, уп. Стеклоомывающая жидкость, уп. Жидкость для очистки и дезинфекции кондиционера, уп. На проведение сезонной акции может быть выделено не более
: К тому же ограничено время работы механиков: в апреле 22 рабочих дня, продуктивный рабочий день механика — 7 ч в день. Следовательно, располагаемый фонд рабочего времени четырех механиков равен 616 ч (4 × 22 × 7). Всего на один пакет «Чистое стекло
» необходимо затратить: На пакет «Свежий воздух
» необходимо затратить: Ограничение по ресурсам является одним из условий задачи исследования операций. Характерной особенностью
исследования операций является системный подход. В связи с этим существующие ограничения по ресурсам можно представить в виде системы уравнений. Для начала введем обозначения для переменных нашей задачи: X
1 — количество пакетов «Чистое стекло»; Х
2 — количество пакетов «Свежий воздух»; A
— количество часов механика; B
— количество флаконов спрея для внутренней очистки стекол; C
— количество бутылей стеклоомывающей жидкости; D
— количество бутылей жидкости для очистки и дезинфекции кондиционеров. 1) во-первых, количество пакетов не может быть отрицательным: Х1, Х2 ≥ 0; 2) во-вторых, расход ресурсов не должен превышать имеющиеся запасы. Это можно выразить при помощи неравенств: по ресурсу А
: 2,5 × Х
1 + 3,6 × Х
2 ≤ 616; по ресурсу В
: 2 × Х
1 + 1 × Х
2 ≤ 320; по ресурсу С
: 2 × Х
1 + 1 × Х
2 ≤ 260; по ресурсу D
: 0 × Х
1 + 1 × Х
2 ≤ 150. Затем следует определиться с целевой функцией
(направлением для оптимизации). Логично было бы распределить квоту на оказание пакетов услуг таким образом, чтобы предприятие получило максимальную прибыль. Для этого нужно рассчитать, сколько прибыли приносит продажа одного пакета услуг, то есть сопоставить цену реализации пакета и стоимость затрачиваемых ресурсов. Как уже говорилось выше, стоимость пакета «Чистое стекло» составляет 3600 руб., а пакета «Свежий воздух
» — 4300 руб. Данные суммы необходимо сопоставить с затратами на выполнение услуг
: тарифная часовая ставка механика составляет 350 руб. за нормо-час (включая налоги и взносы с ФОТ); стоимость флакона жидкости для очистки внутренней поверхности стекла — 661 руб.; стоимость бутыли стеклоочищающей жидкости — 250 руб.; стоимость бутыли жидкости для очистки и дезинфекции кондиционеров — 1589 руб. Расчет прибыли от реализации каждого из пакетов на основании имеющихся данных представлен в табл. 3. Таблица 3. Прибыль от реализации пакетов услуг, руб.
Ресурс
Цена ресурса
Пакет
«Чистое стекло»
Пакет
«Свежий воздух»
Затраты на оплату труда механика Затраты на спрей для очистки стекол Затраты на стеклоомывающую жидкость Затраты на жидкость для очистки и дезинфекции кондиционера Итого затраты на пакет
Стоимость пакета
Прибыль от продажи пакета
Итак, продажа одного пакета «Чистое стекло
» принесет предприятию 903 руб. прибыли, а пакета «Свежий воздух
» — 540 руб. Целевая функция
(Z
) в данном случае примет вид. В технике оптимальный
(вариант, решение, выбор и т. д.) - наилучший (вариант, решение, выбор, …) среди допустимых при наличии правила предпочтения одного другому. Такое правило называется критерием оптимальности , а мерой предпочтения будут служить показатели качества . Можно говорить об оптимальном варианте только при удовлетворении двух условий: Каждый выбор лучшего варианта конкретен, поскольку производится на соответствие определённым критериям. Следовательно, говоря об оптимальном варианте, всегда нужно указывать эти критерии (то есть «оптимальный по …»). И то, что может быть оптимальным при одном критерии, не обязательно будет таковым при другом. Например, сцена, «оптимальная по площади», не обязательно будет «оптимальной по акустике». Оптимальное решение является результатом одного из видов выбора (критериального выбора). Изучением проблем, связанных с выбором оптимальных решений, занимаются теория исследования операций и теория принятия решений . Wikimedia Foundation
.
2010
.
Оптимальное решение
- решение, которое минимизирует или максимизирует (в зависимости от характера задачи) критерий качества оптимизационной модели (критерий оптимальности) при заданных условиях и ограничениях, представленных в этой модели. Но… … Экономико-математический словарь
оптимальное решение
- Решение, которое минимизирует или максимизирует (в зависимости от характера задачи) критерий качества оптимизационной модели (критерий оптимальности) при заданных условиях и ограничениях, представленных в этой модели. Но поскольку модель никогда… … Справочник технического переводчика
Оптимальное управление
- Оптимальное управление это задача проектирования системы, обеспечивающей для заданного объекта управления или процесса закон управления или управляющую последовательность воздействий, обеспечивающих максимум или минимум заданной… … Википедия
решение
- вынести новое решение действие вынести решение действие выносить решение действие выполнять решение реализация ждать решения модальность, ожидание зависит решение субъект, зависимость, причина следствие заниматься решением действие … решение
- сущ., с., употр. часто Морфология: (нет) чего? решения, чему? решению, (вижу) что? решение, чем? решением, о чём? о решении; мн. что? решения, (нет) чего? решений, чему? решениям, (вижу) что? решения, чем? решениями, о чём? о решениях 1. Решением … Толковый словарь Дмитриева
оптимальное
- найти оптимальное решение существование / создание … Глагольной сочетаемости непредметных имён
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПОЗИЦИОННОЕ
- решение задачи оптимального управления математической теории, состоящей в синтезе оптимального управления в виде стратегии управления по принципу обратной связи, как функции текущего состояния (позиции) процесса (см. ). Последнее… … Математическая энциклопедия
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПРОГРАММНОЕ
- решение задачи оптимального управления математической теории, в к рой управляющее воздействие u=u(t).формируется в виде функции времени (тем самым предполагается, что по ходу процесса никакой информации, кроме заданной в самом начале, в систему… … Математическая энциклопедия
Оптимальное планирование
- совокупность методов и средств, позволяющих выбрать из множества возможных вариантов развития экономической системы вариант, обеспечивающий наиболее эффективное использование ресурсов. Основу оптимального планирования составляет решение задачи… … Финансовый словарь
Оптимальное управление
- летательным аппаратом раздел динамики полёта, посвящённый развитию и использованию методов оптимизации для определения законов управления движением летательного аппарата и его траекторий, обеспечивающих максимум или минимум выбранного критерия… … Энциклопедия техники
задачи x j (j = 1,2 ,…, п) ставится в соответствие добавочная переменная , введенная в j - e неравенство двойственной задачи, а каждой добавочной переменной исходной задачи (i =
1,2,…,
т), введенной в i
- e неравенство исходной задачи, – первоначальная переменная двойственной задачи.
(1)
(2)
(3)
Метод искусственного базиса
называются искусственными
. Векторы столбцы
(28)
расширенной задачи (24)−(26) значения искусственных переменных 
, то 
является оптимальным планом задачи (21)−(23).
не станут неотрицательными. При этом, если искусственные переменные исключены из базиса, то найденный план расширенной задачи отвечает некоторому опорному плану исходной задачи.
Решение задач линейного программирования симплекс-методом
Примечания
Смотреть что такое "Оптимальное решение" в других словарях:
Книги