МУ ЭММ _часть 1_

11

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

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

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

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

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие

m

j = fj cj < 0, где fj = aijci , 1 j n,

i 1

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

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

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

Теорема 2. Если для всех векторов выполняется условиеj = fj cj 0, то полученный план является оптимальным.

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

12

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

Z= 0 + r+1xr+1 + … + nxn max, min,

x1 b1 a1r 1xr 1 a1nxn,

x2 b2 a2r 1x 1 a2nxn,

xr br ar r 1xr 1 amxn,

xi 0, i = 1, 2, …, n.

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные x1, x2, …, xr и что при этом b1, b2, …, br ≥ 0 (соответствующее базисное решение является опорным).

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

Далее эта система оформляется в виде симплекс-таблиц:

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

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов) выбирается наименьшее отрицательное число при отыскании max, либо

13

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

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

(j = k), и в этом столбце выбираются положительные коэффициенты.

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

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

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

строится новая таблица, содержащая новые названия базисных переменных: строка разрешающего элемента делится на этот элемент

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

arj arj , 1 j n; в новой таблице все элементы ключевого столбца

ark

равны 0, кроме разрезающего, он всегда равен 1; столбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же; строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же;

востальные клетки новой таблицы записывается результат

1 i m, 1 j n.

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

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

14

1.4. Элементы теории двойственности в задачах линейного программирования

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

F = c1x1 + c2x2 + … + cnxn max,

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

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

Z = b1y1 + b2y2 + … + bmym min,

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

Двойственная задача по отношению к исходной составляется

15

согласно следующим правилам:

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

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

из друга транспонированием; 3) число переменных в двойственной задаче равно числу

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

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

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

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

Первая теорема двойственности. Для взаимодвойственных задач линейного программирования имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: Fmax = Zmin.

16

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

3.В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4.Обе из рассматриваемых задач имеют пустые допустимые множества.

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

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

добавочная переменная хn+i.

Система ограничений двойственной задачи состоит из n неравенств, в которых имеются m переменных. При решении этой задачи симплексным методом необходимо ввести n добавочных неотрицательных переменных: уm+1, ym+2, …, уm+j, …, ym+n, где 1 j n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная уm+j.

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

Иными словами, каждой первоначальной переменной исходной задачи xj (1 j n) ставится в соответствие добавочная переменная уm+j, введенная в j-е неравенство двойственной задачи, а каждой добавочной переменной xn+i исходной задачи (1 i m), введенной в i-е неравенство исходной задачи, ставится в соответствие первоначальная переменная yi двойственной задачи.

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

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

17

оптимум линейной формы другой задачи.

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

Теорема об оценках. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину Fmax , т. е.

yi Fmax .

bi

Эта теорема показывает еще одну связь между переменными прямой и двойственной задач. Поясним это подробнее.

Пусть (х1, х2, …, хj, …, xn) оптимальное решение прямой задачи, а (у1, у2, …, уi, …, уm) оптимальное решение двойственной задачи. Оптимальные значения целевых функций F и Z достигаются при подстановке компонент оптимального решения в их первоначальные выражения, т. е.

Fmax = c1x1 + … + cjxj + … + cnxn,

Zmin = b1y1 + … + biyi + … + bmym.

На основании первой теоремы двойственности (Fmax = Zmin) можно записать

c1x1 + … + cjxj + … + cnxn = b1y1 + … + biyi + … + bmym.

Отсюда следует, что

Fmax = b1y1 + … + biyi + … + bmym.

Поставим вопрос, как изменится величина Fmax, если в исходной задаче увеличить свободный член bi, в i-м ограничении-неравенстве на величину bi (1 i m). Величина Fmax, рассматриваемая теперь как функция переменных b1, …, bi, …, bm, получит приращение Fmax. Частные производные этой функции по любому из этих аргументов имеют вид

Fmax yi .

bi

Учитывая, что функция Fmax линейная, получим Fmax = yi bi. Рассмотрим экономическую интерпретацию двойственной задачи на

примере разд. 2.4.

18

2. КОНКРЕТНАЯ СИТУАЦИЯ ПЛАНИРОВАНИЯ И АНАЛИЗА РАЦИОНАЛЬНОГО ИСПОЛЬЗОВАНИЯ СРЕДСТВ

Для выпуска двух видов продукции требуются затраты электроэнергии, сырья и оборудования. Нормы затрат ресурсов на производство единицы продукции каждого вида, цена единицы продукции каждого вида, а также запасы ресурсов, которые могут быть использованы предприятием, приведены в табл. 1.

Таблица 1

Требуется:

1.Сформулировать экономико-математическую модель задачи в виде задачи линейного программирования.

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

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

4.Сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

5.Решить задачу линейного программирования в MS Excel и выполнить анализ полученных результатов.

2.1. Экономико-математическая модель задачилинейного программирования

Обозначим через x1 и x2 количество продукции A и B, которую планируется произвести в планируемом периоде. Тогда общая стоимость выпущенной продукции составит F = c1x1 + c2x2 = 15x1 + 10x2. Необходимо найти такие значения x1 и x2, чтобы величина F была максимальной, т.е. F max.

Можно утверждать, что переменные x1, x2 не могут принимать произвольных значений, так как их значения ограничены условиями производства продукции. А именно тем, что предприятие располагает ограниченными запасами ресурсов. На изготовление продукции А необходимо израсходовать a11x1 = 3x1 единиц электроэнергии, а на изготовление продукции В a12x2 = 7x2 единиц. Поскольку запас

19

электроэнергии не превышает b1 = 29 единиц, то величины x1 и x2 должны удовлетворять неравенству 3x1 + 7x2 29. Аналогично можно получить неравенство ресурса сырье 3x1 + x2 18, а также для ресурса оборудование x1 + 6x2 23. Кроме того, величины x1, x2 не могут быть отрицательными, т.е. x1 0 и x2 0.

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

F = 15x1 + 10x2 max,

3x1 7x2 29,3x1 x2 18,

x1 6x2 23, x1, x2 0.

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

Рассмотрим вначале геометрическое истолкование системы ограничений задачи. Каждую совокупность значений переменных (x1; x2) можно изобразить точкой на плоскости, если ввести систему координат и по одной оси откладывать значение x1, а по другой x2.

Остановимся на геометрической интерпретации совокупности решений одного отдельно взятого неравенства, описывающего расход электроэнергии 3x1 + 7x2 29.

Рассмотрим прямую на плоскости с уравнением 3x1 + 7x2 = 29. Эта прямая делит плоскость на две полуплоскости, в одной из которых справедливо неравенство, а в другой противоположное. Для того, чтобы проверить, какая из полуплоскостей состоит из решений нашего неравенства, следует взять точку из какой-либо полуплоскости и проверить, выполняется ли оно в этой точке. Множество решений отдельно взятого линейного неравенства представляет собой полуплоскость. Для системы из нескольких таких неравенств точки, координаты которых удовлетворяют всем неравенствам одновременно, должны находиться во всех соответствующих полуплоскостях, т.е. принадлежать теоретико-множественному пересечению этих полуплоскостей. Множество точек на плоскости, удовлетворяющих системе ограничений, составит некоторую выпуклую многоугольную область. Условия неотрицательности переменных x1, x2 0 приводят к тому, что эта область находится в первой координатной четверти.

Построенное на плоскости множество решений системы неравенств сформулированной задачи представлено на рис. 4.

20

Рис. 4. Многоугольник допустимых планов

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