Приложение 1

Вычислительная схема симплекс-метода для решения ОЗЛП

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

		Ориентированность метода на данный тип задач
		Специальные методы	Универсальные
Охват всех задач данного типа	Полный	Симплекс-метод (в том числе методы искусственного базиса)	Имитационное моделирование, градиентные методы и др.
	Частный	Графический метод, метод потенциалов, метод Мака	х

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

«Плюсы»: наглядность и простота;

«Минусы»: ограниченная точность, ориентация на простые задачи, сводимые к 2 переменным.

Симплекс-метод – универсальный метод решения задач линейного программирования. Метод последовательного улучшения плана.

«Плюсы»: простота; точность; универсальность;

«Минусы»: в отдельных случаях нуждается в модификации для получения частных специальных методов.

Основные этапы графического и симплекс-метода представлены в таблице ниже.

Графический метод	Симплекс-метод
1. Графическое представление всех ограничений и требований, построение области допустимых решений (ОДР)	1. Задание пространства решения посредством системы из М линейных уравнений с N неотрицательными переменными. Если M<N, задача имеет бесконечное множество решений
2. Определяются угловые точки ОДР	2. Находится начальное допустимое базисное решение
3. Осуществляется перебор допустимых угловых точек и расчет соответствующих значений Е	3. Выполняется проверка оптимальности базисного решения
4. Среди точек-кандидатов с помощью целевой функции Е определяется угловая точка, соответствующая оптимальному решению	4. Осуществляется переход к смежному не худшему решению. После нескольких итераций находится оптимальное решение

Пример:

По условным данным построить модель задачи линейной оптимизации. Свести задачу ЛП к ОЗЛП. Определить базисное решение.

Е=2Х₁+3Х₂  max

Х₁+3Х₂≤270

4Х₁+6Х₂≤600

3Х₁+Х₂≤240

Х₁, Х₂ ≥0

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

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

2) Базисные переменные определяют решение, а небазисные переменные равны нулю.

3) Базисной переменной для поиска начального допустимого базисного решения принимается переменная, входящая в состав ограничения с коэффициентом «1» и не входящая в состав других ограничений.

Решение задач линейного программирования на основе симплекс-таблиц (симплекс-методом)

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

ШАГ №1. Задача ЛП приводится к ОЗЛП в базисной (стандартной) форме, и определяется начальное допустимое решение, представляющее собой вектор значений переменных. В соответствии с замечанием 3 к постановке ОЗЛП находится количество базисных переменных, соответствующее числу ограничений в модели. Остальные переменные полагаются равными нулю (небазисными).

ШАГ №2. Осуществляется построение симплекс-таблицы. Размерность таблицы зависит от размерности задачи: ширина – от количества переменных, высота – от количества ограничений. При заполнении таблицы в строку целевой функции напротив переменных записываются соответствующие им коэффициенты в функции Е с обратными знаками. В столбце «Решение» записывается значение функции и базисных переменных. В строках, соответствующих ограничениям, записываются коэффициенты при переменных в этих ограничениях с сохранением знака.

ШАГ №3. Из числа текущих небазисных переменных выбирается переменная, включаемая в новый базис (решение). Это включение должно приводить к улучшению значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае переходим к шагу №4.

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

Отсутствие отрицательных коэффициентов в строке целевой функции является признаком оптимальности текущего решения.

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

ШАГ №4. Из числа текущих базисных переменных выбирается переменная, исключаемая из базиса для перевода ее в состав небазисных переменных.

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

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

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

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

ШАГ №5. Находится новое базисное решение, соответствующее новой структуре небазисных и базисных переменных. Осуществляется переход к шагу №3.

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

Пересчет симплекс-таблицы включает 3 операции:

а) ведущая строка делится на ведущий элемент;

б) ведущий столбец (кроме ведущего элемента) заполняется нулями;

