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

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

Пусть задача линейного программирования задана в общем виде, т.е. системой 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,…,т означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная .

Установим следующее соответствие между переменными в исход­ной и двойственной задачах:

Иными словами, каждой первоначальной переменной исходной
задачи x j (j = 1,2 ,…, п) ставится в соответствие добавочная переменная , введенная в j - e неравенство двойственной задачи, а каждой добавочной переменной исходной задачи (i = 1,2,…, т), введенной в i - e неравенство исходной задачи, – первоначальная переменная двойственной задачи.

Теорема 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 ТРАНСПОРТНАЯ ЗАДАЧА

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1. В решении каких производственно-экономических проблем используются методы линейного программирования

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

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

1. Графически могут решаться:

Задачи, заданные в стандартной форме, содержащие не более двух переменных;

Задачи, заданные в канонической форме с числом свободных переменных (r - ранг матрицы системы ограничений);

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

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

3. Методика решения задач ЛП графическим методом

I.В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства. Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI.При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора, при поиске минимума ЦФ - против направления вектора. Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.

4 . Как построить первоначальный опорный план задачи ЛП в симплексном методе и проверить его оптимальность

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

5 . Как определить переменную (вектор) для включения в базис и переменную (вектор) подлежащую исключению из базиса

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

Симплексное отношение (Q) = Элементы столбца свободных членов

Соответствующие элементы разрешающего столбца

Значения симплексного отношения заносятся в таблицу.

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

6 . Какой метод решения систем линейных уравнений лежит в основе симплекс-метода

Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана - Гаусса для системы линейных уравнений канонической формы, в которой должна быть предварительно записана исходная ЗЛП; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

7. Опишите алгоритм симплекс-метода

Схема решения задачи линейного программирования симплексным методом состоит из следующих основных этапов. 1. Математическая формализация задачи; 2. Приведение системы ограничений к каноническому виду; 3. Поиск опорного решения и нахождение базиса задачи; 4. Построение первой симплексной таблицы; 5. Проверка плана на оптимальность; 6. Последовательное улучшение плана до получения оптимального.

8. Опишите правила построения двойственной задачи ЛП

Правила построения двойственных задач:

Упорядочивается запись исходной задачи (если целевая функция максимизируется, то ограничения неравенства должны быть вида <= если минимизируется то >=), выполнение этих условий достигается умножением соответствующих ограничений на -1.Если прямая задача решается на максимум то двойственная на минимум, и на оборот. К каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот. Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи транспонированием.Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной и наоборот Если на переменную прямой задачи наложено условие не отрицательности то соответствующее ограничение двойственной задачи записывается как ограничение неравенства, если же нет то как ограничение равенства. Если какое либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие не отрицательности не налагается.

9 . Какова экономическая интерпретация двойственных оценок

С экономической точки зрения двойственную задачу можно интерпретировать так:

какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C j минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции x j (j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2,…, n) единицы продукции и размерах имеющихся ресурсов b i (i =1,2,…, n) максимизировать выпуск продукции в стоимостном выражении.

1 0 . Каким образом определяются двойственные оценки из последней симплексной таблицы

Чтобы найти решение двойственной задачи, сначала находим решение исходной задачи методом искусственного базиса. Из последней симплекс-таблицы видно, что двойственная задача имеет решение.

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

Некоторое предприятие производит n типов продукции, затрачивая при этом m типов ресурсов. Известны следующие параметры: aij - количество i-го ресурса, необходимое для производства единичного количества j-й продукции; aij0 (i=1,…,m; j=1,…,n);

bi-запас i-го ресурса на предприятии, bi>0;

cj-цена единичного количества j-й продукции, cj>0.

Предполагается, что затраты ресурсов растут прямо пропорционально объему производства. Пусть xj - планируемый объем производства j-й продукции. Тогда допустимым является только такой набор производимой продукции x=(x1,x2,…,xn), при котором суммарные затраты каждого вида i-го ресурса не превосходят его запаса:

Кроме того, имеем следующее ограничение: xj0; j=1,…,n. (2)

Стоимость набора продукции x выражается величиной: (3)

Задача планирования производства ставится следующим образом: среди всех векторов x, удовлетворяющим ограничениям (1), (2), найти такой, при котором величина (3) принимает наибольшее значение.

1 2 . Сформулируйте задачу оптимального состава смеси и запишите ее в виде модели ЛП

Пусть имеется m видов сырья, запасы которого составляют соответственно d1,…, dm. Из этого сырья необходимо составить смесь, содержащую n веществ, определяющих технические характеристики смеси. Известны величины aij (i =1,m; j =1, n) ,определяющие количество j-го вещества в единице i -го вида сырья, цена которого равна сi (i = 1,m), а также b j (j = 1,n) ?наименьшее допустимое количество j-го вещества в смеси.

Требуется получить смесь с заданными свойствами при наименьших затратах на исходные сырьевые материалы.

Цель задачи (целевая функция) - минимизировать суммарные затраты на сырье.

Найти вектор X = (x 1 , x 2, …, x n), удовлетворяющий системе ограничений:

и доставляющий целевой функции минимальное значение.

1 3 . Сформулируйте транспортную задачу ЛП и запишите ее модель

