Математические методы в решении экономических задач (стр. 4 из 6)

Х2 = 111 -

Х5 -

Х4

Х3 = 213 -

Х5 +

Х4

F = 5880 + 23(63 +

Х5 -

Х4) - 7 Х5 = 7329 - 2 Х5 - 7 Х4

Так как в выражение линейной формы переменные Х4 и Х5 входят с отрицательным коэффициентами, то никакое увеличение F за счет этих переменных невозможно.

Следовательно, на III шаге критерий оптимальности достигнут и задача решена. Оптимальным служит решение (63;111;213;207;0), при котором Fmаx= 7329.

Таким образом, для получения наибольшей прибыли, равной 7329 ден. ед., из данных запасов сырья предприятие должно изготовить 63 вида изделий А1 и 111изделий вида А2.

Ответ: Х1* = 63; Х2* = 111. Fmаx= 7329.

Решить задачу табличным симплексным методом

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

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

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

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

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

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

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

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

Составим математическую модель задачи. Искомый выпуск продукции А1 обозначим через Х1, продукции А2 – Х2. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные Х1, Х2 должны удовлетворять следующей системе неравенств:

5Х1+2Х2 ≤ 750

4Х1+5 Х2 ≤ 807

Х1+7Х2 ≤ 840

Х1≥0, Х2≥0

Общая стоимость произведенной предприятием продукции при условии выпуска Х1изделий А1 и Х2 изделий А2 составляет F = 30Х₁ +49Х₂

По своему экономическому содержанию переменные Х1 и Х2 могут принимать только лишь неотрицательные значения: Х1, Х2 ≥0.

Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств (1.1) требуется найти такое, при котором функция F = 30Х₁ +49Х₂ принимает максимальное значение.

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений:

Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, Х3 — это неиспользуемое количество сырья 1-ого вида и т.д.

Для решения задачи табличным симплексным методом прежде всего нужно найти любое базисное решение. В данном случае это легко сделать. Для этого достаточно взять в качестве базисных добавочные переменные Х3, Х4, Х5.,а в качестве свободных переменные Х1 и Х2 равными нулю, получим базисное решение (0; 0; 750; 807; 840), которое к тому же оказалось допустимым. F = 30Х₁ +49Х₂ => F - 30Х₁ - 49Х₂ = 0

Как видно из таблицы (2.1), значения всех переменных отвечают такому «плану», при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.

Это видно и из 4-й строки таблицы (2.1), так как в ней имеется два отрицательных числа: (- 30; - 49;0;0;0). Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции.

Даже с экономической точки зрения наиболее целесообразным является включение в план производства изделий А2. Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число -49, стоит в 4-й строке 2-го столбца => этот столбец является разрешающим.Определяем вектор, подлежащий исключению из базиса и выбираем разрешающую строку. Для этого находим:

Базисные переменные		Свободные переменные	1	2	3	4	5
Базисные переменные		Свободные переменные	Х1	Х2	Х3	Х4	Х5
1	Х3	510	33/7	0	1	0	-2/7
2	Х4	207	23/7	0	0	1	-5/7
3	Х2	120	1/7	1	0	0	1/7
4	F	5880	-23	0	0	0	7