Улучшение опорного решения. Возможные случаи допустимого множества решений задачи линейного программирования Какое решение считается оптимальным

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

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

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

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

Как известно, упорядоченная совокупность значений n переменных , , … представляется точкой n-мерного пространства . В дальнейшем эту точку будем обозначать Х =( , , … ).

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

, A – матрица размера ,

Точка Х =( , , … ), удовлетворяющая всем условиям, называется допустимой точкой . Множество всех допустимых точек называется допустимой областью .

Оптимальным решением (оптимальным планом) задачи линейного программирования называется решение Х =( , , … ), принадлежащее допустимой области и при котором линейная функция Q принимает оптимальное (максимальное или минимальное) значение.

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

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

Точка Х называется выпуклой линейной комбинацией точек если выполняются условия

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

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

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

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n-m неосновных переменных равны нулю. В задачах линейного программирования такие решения называют допустимыми базисными решениями (опорными планами).

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

Из приведенных теорем вытекает важное следствие:

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

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

Составляющие математической модели

Основой для решения экономических задач являются математические модели.

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

Составление математической модели включает:

выбор переменных задачи
составление системы ограничений
выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X1, X2,...,Xn).

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

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

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

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

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

Пример составления математической моделиЗадача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

bi (i = 1,2,3,...,m) - запасы каждого i-го вида ресурса;
aij (i = 1,2,3,...,m; j=1,2,3,...,n) - затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
cj (j = 1,2,3,...,n) - прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X1, X2,...,Xn), где xj (j = 1,2,...,n) - объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема xj продукции равны aijxj, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна cjxj, поэтому целевая функция равна:

Ответ - Математическая модель имеет вид:

Каноническая форма задачи линейного программирования

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

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

Она может быть представлена в координатной, векторной и матричной записи.

Каноническая задача линейного программирования в координатной записи имеет вид:

Каноническая задача линейного программирования в матричной записи имеет вид:

А - матрица коэффициентов системы уравнений
Х - матрица-столбец переменных задачи
Ао - матрица-столбец правых частей системы ограничений

Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной записи имеют вид:

Приведение общей задачи линейного программирования к канонической форме

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство a1x1+a2x2+...+anxn≤b и прибавим к его левой части некоторую величину xn+1, такую, что неравенство превратилось в равенство a1x1+a2x2+...+anxn+xn+1=b. При этом данная величина xn+1 является неотрицательной.

Рассмотрим все на примере.

Пример 26.1

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x4 x5 (на математической модели эта операция отмечена буквой Д).
Переменная х4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x4 x5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде:

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

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

Пусть задача линейного программирования задана в общем виде, т.е. системой 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 ТРАНСПОРТНАЯ ЗАДАЧА

Общая задача линейного программирования (ОЗЛП) формулируется следующим образом – найти переменные задачи x 1 , x 2 , ..., x n , которые обеспечивают экстремум целевой функции

Допустимым решением (планом) задачи линейного программирования (ЗЛП) называется любой n -мерный вектор X =(x 1 , x 2 , ..., x n), удовлетворяющий системе ограничений равенств и неравенств. Множество допустимых решений задачи образует область допустимых решений D .

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение, при котором целевая функция Z (X ) достигает экстремума.

Каноническая задача линейного программирования (КЗЛП) имеет вид

(1.2)

Она отличается от ОЗЛП тем, что её система ограничений является системой только уравнений и все переменные неотрицательные.

Приведение ОЗЛП к каноническому виду ЗЛП:

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

Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных x n +1 ≥ 0 они преобразуются в равенства:

неравенство a i 1 x 1 +…+a in x n ≥ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ,

неравенство a i 1 x 1 +…+a in x n ≤ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ;

Если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательны-ми переменными: x k = x " k – x ” k , где x " k ≥ 0. x ” k ≥ 0.

Графический метод решения ЗЛП с двумя неизвестными

ЗЛП с двумя неизвестными имеет вид:

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

Область допустимых решений (ОДР) задачи является выпуклым многоугольником и строится как пересечение (общая часть) областей решений каждого из неравенств ограничений задачи.

Областью решения неравенства a i 1 x 1 +a i 2 x 2 ≤ b i является одна из двух полуплоскостей, на которые прямая a i 1 x 1 +a i 2 x 2 = b i , соответствующая этому неравенству, делит координатную плоскость. Чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на разделяющей прямой подставить в неравенство:

Если неравенство справедливо, то областью решений является полуплоскость, содержащая эту точку;

Если неравенство не справедливо, то областью решений является полуплоскость, не содержащая эту точку.

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

Линией уровня называется прямая с 1 x 1 +с 2 x 2 = l , где l = const, на которой целевая функция задачи принимает постоянное значение. Все линии уровня параллельны между собой.

Градиент целевой функции grad Z (X ) задает вектор нормали C = (c 1 , c 2) линий уровня. Целевая функция на линиях уровня возрастает, если линии уровня перемещать в направлении их нормали, и убывает – в противоположном направлении.

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

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

Алгоритм графического метода решения ЗЛП с двумя неизвестными:

Построить ОДР.

Построить вектор нормали C = (c 1 , c 2) и линию уровня с 1 x 1 +с 2 x 2 = 0, проходящую через начало координат и перпендикулярную вектору С .