Транспортная задача (transportation problem) - одна из наиболее распространенных задач математического программирования (обычно - линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям и наоборот. В простейшем виде, когда распределяется один вид продукта и потребителям все равно, от кого из поставщиков его получать, задача формулируется следующим образом.

Исходная информация:

Mi - количество единиц груза в i-м пункте отправления (i = 1, 2, …, k);

Nj - потребность в j-м пункте назначения (j = 1, 2, …, l) (в единицах груза);

aij - стоимость перевозки единицы груза из i-гo пункта в j-й.

Обозначим через xij планируемое количество единиц груза для перевозки из i-ro пункта в j-й.

В принятых обозначениях:

Общая (суммарная) стоимость перевозок;

Количество груза, вывозимого из i-ro пункта;

Количество груза, доставляемого в j-и пункт.

В простейшем случае должны выполняться следующие очевидные условия:

Таким образом, математической формулировкой транспортной задачи будет:

при условиях:

Эта задача носит название замкнутой (закрытой, сбалансированной) транспортной модели. Заметим, что условие является естественным условием разрешимости замкнутой транспортной задачи.Более общей транспортной задачей является так называемая открытая (несбалансированная) транспортная модель:

при условиях:

1 4 . Какие модели транспортной задачи называются открытыми и как преобразовать открытую модель в закрытую?

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы в пунктах отправления были равны потребностям в грузе в пунктах назначения. Если условие баланса выполняется, то модель транспортной задачи называется закрытой. Если условие баланса не выполняется, то модель транспортной задачи называется открытой. Чтобы получить закрытую модель, вводят дополнительную (фиктивную) базу с запасом недостающего груза.

Если, в модель вводится фиктивный (m+1)-й поставщик, для которого запас груза равен разности между суммарным спросом потребителей и фактическим запасом поставщиков. Все тарифы на доставку груза от фиктивного поставщика считают равным 0: . В транспортную таблицу добавляется одна строка.

В модель вводится фиктивный (n+1)-й потребитель, для которого потребность равна разности между суммарным запасом поставщиков. Все тарифы на доставку груза с фиктивными потребностями считают равными 0: . В транспортную таблицу добавляется один столбец.

15 . Метод потенциалов

Широко распространенным методом решения транспортных задач является метод потенциалов. Если допустимое решение (i=1,2,…,m; j=1,2,…n) транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков (i=1,2,…,m)и потребителей (j=1,2,…,n). Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные. Алгоритм решения транспортных задач методом потенциалов:

а) проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок. b) построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1) и убедиться в линейной независимости векторов условий (используется метод вычеркивания). c) построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений, которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам. d) проверить выполнения условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам и те из них, которые больше нуля, записываются в левые нижние углы клеток. Если для всех свободных клеток, то вычисляют значение целевой функции и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, опорное решение не является оптимальным.

e) перейти к опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка. Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину. Клетка со знаком «-», в которой достигается остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным. Далее перейти к пункту 3 данного алгоритма.

МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ

1. Каковы цели применения методов СПУ? Охарактеризуйте область применения сетевых методов в с фере экономики

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

Система СПУ позволяет:

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

2. Что представляет собой сетевой график?

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

3. Что понимается под терминами работа и события, каки е разновидности работ Вы знаете ?

Сетевые модели состоят из трех следующих элементов:

Работа (или задача) Событие (вехи) Связь (зависимость)

Работа (Activity) - это процесс, который необходимо выполнить для получения определенного (заданного) результата, как правило, позволяющего приступить к последующим действиям. Термины "задача" (Task) и "работа" могут быть идентичны, однако в некоторых случаях задачами принято называть выполнение действий, выходящих за рамки непосредственного производства, например "Экспертиза проектной документации" или "Переговоры с заказчиком". Иногда понятие "задача" используют для отображения работ самого низкого уровня иерархии. Событие (Node) - момент изменения состояния системы, в частности, момент начала или окончания любой работы по своей сути является событием, а каждая работа обязательно имеет начальное и конечное события. Работа - это действие или процесс, которые должны произойти для перехода от начального события к конечному. Некоторые события являются общими для нескольких работ, в этом случае свершение события является моментом времени, соответствующим завершению последней из работ, непосредственно предшествующих данному событию. Веха (Milestone) - разновидность события, характеризующая достижение значимых промежуточных результатов (отдельных этапов проекта). Связь (Link) - это логическая зависимость между сроками выполнения отдельных работ и наступления событий. Если для начала выполнения какой-либо работы необходимо завершение другой работы, говорят, что эти работы соединены связью (связаны). Связи по своему существу могут определяться технологией работ, либо их организацией. Соответственно различают технологические и организационные виды связей. Связи могут называться также зависимостями (Relationship), или фиктивными работами (Dummy Activity). Связям не требуются исполнители и прямые затраты времени, однако они могут характеризоваться продолжительностью растяжения (положительным, отрицательным или нулевым).

4. Опишите основные требования, которым долж ен удовлетворять сетевой график

При построении сетевого графика необходимо соблюдать ряд правил.