в) остальные элементы, включая строку Е, пересчитываются по правилу «прямоугольника». Прямоугольник строится мысленно: одна его диагональ образуется пересчитываемым и ведущим элементом, а вторая достраивается путем мысленного построения вертикальных и горизонтальных сторон.

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

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

Пример решения ОЗЛП на основе симплекс-таблиц.

Некоторые особенности решения задач линейного программирования

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

2) Минимизация целевой функции эквивалентна максимизации той же функции, взятой с противоположным знаком. Поэтому при реализации симплекс-метода исходная целевая функция умножается на «минус» 1;

3) Если в исходных ограничениях есть знаки «=» и «≥», то найти начальное допустимое базисное решение затруднительно. В этих случаях целесообразно использовать концепцию искусственных переменных и применить один из методов искусственного базиса: а) двухэтапный метод; б) метод больших штрафов (М-метод).

4) При реализации симплекс-метода возможны особые случаи:

• вырожденность;

• альтернативное оптимальное решение;

• неограниченное решение;

• отсутствие допустимых решений.

5) На основе анализа симплекс-таблиц и дополнительных вычислений возможно получить информацию относительно:

• оптимального решения;

• статуса ресурсов;

• ценности ресурсов;

• чувствительности оптимального решения к изменениям запаса ресурсов и коэффициентов целевой функции.

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

Общая технологическая схема решения задач ЛП

1. Анализируется постановка задачи на содержательном уровне и выполняется построение базовой аналитической модели;

2. Формальная постановка задачи приводится к стандартной форме ОЗЛП;

3. Если для задачи возможно определить начальное допустимое базисное решение (возможно найти необходимое число базисных переменных), то осуществляется переход к шагу 6 (Обычно это возможно для задач, которые имеют все ограничения типа «≤»);

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

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

6. С помощью симплекс-таблиц находится оптимальное решение;

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

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

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

Методы искусственного базиса: Двухэтапный метод

Двухэтапный метод позволяет получить сначала стартовую точку, то есть начальное допустимое базисное решение (этап 1), а затем – оптимальное решение (этап 2).

Технология решения задачи двухэтапным методом:

Этап 1. В ограничения, где отсутствуют базисные переменные, вводятся искусственные переменные, необходимые для получения стартовой точки. Такие ограничения изначально имеют вид «=» или «≥».

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

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

Новая задача с двумя целевыми функциями вновь приводится к ОЗЛП: искусственная целевая функция умножается на «минус» 1.

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

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

Этап 2. Допустимое решение, полученное на этапе 1, используется в качестве стартовой точки для определения оптимального решения задачи на основе стандартных процедур симплекс-метода.

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

Методы искусственного базиса: М-метод или метод больших штрафов

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

«Плюсы»: Мало отличается от обычного симплекс-метода.

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

Краткая технология работы метода больших штрафов:

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

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

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

Для получения оптимального решения используются стандартные процедуры симплекс-метода.

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

Пример решения задачи М-методом

Привести к ОЗЛП и продемонстрировать процедуру поиска начального допустимого решения двухэтапным и М-методом.

Е=20Х₁+17Х₂+14х₃→min

96Х₁+85Х₂+78Х₃≥90

Х₁+Х₂+Х₃=1

Х₁+Х₂+3Х₃≤2

Х₁, Х₂, Х₃≥0

Основные задачи анализа моделей на чувствительность

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

Для пояснения сути анализа сопроводим его примером.

Пример

Предприятие производит два вида компьютеров, выпуск которых осуществляется на отдельных конвейерах. Производительность первого конвейера составляет 60 компьютеров в час, а второго конвейера – 75 компьютеров в час. На 1 компьютер первого вида расходуется 10 комплектов микросхем, на выпуск второй модели – 8 таких же комплектов. Максимальная часовая поставка комплектов составляет 800 штук. Прибыль от реализации одного компьютера первой и второй модели составляет соответственно 30 и 20 долл.

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

Формальная модель задачи:

Е=30Х₁+20Х₂→max