Передвигать линию уровня до опорной прямой в направлении вектора С в задаче на max, или в противоположном направлении – в задаче на min.

Если при перемещении линии уровня в направлении экстремума ОДР уходит в бесконечность, то ЗЛП не имеет решения ввиду неограниченности целевой функции.

Если ЗЛП имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих ОДР и имеющих общие точки с опорной прямой. Если экстремум достигается в двух угловых точках, то ЗЛП имеет бесконечное множество решений, принадлежащих ребру ОДР, ограниченному этими угловыми точками. В данном случае вычисляются координаты обеих угловых точек.

Вычислить значение целевой функции в точке экстремума.

Симплекс-метод решения ЗЛП

Симплекс-метод основывается на следующих положениях:

ОДР задачи линейного программирования является выпуклым множеством с конечным числом угловых точек;

Оптимальным решением ЗЛП является одна из угловых точек ОДР. Угловые точки ОДР алгебраически представляют некоторые базисные (опорные) решения системы ограничений ЗЛП.

Базисным (опорным) решением ЗЛП называется такое допустимое решение X 0 =( x 10 , x 20 , ..., x m 0 , 0,…0), для которого векторы условий (столбцы коэффициентов при неизвестных в системе ограничений) линейно независимы.

Ненулевые координаты x 10 , x 20 , ..., x m 0 решения X 0 называются базисными переменными, оставшиеся координаты решения X 0 - свободными переменными. Число отличных от нуля координат опорного решения не может быть больше ранга r системы ограничений ЗЛП (числа линейно независимых уравнений в системе ограничений ЗЛП). Далее считаем, что система ограничений ЗЛП состоит из линейно независимых уравнений, т.е. r = m .

Смысл симплекс-метода заключается в целенаправленном переходе от одного опорного решения ЗЛП к другому (т.е. от одной угловой точки ОДР к другой) в направлении экстремума и состоит в последовательности этапов:

Найти начальное опорное решение;

Осуществить переход от одного опорного решения к другому;

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

Алгоритм выполнения Симплекс-метода ЗЛП

Алгоритм симплекс-метода осуществляет переход от одного опорного решения ЗЛП к другому в направлении экстремума целевой функции.

Пусть ЗЛП задана в каноническом виде (1.2) и выполнено условие

b i ≥ 0, i =1,2,…,m , (1.3)

соотношение (1.3) всегда можно выполнить, домножив соответствующее уравнение на «-1» в случае отрицательности b i . Также считаем, что система уравнений в ограничениях задачи (1.2) линейно независима и имеет ранг r = m . При этом вектор опорного решения имеет m ненулевых координат.

Пусть исходная задача (1.2), (1.3) приведена к виду, где базисные переменные x 1 , x 2 , ..., x m выражены через свободные переменные x m + 1 , x m + 2 , ..., x n

(1.4)

На основе этих соотношений построим таблицу 1

Таблица 1.

Таблица 1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменениями содержания этой таблицы.

Алгоритм с имплекс-метода :

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

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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

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

Таблица 2

6. Элемент таблицы 2, соответствующий разрешающему элементу таблицы 1, равен обратной величине разрешающего элемента.

7. Элементы строки таблицы 2, соответствующие элементам разрешающей строки таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент.

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

9. Остальные элементы вычисляются по правилу прямоугольника : мысленно вычерчиваем прямоугольник в таблице 1, одна вершина которого совпадает с разрешающим элементом (Рэ), а другая – с элементом, который мы ищем; обозначим элемент в новой таблице 2 через (Нэ), а элемент, стоящий на этом же месте в старой таблице 1 – через (Сэ). Остальные две вершины А и В дополняют фигуру до прямоугольника. Тогда искомый элемент Нэ из таблицы 2 равен Нэ = Сэ – А*В/Рэ.

10. Критерий оптимальности. Как только получится таблица, у которой в последней строке в задаче на min все элементы отрицательны (в задаче на max все элементы положительны), считается, что экстремум найден. Оптимальное значение целевой функции равно свободному члену в строке Z, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные полагаются равными нулю.

11.Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

Метод искусственного базиса решения ЗЛП

Алгоритм симплекс-метода применим, если выделено какое-либо опорное решение ЗЛП, т. е, исходная ЗЛП (1.2) приведена к виду (1.4). Метод искусственного базиса предлагает процедуру построения такого опорного решения.

Метод искусственного базисаоснован на введении искусственных базисных переменных y 1 , y 2 ,…, y m , с помощью которых система ограничений ЗЛП (2.2)

(1.5)

может быть преобразована к виду

(1.6)

Системы (1.5) и (1.6) будут эквивалентны в том случае, если все y i будут равны нулю. Как и раньше мы считаем, что все b i ≥ 0. Для того чтобы у i были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные базисные переменные y i перешли в свободные переменные. Такой переход можно сделать алгоритмом симплекс метода относительно дополнительной целевой функции

F (y ) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)

Исходная симплекс таблица для данного метода имеет вид

Сначала симплекс таблица преобразуется относительно целевой функции F (y ) до получения опорного решения. Опорное решение найдено, когда выполнен следующий критерий: F (y ) = 0 и все искусственные переменные у i переведены в свободные переменные. Затем из симплекс таблицы вычеркивается строка для F (y ) и столбцы для у i и решают задачу для исходной целевой функции Z (x ) до получения оптимального решения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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