1. В сетевой модели не должно быть «тупиковых» событий, то есть событий, из которых не выходит ни одна работа, за исключением завершающего события. Здесь либо работа не нужна и её необходимо аннулировать, либо не замечена необходимость определённой работы, следующей за событием для свершения какого-либо последующего события. В таких случаях необходимо тщательное изучение взаимосвязей событий и работ для исправления возникшего недоразумения.

2. В сетевом графике не должно быть «хвостовых» событий (кроме исходного), которым не предшествует хотя бы одна работа. Обнаружив в сети такие события, необходимо определить исполнителей предшествующих им работ и включить эти работы в сеть.

3. В сети не должно быть замкнутых контуров и петель, то есть путей, соединяющих некоторые события с ними же самими. При возникновении контура (а в сложных сетях, то есть в сетях с высоким показателем сложности, это встречается довольно часто и обнаруживается лишь при помощи ЭВМ) необходимо вернуться к исходным данным и путём пересмотра состава работ добиться его устранения.

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

5. Как определяются временные оценки работ и событий?

Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы Р i,j , состоящий из номеров начального (i-го) и конечного (j-го) событий (рис.1, а). На рис.1, б изображен пример кодирования работ и событий в принятых обозначениях: t ij - продолжительность работы Р i,j , t - ранний срок (ожидаемый момент) осуществления события, t * - поздний срок (предельный момент) осуществления события, n - номер события, n см - номер предшествующего (смежного) события.

Рис.1. Обозначение элементов сетевого графика: а - код работы; б - пример кодирования событий в принятых обозначениях; в - пример изображения события в принятых выше обозначениях.

На рис.1 в приведён пример изображения события в принятых выше обозначениях. Обозначим через множество работ, входящих в j-е событие, а через - множество работ, выходящих из i-го события. Ранний срок (ожидаемый момент) осуществления j-го события представляет собой момент времени, раньше которого событие произойти не может и рассчитывается по формуле

Поздний срок (предельный момент) осуществления i-го события показывает максимальную задержку во времени наступления данного события:

6. Раскройте содержание, метод определения и значение критического пути в моделях сетевого планирования

Критический путь - последовательность работ между начальными и конечными событиями сети, имеющих наибольшую продолжительность во времени. Минимальное время, необходимое для выполнения проекта, запланированного сетевым графиком, равно длине критического пути. Сетевой график может содержать не один, а несколько критических путей. Критическими называются также работы и события, расположенные на этом пути. Резервный интервал от t до t* для событий, лежащих на критическом пути, равен 0. Для завершающего события сетевого графика поздний срок свершения события должен равняться его раннему сроку, т. е. t п = t* п. Длина критического пути равна раннему сроку свершения завершающего события, т. е. t кр = t п = t* п.

ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

1. Какие системы исследуются при помощи теории массового обслуживания?

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

2. Привидите примеры систем массового обслуживан ия в экономике, на производстве

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

3. Как классифицируются системы массового обслуживания?

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

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

4. Какими чертами обладает простейший поток?

Простейший поток обладает такими важными свойствами:

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

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

3) Свойством ординарности, которое выражает практическую невозможность одновременного поступления двух или более требований (вероятность такого события неизмеримо мала по отношению к рассматриваемому промежутку времени, когда последний устремляют к нулю).

При простейшем потоке требований распределение требований, поступающих в систему подчиняются закону распределения Пуассона:

вероятность того, что в обслуживающую систему за время t поступит именноk требований:

где. - среднее число требований, поступивших на обслуживание в единицу времени.

5. Какое распределение обычно имеет время обслуживания?

Одной из важнейших характеристик обслуживающих устройств, которая определяет пропускную способность всей системы, является время обслуживания. Время обслуживания одного требования()- случайная величина, которая может изменятся в большом диапазоне. Она зависит от стабильности работы самих обслуживающих устройств, так и от различных параметров, поступающих в систему, требований (к примеру, различной грузоподъемности транспортных средств, поступающих под погрузку или выгрузку). Случайная величина полностью характеризуется законом распределения, который определяется на основе статистических испытаний.

На практике чаще всего принимают гипотезу о показательном законе распределения времени обслуживания.

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

При показательном законе распределения времени обслуживания вероятность события, что время обслуживания продлиться не более чем t, равна:

гдеv - интенсивность обслуживания одного требования одним обслуживающим устройством, которая определяется из соотношения:

где- среднее время обслуживания одного требования одним обслуживающим устройством.

Следует заметить, что если закон распределения времени обслуживания показательный, то при наличии нескольких обслуживающих устройств одинаковой мощности закон распределения времени обслуживания несколькими устройствами будет также показательным:

где n - количество обслуживающих устройств.

6. Какое практическое применение имеет теория массового обслуживания при анализе функционирования подразде лений производства?

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

МОДЕЛИ МЕЖОТРАСЛЕВОГО БАЛАНСА

1. Область применения межотрас левых и межпродуктовых балансов

Межотраслевой баланс (МОБ, метод «затраты-выпуск») -- экономико-математическая балансовая модель, характеризующая межотраслевые производственные взаимосвязи в экономике страны. Характеризует связи между выпуском продукции в одной отрасли и затратами, расходованием продукции всех участвующих отраслей, необходимым для обеспечения этого выпуска. Межотраслевой баланс составляется в денежной и натуральной формах.