10Х₁+8Х₂≤800

Х₁≤60

Х₂≤75

Х₁, Х₂ ≥0, целые числа

Модель задачи после приведения к стандартной форме ОЗЛП:

Е=30Х₁+20Х₂→max

10Х₁+8Х₂+Х₃≤800

Х₁+Х₄≤60

Х₂+Х₅≤75

Х₁, Х₂, Х₃, Х₄, Х₅ ≥0, Х₁, Х₂ – целые числа

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

Базис	Х1	Х2	Х3	Х4	Х5	Решение
Е	0	0	2,5	5	0	2300
Х2	0	1	0,125	-1,25	0	25
Х1	1	0	0	1	0	60
Х5	0	0	-0,125	1,25	1	50

На основании итоговой симплекс-таблицы можно получить информацию об оптимальном решении:

Оптимальным решением является производство в сутки 60 компьютеров первой модели и 25 компьютеров второй модели. При этом фирма обеспечит себе максимальную величину прибыли 2300 долл. США.

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

Стандартная процедура анализа включает в себя следующие шаги:

1. Определение статуса ресурсов. Все ресурсы по своему статусу классифицируются на дефицитные (используются полностью) и не дефицитные (имеются в некотором избытке).

Для определения статуса анализируются значения остаточных и избыточных переменных.

Переменная	Описание	Статус ресурса
Х3	неиспользованная часть поставки микросхем, шт./час (остаточная переменная в ограничении о максимальной величине поставок микросхем)	дефицитный
Х4	неиспользуемая производительность первой линии (остаточная переменная в ограничении производительности первой технологической линии)	дефицитный
Х5	неиспользуемая производительность второй линии (остаточная переменная в ограничении производительности второй технологической линии)	недефицитный

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

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

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

Изменение в составе базисных переменных можно объяснить следующим образом:

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

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

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

Для остаточной переменной Х₃ – величины часовой поставки комплектов микросхем – решается следующая система неравенств:

2) статус ресурсов определяется значениями остаточных переменных в структуре оптимального базиса: Х₃ =0 (запас комплектов - дефицитный ресурс); Х₄ = 0 (производительность первой линии – дефицитный ресурс); Х₅ = 50 (производительность второй линии – недефицитный ресурс).

3) предельный диапазон изменения запасов определяется системой уравнений:

2 5+0,125*d≥0 d≥-200

60+1*d≥0 +/- бесконечность

50-0,125*d≥0 d≤400

-200≤d≤400

То есть увеличение поставки сверх 400 комплектов в час приведет к полной загрузке второй технологической линии и сделает запас микросхем избыточным ресурсом. С другой стороны сокращение поставок более чем на 200 комплектов приведет к необходимости полного отказа от использования второй технологической линии и к полному закрытию выпуска второй модели компьютеров.

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

2 5-1,25*d≥0 d≤20

60+0*d≥0 d≥-60

50+1,25*d≥0 d≥-40

-40≤d≤20

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

По третьему виду ресурсов получаем следующую систему неравенств:

2 5-0*d≥0 +/- бесконечность

60+0*d≥0 +/- бесконечность

50+1*d≥0 d≥-50

-50≤d

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

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

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

Ценность одного комплекта микросхем составляет 2,5 долл. США / комплект (то есть увеличение поставки микросхем обеспечивает прирост целевой функции на 2,5 доллара за каждый дополнительный комплект).

Ценность дополнительной производительности 1-ой линии – 5 долл. США за каждое дополнительную единицу мощности.

Ценность дополнительной производительности 2-ой линии равна нулю, поскольку мощности имеются в избытке.

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

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

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

2 ,5+0*d≥0 +/- бесконечность

5+1*d≥0 d≥-5

0-0*d≥0 +/- бесконечность

d≥-5

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

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

2 ,5+0,125*d≥0 d≥-20

5-1,25*d≥0 d≤4

0-0*d≥0 +/- бесконечность

-20≤d≤4

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