Методы принятия управленческих решений (стр. 6 )

Определение. Стандартной (симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1.1) при выполнении условий (1.2) и (1.4), где k = m и l = n .

Определение. Канонической (основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1.1) при выполнении условий (1.3) и (1.4), где k = 0 и l = n .

Определение. Совокупность чисел , удовлетворяющих ограничениям задачи (1.2) – (1.4), называется допустимым решением (планом).

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

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

Свойства основной задачи линейного программирования (1.5) – (1.7) тесным образом связаны со свойствами выпуклых множеств.

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

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

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

Например, угловыми точками треугольника являются его вершины, круга – точки окружности, которая его ограничивает.

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

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

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

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

L( ) = С1 · x1+ С2 · x2 (1.9)

при условиях , (1.10)

xj ≥ 0, (1.11)

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

, , x1 = 0, x2 = 0.

Если система неравенств (1.10), (1.11) совместна, то областью допустимых решений задачи является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат прямых, уравнения которых получаются из исходной системы заменой знаков неравенств на знаки точных равенств. Для определения вершины многоугольника решений, в которой функция принимает максимальное значение, необходимо построить линию (начальную прямую) С1x1+С2x2=0, проходящую через начало координат на плоскости x10x2, и передвигать ее в направлении вектора N = (С1,С2) до тех пор, пока она не пройдет через последнюю общую точку с многогранником решений. Координаты указанной точки определяют оптимальный план данной задачи.

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

1.  На плоскости x10x2 строят прямые, уравнения которых получаются в результате замены в ограничениях (1.10) и (1.11) знаков неравенств на знаки точных равенств.

2.  Находят полуплоскости, определяемые каждым из ограничений задачи.

3.  Находят многоугольник решений.

4.  Строят вектор N = (С1,С2), направление которого указывает на возрастание целевой функции.

5.  Строят начальную прямую С1x1+С2x2=0, проходящую через начало координат.

6.  Передвигают начальную прямую в направлении вектора N = (С1,С2) до положения опорной прямой (до крайней угловой точки многогранника решений). В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливается неограниченность сверху функции на множестве планов (L(x) → ∞).

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

Замечания.

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

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

min L(X) = – max (–L(X)).

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

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

где 0 ≤ α ≤

Пример.

Найти максимум и минимум линейной функции = –2x1+8x2 → extr при условиях:

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

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

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

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

Решая систему уравнений, получим , ;

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

1. .

Получим ; ; в т. А

2.

Получим ; ; в т. Е

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

= ;

где 0 ≤ α ≤ 1

= = .

Таким образом, оптимальный план задачи:

, ;

=,

Подставляя любые значения α от 0 до 1 , получим координаты множества точек отрезка АЕ, в каждой из которых целевая функция принимает минимальное значение, равное – 8.

Симплексный метод решения задачи

линейного программирования.

Пусть торговое предприятие реализует n групп товаров, используя при этом ограниченные материально-денежные ресурсы размером bi . Известны расходы ресурсов i –го вида на организацию продажи единицы товарооборота товаров j-ой группы, заданные в виде технологической матрицы А = (aij) , ,, и прибыль, получаемая предприятием от реализации единицы товарооборота товаров j-ой группы - Сj.

Требуется определить объем и структуру товарооборота Хj , при которых общая прибыль торгового предприятия была бы максимальной.

Математическую модель задачи можно записать следующим образом:

Определить , который удовлетворяет ограничениям

, (2.1)

, (2.2)

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

(2.3)

Задача линейного программирования (2.1)–(2.3) может быть решена симплексным методом, так как система ограничений задана в виде системы неравенств только смысла «≤ » и вектор столбец свободных членов содержит только положительные числа, т. е.

bi ≥ 0.

Алгоритм симплексного метода включает следующие этапы.

1.  Составление первого опорного плана.

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

, (2.4)

Разрешим систему уравнений (2.4) относительно базисных переменных:

, (2.5)

Аналогично функцию цели представим в виде:

(2.6)

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

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

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

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

3.  Определение направляющих (разрешающих) столбца и строки.

Из отрицательных коэффициентов индексной строки ∆j < 0 выбираем максимальный по абсолютной величине. Направляющий столбец, соответствующий выбранному коэффициенту, показывает, какой вектор или переменная на следующей итерации прейдет из свободных в базисные. Пусть, например, ∆k < 0 и решено ввести в базис вектор А k.

Для определения вектора (переменной), подлежащего исключению из базиса, элементы столбца свободных членов симплексной таблицы (значения базисных переменных) делим на соответствующие положительные элементы направляющего столбца для всех . Результаты заносим в столбец Θ симплексной таблицы. Строка симплексной таблицы, соответствующая минимальному значению Θ, является направляющей. Пусть этот минимум достигается при i = r. Тогда из базиса исключают вектор Аr , т. е. переменная xr на следующей итерации выйдет из состава базисных переменных и станет свободной. Элемент симплексной таблицы аrk , находящийся на пересечении направляющих столбца и строки, называется разрешающим.

4. Определение нового опорного плана.

Для перехода к новому опорному плану производится пересчет симплексной таблицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, т. е. вместо xr в базис войдет переменная аk , соответствующая направляющему столбцу.

Разделим все элементы направляющей строки r предыдущей симплексной таблицы на разрешающий элемент аrk и результаты деления занесем в строку r следующей симплексной таблицы, которая соответствует введенной в базис переменной xk. В результате этого на месте разрешающего элемента новой симплексной таблицы будем иметь «1», а в остальных клетках столбца «к» накапливаем нули. Это равносильно исключению переменной xk из всех строк таблицы (уравнений), кроме строки r, соответствующей переменной. xk .