2. Что показывает и отражают балансовые модели?

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

3. Дайте характерис тику разделов балансовой модели

В схеме МОБ по методологии СНС, как и в известной открытой статистической модели, выделяются три основные части (квадранты): внутренний (или первый) квадрант (I); боковое (или правое) крыло (II квадрант); нижнее крыло (III квадрант). IV квадрант не разрабатывается. Общая схема МОБ имеет следующий вид:

Внутренний (или первый) квадрант (I) характеризует взаимосвязи отраслей, отражает промежуточное потребление; во II квадранте приводится структура конечного использования валового внутреннего продукта (ВВП); в III квадранте показывается структура валовой добавленной стоимости по элементам. В I квадранте («шахматная таблица») по строкам и колонкам записываются отрасли экономики. В колонках I квадранта по каждой отрасли представлены затраты на производство продукции, работ, услуг (стоимость сырья, материалов, топлива, энергии, услуг), а по строкам показывается, как распределяется продукция каждой отрасли между всеми отраслями. В правой части МОБ (// квадрант) строки соответствуют отраслям-потребителям. Колонки представляют собой категории конечного использования: конечное потребление (расходы на конечное потребление домашних хозяйств, государственного управления и некоммерческих организаций, обслуживающих домашние хозяйства), валовое накопление (валовое накопление основного капитала, изменение запасов материальных оборотных средств, чистое приобретение ценностей), сальдо экспорта-импорта товаров и услуг. В III квадранте представлена стоимостная структура ВВП. Колонки III квадранта соответствуют отраслям-производителям, а строки -- основным стоимостным компонентам валовой добавленной стоимости (оплата труда наемных работников, валовая прибыль, валовой смешанный доход, налоги и субсидии, связанные с производством) и налогам и субсидиям на продукты. Таким образом, если рассматривать данные МОБ по вертикали, то по колонкам показывается стоимостная структура выпуска продукции отдельных отраслей, который состоит из промежуточного потребления (I квадрант) и валовой добавленной стоимости (III квадрант), а по горизонтали -- по строкам -- натурально-вещественный состав продукции, которая расходуется на промежуточное потребление (I квадрант) и конечное использование (II квадрант). Для каждой отрасли экономики ресурсы продуктов равны их использованию.Четвертый раздел располагается под вторым. Он характеризует перераспределительные отношения в экономике, осуществляемые через финансово-кредитную систему. В плановых расчетах четвертый раздел, как правило, не используется, и поэтому в пределах нашего курса рассматриваться не будет.

4 . Дайте характеристику методов формирования коэффициентов прямых затрат в балансовых моделях. Как вычисляются эти коэффициенты?

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

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

где Xij и Xj взяты из отчетного баланса.

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

Определив коэффициенты аij, можно использовать систему (4) для решения сформулированных выше задач 1 - 3.

Технологические коэффициенты аij обладают следующими свойствами:

ИГРОВЫЕ МОДЕЛИ В ЭКОНОМИКЕ

1. Какие причины вызывают неопределенность результатов игры?

Выделяют следующие группы причин возникновения неопределенности и вызванного ею риска: индетерминированность многих процессов и явлений, которые влияют на экономику (НТП, стихийного бедствия, поведение конкурентов и потребителей); неполнота, неточность и противоречивость информации, которые вызваны, как техническими затруднениями при получении и обработке, так и сугубо экономическими причинами - слишком большими затратами на получение информации, которые превышают возможные выгоды от владения ею.

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

2. Как определить нижнюю и верхнюю цену матричной игры и какое соотношение существует между ними?

Рассмотрим игру m Ч n с матрицей и определим наилучшую среди стратегий A 1 , A 2 , …, А m . Выбирая стратегию А i игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий B j , для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).Обозначим через б наименьший выигрыш игрока А при выборе им стратегии А; для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы).Назовем б нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию B j , он учитывает максимально возможный при этом выигрыш для А. Назовем В верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно, .

Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры б = в = н называется чистой ценой игры, или ценой игры.

3. Сформулируйте основн ую теорему теории матричных игр

Основная теорема теории Матричные игры (теорема Неймана о минимаксе) утверждает, что в любой Матричные игры существуют оптимальные смешанные стратегии х*, у*, на которых достигаемые «минимаксы» равны (общее их значение есть значение игры).

Или Для матричной игры с любой матрицей А величины и равны между собой, т.е.

Более того, существует хотя бы одна ситуация в смешанных стратегиях, для которой выполняется соотношение

4.Какие существуют методы упрощения игр?

Первый метод, используемый для уменьшения размерности матрицы, основан на одном из важнейших понятий в теории игр - понятии доминирования стратегий.

Если i-я строка поэлементно не меньше (?) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B. Аналогично, если i-й столбец поэлементно не меньше (?) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (?), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры. Частный случай доминирования является дублирование стратегий . Если платёжная матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляем только одну строку, а остальные строки (столбцы) отбрасываем. Отброшенным стратегиям припишем нулевые вероятности.Упрощение (уменьшение размерности) платёжных матриц за счёт исключения заведомо невыгодных чистых стратегий возможно в силу справедливости следующей Теоремы о доминирующих стратегиях :

Пусть I - игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G - игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда:

