Решение оптимизационных экономических задач методами линейного программирования

x₁ = 2, x₂ = 6 ; x₁ = 6, x₂ = 4.

 

Отобразим на графике  найденные нами точки и найдем полуплоскости, определяемые каждым из ограничений задачи:

 

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

Обозначим границы области многоугольника решений:

Рассмотрим целевую  функцию задачи F = 2x₁ + 5x₂ → min.

Построим вектор, отвечающий значению функции F = 2x₁ + 5x₂ = 0. Поскольку нас интересует минимальное решение, следовательно проводим от вектора характеристическую прямую в виде перпендикуляра и двигаем ее до первого касания обозначенной области. На графике она обозначена пунктирной линией.

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

Характеристическая прямая пересекает область в точке C. Т.к. точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям следующих прямых:

x₁ + 3x₂ ≥ 15

2x₁+4x₂ ≥ 28

 

Решим систему уравнений:

 

 

 

Подставив полученные значения в целевую функцию, получим:

F_min = 2*12 + 5*1 = 29

 

Ответ: рацион минимальной стоимости должен состоять из 12кг  корма 1 и 1кг корма 2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

Этот метод является универсальным, применимым к любой  задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

симплексный метод алгоритм граммирование

К такому виду можно привести любую  совместную систему, например, методом  Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

• просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов ) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке- ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;
• в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:
• разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
• строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.
• в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.
• столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.
• строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.
• в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

 

 

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

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

 

 

 

 

 

 

 

 

6. Пример решения задачи ЛП симплексным методом

Для изготовления 4-ех видов продукции P₁, P₂, P₃, P₄  используют два вида сырья: S₁ и S₂ . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2. Составить план производства, обеспечивающий получений максимальной прибыли.

Вид сырья	Запас сырья	Количество  единиц сырья, идущих на изготовление единицы продукции
		P1	P2	P3	P4
S1	2	3	2	1	2
S2	5	3	1	3	4
Прибыль от единицы  продукции		27	10	15	28

 

Запишем функцию, отражающую полученную прибыль:

F = 27x₁ + 10x₂ + 15x₃ + 28x₄ → max

Также обозначим ограниченность запасов сырья в виде системы неравенств:

 

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

F = 27x₁ + 10x₂ + 15x₃ + 28x₄ +0x₅ + 0x₆ → max

 

 

 

Запишем систему ограничений  в векторной форме:

Выберем два неравных между собой базисных вектора A_i с координатами 1 и 0 - в нашем случае это A₅ и A₆. Теперь можно составить первую симплекс-таблицу.

 качестве ведущего  выберем столбец, соответствующий  переменной x4, так как это наибольший  коэффициент по модулю. Из него выберем наименьшее значение: min (2 : 2 , 5 : 4 ) = 1. Следовательно, первая строка является ведущей. Разрешающий элемент равен 2 и находится на пересечении ведущего столбца и ведущей строки.

Базис	Cб.	B	C1 = 27	C2 = 10	C3 = 15	C4 = 28	C5 = 0	C6 = 0
			A1	A2	A3	A4	A5	A6
A5	0	2	3	2	1	2	1	0
A6	0	5	3	1	3	4	0	1
Δi =			-27	-10	-15	-28	0	0