Преобразование остальных строк симплексной таблицы, включая индексную, рассмотрим на примере строки і. Для получения новых элементов і-ой строки коэффициент а іk , находящийся на пересечении і-ой строки и k-го столбца и взятый с противоположным знаком, умножаем на элементы преобразованной направляющей строки r и складываем с соответствующими элементами і-ой строки. Результаты заносим в і-ую строку новой симплексной таблицы. Если коэффициент а іk = 0, то і-ая строка переносится в следующую симплексную таблицу без изменений.

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

Замечания.

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

2. Если в направляющем столбце все коэффициенты а іk ≤ 0, то функция цели L() не ограничена на множестве допустимых планов, т. е. L() → ∞ и задача не имеет решения.

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

4. Если в оптимальный план вошла дополнительная переменная xn+1 , то это свидетельствует о недоиспользовании ресурса і-го вида в количестве значения этой переменной.

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

Пример.

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

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

№ п\п	Виды материально-денежных ресурсов (i = 1,3)	Единица измерения	Норма затрат ресурсов на реализацию 1 ед. товарооборота	Объем материально-денежных ресурсов (b і)
1 группа (а і1)	2 группа (а і2)	3 группа (а і3)
1. 2. 3.	Рабочее время продавцов Площадь торговых залов Площадь складских помещений	Чел.-час. м2 м2	2 3 2	1 3 1	6 9 2	240 540 120
Прибыль от реализации ед. т/о	Тыс. руб.	14	6	22	max

Запишем математическую модель задачи.

Определить , который удовлетворяет условиям

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

. (2.9)

Задачу (2.8) – (2.9) решим симплексным методом.

Для получения первого опорного плана систему неравенств (2.7) приведем к системе уравнений

(2.10)

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

Решим систему уравнений (2.10) относительно базисных переменных

Функцию цели запишем в виде: (2.12)

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

Первый опорный план заносим в симплексную таблицу (см. таблицу0. этот план является не оптимальным, так как в индексной строке находятся отрицательные коэффициенты: –14, –6, –22. Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине. Так как |–22| > {|–14|, |–6|}, то направляющий столбец соответствует переменной x3. Тогда на следующей итерации переменная x3 перейдет из свободных в базисные. Элементы столбца свободных членов симплексной таблицы разделим на соответствующие положительные коэффициенты направляющего столбца: ; ; . Из трех значений столбца θ выбираем min{40,60,60}= 40. Строка симплексной таблицы, соответствующая минимальному значению θ, является направляющей. Она определяет переменную x4, которая на следующей итерации перейдет из базиса и станет свободной. На пересечении направляющих столбца и строки находится разрешающий элемент, равный 6. В таблице 1 направляющие столбец и строка помечены стрелками, а разрешающий элемент обведен кругом.

Формируем следующую симплексную таблицу 2. Вместо переменной x4 в таблицу 2 вошла переменная x3. Строка, соответствующая переменной x3 получена в результате деления всех элементов направляющей строки (строка переменной x4 таблицы 1) на разрешающий элемент 6. На месте разрешающего элемента в таблице получаем «1». В остальных клетках столбца x3 таблицы 2 накапливаем нули методом Жордана-Гаусса.

Рассмотрим преобразование второй строки симплексной таблицы, которая соответствует переменной x4 . Для получения новых значений элементов данной строки необходимо все элементы преобразованной направляющей строки таблицы 2 умножить на число, стоящее на пересечении строки x5 и столбца x3 таблицы 1, взятое с противоположным знаком, т. е. на (–9). Результаты умножения сложить с соответствующими элементами строки x5 таблицы 1 и записать в строку x5 таблицы 2.

40·(–9) + 540 = 180

·(–9) + 3 = 0

·(–9) + 3 =

1·(–9) + 9 = 0

·(–9) + 0 = –

0·(–9) + 1 = 1

0·(–9) + 0 = 0.

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

Далее возвращаемся к этапу 2 алгоритма – проверка оптимальности опорного плана. Выполняя последовательно все этапы алгоритма, заполняем таблицу 3.

На третьей итерации в таблице 3 получен оптимальный план, так как все коэффициенты в индексной строке ∆j ≥ 0, j = 1, 6.

Запишем оптимальный план:

= (30, 0, 30, 0, 180, 0), L() = 1080 (тыс. руб.).

Следовательно, для получения максимальной прибыли в размере 1080 тыс. руб. торговому предприятию необходимо продавать товаров 1-ой группы 30 ед. (х1*= 30) и товаров 3-ей группы 30 ед. (х3*= 30). В оптимальный план вошла дополнительная переменная х5*= 180. Это указывает на то, что ресурсы второго вида (площади торговых залов) недоиспользованы на 180 м2, остальные ресурсы использованы полностью, так как х4*= х6*= 0.

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

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

Таблица 1	Базисные перемен- ные	Свободные члены (значения базисных перемнных)	x1	x2	x3	x4	x5	x6	θ
←x4	240	2	1	6	1	0	0	40
x5	540	3	3	9	0	1	0	60
x6	120	2	1	2	0	0	1	60
	0	–14	–6	–22↑	0	0	0
Таблица 2	x3	40			1		0	0	120
x5	180	0		0	–	1	0	–
←x6	40			0	–	0	1	30
	880	–↑	–	0		0	0
Таблица 2	x3	30	0	0	1		0	–
x5	180	0		0	–	1	0
x1	30	1		0	–	0
	1080	0	1	0	2	0	5