1. цена игры I равна цене игры G;

2. оптимальная смешенная стратегия Q * = (q 1 * ,q 2 * ,…,q n *) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I;

3. если P * = (p 1 * ,p 2 * ,…,p i * , p* i+2 ,…, p m *) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P * = (p 1 * ,p 2 * ,…,p i * , p* i+2 ,…, p m *) является оптимальной в игре I.

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

5. Геометрические методы решения игр с матрицами 2_ _n и m 2 и их применение

Решение игры в смешанных стратегиях допускает наглядную геометрическую интерпретацию. Геометрический метод решения игры включает следующие этапы. 1. В декартовой системе координат по оси абсцисс откладывается отрезок А1А2, длина которого равна 1 (рис. 2.1.). Левый конец отрезка точка x = 0 соответствует стратегии A1, правый, где х = 1,0 -- стратегии А2. Все промежуточные точки этого отрезка соответствуют смешанным стратегиям S1 = (p1, p2). 2. По оси ординат от точки O откладываются выигрыши при стратегии А1. 3. На линии, параллельной оси ординат, от точки 1 откладываются выигрыши при стратегии А2 .Пусть имеется игра с платежной матрицей:

Если игрок II применяет стратегию В1, то выигрыш игрока I при использовании чистых стратегий А1 и А2 составляет соответственно a11 = 0,4 и a21 = 0,6. Соединим эти точки прямой В1В1 . Если игрок I при стратегии В1 применяет смешанную стратегию, то средний выигрыш, определяемый по формуле математического ожидания g1 = a11p1 + a21p2, изображается ординатой точки N на прямой B1B1. Прямая B1B1 называется стратегией В1. Ордината любой точки отрезка B1B1 равна величине выигрыша игрока I при применении им стратегии A1 и А2 с соответствующими вероятностями p1 и p2.Аналогично строим отрезок В2В2, соответствующий применению игроком II стратегии В2 .Ординаты точек отрезка определяют средний стратегий А1 и А2 с соответствующими вероятностями p1 и p2 и равных g2 = a12p1 + a22p2.

6. На чем основана связь матричной игры и задачи линейного программирования?

Первоначально развитие теории стратегических матричных игр осуществлялось параллельно и независимо от линейного программирования. Позже было установлено, что стратегическая матричная игра может быть сведена к паре двойственных задач линейного программирования. Решив одну из них, получаем оптимальные стратегии игрока 1; решив другую, получаем оптимальные стратегии игрока 2. Математическое соответствие между стратегическими матричными играми и линейным программированием было установлено Дж. Б. Данцигом, сформулировавшим и доказавшим в 1951 г. основную теорему теории игр.

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число v и такие стратегии U* и W* игроков 1 и 2 соответственно, что выполняются неравенства:

Поясним смысл доказываемых неравенств: если игрок 1 отклоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей оптимальной стратегии отклоняется игрок 2, то по сравнению с ценой игры его проигрыш не уменьшается.

7. В чем состоит отличие игры с природой?

Отличительная особенность игры с природой состоит в том, что в ней сознательно действует только один из участников, в большинстве случаев называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные «ходы» партнер по игре. Поэтому термин «природа» характеризует некую объективную действительность, которую не следует понимать буквально, хотя вполне могут встретиться ситуации, в которых «игроком» 2 действительно может быть природа (например, обстоятельства, связанные с погодными условиями или с природными стихийными силами).

8. Перечислите основные критерии решения игр с природой и каковы расчетные формулы для этих критериев.

Критерий Байеса .

По критерию Байеса за оптимальные принимается та стратегия (чистая) A i , при которой максимизируется средний выигрыш a или минимизируется средний риск r.

Считаем значения?(a ij p j)

Критерий Лапласа .

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

q 1 = q 2 = ... = q n = 1/n.

Критерий Вальда .

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

a = max(min a ij)

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

Критерий Севиджа .

a = min(max r ij)

Критерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.

Критерий Гурвица .

Критерий Гурвица является критерием пессимизма - оптимизма. За (оптимальную принимается та стратегия, для которой выполняется соотношение:

где s i = y min(a ij) + (1-y)max(a ij)

При y = 1 получим критерий Вальде, при y = 0 получим - оптимистический критерий (максимакс).

Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.

Критерий максимакса .

Критерий максимакса ориентирует статистику на самые благоприятные состояния природы, т.е. этот критерий выражает оптимистическую оценку ситуации.

Практические задания

Задание № 1

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

Определим максимальное значение целевой функции F(X) = 2x 1 + 5x 2 + 6x 3 при следующих условиях-ограничений.

7x 1 + 8x 2 + 3x 3 ?81

4x 1 + x 2 + 6x 3 ?68

5x 1 + x 2 + 7x 3 ?54

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

В 1-м неравенстве смысла (?) вводим базисную переменную x 4 . В 2-м неравенстве смысла (?) вводим базисную переменную x 5 . В 3-м неравенстве смысла (?) вводим базисную переменную x 6 .

7x 1 + 8x 2 + 3x 3 + 1x 4 + 0x 5 + 0x 6 = 81

4x 1 + 1x 2 + 6x 3 + 0x 4 + 1x 5 + 0x 6 = 68

5x 1 + 1x 2 + 7x 3 + 0x 4 + 0x 5 + 1x 6 = 54

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

Решим систему уравнений относительно базисных переменных: x 4 , x 5 , x 6

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,81,68,54)

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x 3 , так как это наибольший коэффициент по модулю.

...

Подобные документы

Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.

курсовая работа , добавлен 05.10.2014


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

контрольная работа , добавлен 09.04.2012


Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.

контрольная работа , добавлен 04.05.2014


Симплекс-метод решения задач линейного программирования. Элементы теории игр. Системы массового обслуживания. Транспортная задача. Графоаналитический метод решения задач линейного программирования. Определение оптимальной стратегии по критерию Вальде.

контрольная работа , добавлен 24.08.2010


История создания средств цифровой вычислительной техники. Методы и модели линейного программирования. Экономическая постановка задачи. Выбор метода реализации задачи. Особенности выбора языка программирования. Решение задачи сетевым методом планирования.

курсовая работа , добавлен 19.02.2015


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

учебное пособие , добавлен 15.06.2015


Моделирование экономических систем: основные понятия и определения. Математические модели и методы их расчета. Некоторые сведения из математики. Примеры задач линейного программирования. Методы решения задач линейного программирования.

лекция , добавлен 15.06.2004


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

контрольная работа , добавлен 11.05.2014


Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.

курсовая работа , добавлен 02.10.2014


Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.

Управление производством предполагает постоянное принятие решений. Каждое принятое решение выбирается из определенного множества допустимых альтернатив. Задача менеджмента в данном случае состоит в том, чтобы выбрать оптимальное решение, то есть то решение, которое по определенным признакам предпочтительнее остальных. Решение будет считаться оптимальным, если оно приведет к максимально возможному положительному эффекту (например, росту прибыли предприятия).

Одним из методов, позволяющих найти оптимальное решение среди всего множества допустимых решений, является исследование операций . Исследование операций — один из разделов прикладной математики, суть которого заключается в поиске максимума (минимума) целевой функции, с учетом всех имеющихся ограничений. Суть экономики предприятия заключается в максимизации прибыли, с учетом ограниченности ресурсов, которыми располагает организация. Этим обусловлена применимость методов исследования операций в решении задач организации производственного процесса на предприятии. В экономике предприятия такие задачи называются задачами распределения ресурсов (или задачами оптимизации ).

Рассмотрим пример, как можно применять методы исследования операций для решения производственных задач и как можно ускорить данный процесс путем применения встроенных возможностей MS Excel .

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

1) пакет «Чистое стекло » стоимостью 3600 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, очистка внутренней поверхности стекол автомобиля с применением специального спрея (плюс один флакон спрея в подарок); заливка в омывательный бачок стеклоочищающей жидкости (плюс одна бутыль стеклоочищающей жидкости в подарок);

2) пакет «Свежий воздух » стоимостью 4300 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, включая работы по очистке и дезинфекции кондиционера автомобиля с применением специального средства; очистка внутренней поверхности стекол автомобиля с применением специального спрея; заливка в омывательный бачок стеклоочищающей жидкости.

В табл. 1 представлен комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов).

Таблица 1. Комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов)
Работа	Пакет «Чистое стекло»	Пакет «Свежий воздух»
Проверка уровня моторного масла
Проверка уровня и плотности охлаждающей жидкости
Проверка уровня тормозной жидкости
Проверка состояния салонного фильтра
Визуальный контроль герметичности агрегатов
Визуальная проверка состояния тормозных дисков и колодок
Проверка тормозной системы на испытательном стенде
Корректировка давления в шинах
Функциональная проверка стеклоочистителей и стеклоомывателей
Проверка резиновых щеток стеклоочистителя на износ и наличие трещин
Проверка состояния радиатора охлаждения на предмет загрязнения
Проверка и корректировка фар
Проверка заряда аккумуляторной батареи
Короткий тест с помощью диагностической программы
Очистка и дезинфекция кондиционера
Итого

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

Проведение сезонных акций позволяет предприятию решить целый ряд задач :

1. Привлечение клиентов.

2. Сбыт залежавшихся сезонных товаров (автохимия).

4. Получение дополнительной прибыли.

По задумке менеджмента организации, количество пакетов ограничено :

во-первых , акция будет продолжаться до тех пор, пока не кончатся складские остатки участвующей в акции автохимии;

во-вторых , срок проведения акции органичен одним месяцем (апрелем);

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

Таким образом, ресурсы, выделяемые на проведение данной акции, ограничены. Ограничения по ресурсам на проведение сезонной акции представлены в табл. 2.

Таблица 2. Ограничения по ресурсам на проведение сезонной акции
Задействованные ресурсы	Расход ресурсов		Запас ресурсов
	пакет «Чистое стекло»	пакет «Свежий воздух»
Работа механика, ч
Спрей для очистки внутренней поверхности стекла, уп.
Стеклоомывающая жидкость, уп.
Жидкость для очистки и дезинфекции кондиционера, уп.

На проведение сезонной акции может быть выделено не более :

• 320 флаконов спрея для очистки внутренней поверхности стекла;

• 260 бутылей стеклоомывающей жидкости;

• 150 бутылей жидкости для очистки и дезинфекции кондиционера.

К тому же ограничено время работы механиков: в апреле 22 рабочих дня, продуктивный рабочий день механика — 7 ч в день. Следовательно, располагаемый фонд рабочего времени четырех механиков равен 616 ч (4 × 22 × 7).

Всего на один пакет «Чистое стекло » необходимо затратить:

• 2,5 ч работы механика;

• 2 флакона спрея для очистки внутренней поверхности стекла (один использовать, один — в подарок);

• 2 бутыли стеклоомывающей жидкости (одну использовать, одну — в подарок).

На пакет «Свежий воздух » необходимо затратить:

• 3,6 ч работы механика;

• 1 флакон спрея для очистки внутренней поверхности стекла;

• 1 бутыль стеклоомывающей жидкости и одну бутыль жидкости для очистки и дезинфекции кондиционера.

Ограничение по ресурсам является одним из условий задачи исследования операций. Характерной особенностью исследования операций является системный подход. В связи с этим существующие ограничения по ресурсам можно представить в виде системы уравнений. Для начала введем обозначения для переменных нашей задачи:

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 ) в данном случае примет вид.

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

Концепция, утверждающая, что оптимальное решение есть функция факторов среды в самой организации (внутренние переменные) и окружающей  

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

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

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

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

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

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

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

Всякая претендующая на реализацию система экономического саморегулирования должна обеспечивать соблюдение ряда основных принципов социальной справедливости . Прежде всего (и это касается не только геологоразведки) необходимо сделать выбор основного принципа распределения равную оплату за равный труд или равную оплату за равные конечные результаты труда . Дело в том, что в геологии, как ни в какой другой отрасли, ввиду огромных различий естественной производительности труда в зависимости от экономико-географических, геологических и горнотехнических условий эквивалентное количество и качество труда объективно приводит к различным результатам. Поэтому внешне кажется, будто равная оплата за равный труд в этих условиях более справедлива. Ведь неравные условия труда созданы природой и не зависят от исполнителей. Однако этот принцип не стимулирует поиска оптимальных решений в выборе направлений и метода ведения работ. Наоборот, оплата за равные результаты труда максимально стимулирует прогресс, но при этом приведет к значительно большей дифференциации доходов как предприятий, так и отдельных трудящихся. Что предпочесть Нетрудно сформулировать следующее статистическое положение скорость научно-технического и хозяйственного прогресса тесно коррелирует с дифференциацией доходов . На повестку дня встает вопрос быть ли нам значительно более равными по доходам, но существенно беднее, или в среднем значительно богаче, но существенно дифференцированнее по доходам Впрочем, этот вопрос нельзя ставить как альтернативу между двумя крайними существует множество промежуточных положений, из которых можно выбрать подходящее, регулируя оставляемую в распоряжении ПГО долю дифференциальной ренты , образующейся за счет большей естественной производительности труда (дифференциальная рента I). Если эта доля будет существенной, геологоразведочные предприятия будут заинтересованы в проведении работ в первую очередь на объектах с лучшей естественной производительностью труда . Дифференциальную ренту II, по нашему мнению, необходимо целиком оставлять в распоряжении предприятия.  

Как известно, СЭВ осуществил значительную работу в порядке подготовки единого энергетического баланса стран - членов СЭВ на 1966-1970 гг. В этом документе сбалансированы объемы производства и потребления различных видов топлива и энергии, даны экономические расчеты, обосновывающие выбор наиболее оптимальных решений, приводится комплекс мероприятий, обеспечивающих успешную реализацию намеченных планов.  

Термины оптимизация и оптимальный ассоциируются с экономико-математическими методами (ЭММ) и ЭВМ, т. е. с методами и средствами, способствующими наиболее эффективному решению задач планирования и управления. Вместе с тем и в действующей практике, основанной на традиционных методах , руководитель любого уровня управления на предприятии также заинтересован в оптимальном решении вопроса по увеличению выпуска продукции , снижению затрат на производство, использованию капиталовложений и т. Д. Но он пытается этого достичь, пользуясь в основном установившимися принципами общих закономерностей и далеко не совершенными вычислительными средствами. При этом во многих случаях также рассматривается ряд вариантов, хотя и ограниченный, что обусловливается реальными организационными и техническими возможностями. Тем не менее в отдельных случаях не исключено совпадение результатов решения, полученных с использованием ЭММ и ЭВМ и на основе традиционного подхода.  

Упорядоченный перебор интересующих нас допустимых планов , нахождение допустимых планов требуют огромной вычислительной работы, которая осуществляется на ЭВМ. Симплекс-метод , согласно которому ЭВМ осуществляет упорядоченный перебор и находит оптимальное решение, является наиболее распространенным экономико-математическим методом.  

Способы решения любой проблемы всегда многовариантны. Они не сводятся к простой альтернативе "делать или не делать ". Возможный выбор здесь обычно гораздо более широк, хотя и не очевиден заранее. При этом наиболее выгодными нередко оказываются нетрадиционные, "прорывные" варианты решения проблемы . Обнаружение таких нетривиальных возможностей требует специальных, порой длительных, творческих усилий. Но именно такие варианты обычно дают наибольший экономический эффект . Умение находить нетрадиционные способы (варианты) решения поставленных задач - один из наиболее ярких показателей профессионального уровня руководителя и специалиста. А тщательное многовариантное рассмотрение возможностей является непременным условием отыскания оптимального решения любой достаточно сложной задачи. И нет большей и более досадной ошибки специалистов, принимающих ответственные решения, чем упустить действительно наивыгоднейший вариант просто из-за отсутствия привычки хорошенько подумать.  

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

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

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

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

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

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

В этой борьбе заслуживают быть особо отмеченными несколько ее характеристик. Во-первых, ее стопроцентно бескомпромиссный характер Рабочие осуществляют настолько жесткий контроль качества в процессе трудовых операций, что отпадает необходимость во входном контроле и деятельности органов, проверяющих изделия после их изготовления. Во-вторых, ее воздействие на характер отправления работниками своих функций Пребывание в группе (качества.- В. Р.) исключает формальное исполнение работником вмененных ему обязанностей. Только творческое отношение к самым обыденным, рутинным технологическим операциям способно обеспечить успех работника как члена группы качества . И только такое творческое отношение, активизация всех созидательных потенций работника позволяет обеспечить встроенность" высокого качества в производственный процесс , их нерушимый синтез. Одними, пусть и самыми совершенными, технологическими приемами такого синтеза невозможно добиться. В-третьих, миссия борьбы за качество как регулятора межличностных деловых контактов Ориентация (на консенсус.- В. Р.)... определяет и саму тональность обсуждения группой качества даже наиболее острых вопросов. Доброжелательный стиль дискуссии, при котором невозможны взаимные обвинения, личные выпады, наклеивание ярлыков, выявление правых" и виноватых", рассматривается как важное условие быстрого обнаружения оптимальных решений.  

Смотреть страницы где упоминается термин Оптимальное решение

:          c.184 ]

Это наилучшее средство для поиска информации на сайте

В технике оптимальный (вариант, решение, выбор и т. д.) - наилучший (вариант, решение, выбор, …) среди допустимых при наличии правила предпочтения одного другому. Такое правило называется критерием оптимальности , а мерой предпочтения будут служить показатели качества . Можно говорить об оптимальном варианте только при удовлетворении двух условий:

1. наличия хотя бы одного критерия,
2. наличия не менее двух сравниваемых вариантов (необходимость осуществления выбора).

Каждый выбор лучшего варианта конкретен, поскольку производится на соответствие определённым критериям. Следовательно, говоря об оптимальном варианте, всегда нужно указывать эти критерии (то есть «оптимальный по …»). И то, что может быть оптимальным при одном критерии, не обязательно будет таковым при другом. Например, сцена, «оптимальная по площади», не обязательно будет «оптимальной по акустике».

Оптимальное решение является результатом одного из видов выбора (критериального выбора). Изучением проблем, связанных с выбором оптимальных решений, занимаются теория исследования операций и теория принятия решений .

Примечания

Wikimedia Foundation . 2010 .

• Оптиконевромиелит
• Оптиматы (фема)

Смотреть что такое "Оптимальное решение" в других словарях:

Оптимальное решение - решение, которое минимизирует или максимизирует (в зависимости от характера задачи) критерий качества оптимизационной модели (критерий оптимальности) при заданных условиях и ограничениях, представленных в этой модели. Но… … Экономико-математический словарь

оптимальное решение - Решение, которое минимизирует или максимизирует (в зависимости от характера задачи) критерий качества оптимизационной модели (критерий оптимальности) при заданных условиях и ограничениях, представленных в этой модели. Но поскольку модель никогда… … Справочник технического переводчика

Оптимальное управление - Оптимальное управление это задача проектирования системы, обеспечивающей для заданного объекта управления или процесса закон управления или управляющую последовательность воздействий, обеспечивающих максимум или минимум заданной… … Википедия

решение - вынести новое решение действие вынести решение действие выносить решение действие выполнять решение реализация ждать решения модальность, ожидание зависит решение субъект, зависимость, причина следствие заниматься решением действие …

решение - сущ., с., употр. часто Морфология: (нет) чего? решения, чему? решению, (вижу) что? решение, чем? решением, о чём? о решении; мн. что? решения, (нет) чего? решений, чему? решениям, (вижу) что? решения, чем? решениями, о чём? о решениях 1. Решением … Толковый словарь Дмитриева

оптимальное - найти оптимальное решение существование / создание … Глагольной сочетаемости непредметных имён

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПОЗИЦИОННОЕ - решение задачи оптимального управления математической теории, состоящей в синтезе оптимального управления в виде стратегии управления по принципу обратной связи, как функции текущего состояния (позиции) процесса (см. ). Последнее… … Математическая энциклопедия

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПРОГРАММНОЕ - решение задачи оптимального управления математической теории, в к рой управляющее воздействие u=u(t).формируется в виде функции времени (тем самым предполагается, что по ходу процесса никакой информации, кроме заданной в самом начале, в систему… … Математическая энциклопедия

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

Оптимальное управление - летательным аппаратом раздел динамики полёта, посвящённый развитию и использованию методов оптимизации для определения законов управления движением летательного аппарата и его траекторий, обеспечивающих максимум или минимум выбранного критерия… … Энциклопедия техники

Книги

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