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

Для сведения системы ограничений-неравенств к системе уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные Х3, Х4, Х5. В условиях данной задачи они имеют конкретное экономическое содержание, а именно выражают объем остатков сырья каждого вида после выполнения плана по выпуску продукции. После введения добавочных переменных получим систему уравнений:

5Х1+2Х2+Х3 = 750

4Х1+5 Х2+ Х4 = 807

Х1+7Х2+Х5 = 840

Хi≥0, i=1….5

Нужно найти такое допустимое базисное решение этой системы ограничений, которое бы максимизировало линейную форму F = 30Х₁ +49Х₂.

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

Для решения задачи симплексным методом прежде всего нужно найти любое базисное решение. В данном случае это легко сделать. Для этого достаточно взять в качестве базисных добавочные переменные Х3, Х4, Х5. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель. Считая свободными переменные Х1 и Х2 равными нулю, получим базисное решение (0; 0; 750; 807; 840), которое к тому же оказалось допустимым. Переходим к поискам оптимального решения.

I ш а г. Базисные переменные: Х3, Х4, Х5; свободные переменные: Х1 и Х2. В системе (1.1) базисные переменные выразим через свободные. Для того чтобы судить, оставить ли свободные переменные в числе свободных или их выгоднее с точки зрения приближения к оптимальному решению перевести в базисные, следует выразить через них и линейную форму (в данном случае она уже выражена через переменные Х1 и Х2). Тогда получим:

Х3 = 750 - 5 Х1 - 2 Х2

Х4 = 807 - 4 Х1 - 5Х2

[Х5 = 840 - Х1 - 7Х2]

F = 30Х₁ +49Х₂

При Х1 = Х2 = 0 имеем Х3 = 750, Х4 = 807, Х5 = 840, что дает базисное решение (0; 0; 750; 807; 840), которое мы приняли за исходное. При этом базисном решении значение линейной формы

F = 30Х₁ +49Х₂ = 0.

Когда мы предположили, что Х1 = Х2 = 0 (предприятие ничего не выпускает), была поставлена цель — найти первое, безразлично какое, базисное решение. Эта цель достигнута. Теперь от этого первоначального решения нужно перейти к другому, при котором значение линейной формы увеличится. Из рассмотрения линейной формы видно, что ее значение возрастает при увеличении значений переменных Х1 и Х2. Иными словами, эти переменные невыгодно считать свободными, т. е. равными нулю, их нужно перевести в число базисных. Это и означает переход к новому базисному решению. При симплексном методе на каждом шаге решения предполагается перевод в число базисных только одной из свободных переменных. Переведем в число базисных переменную Х2 так как она входит в выражение линейной формы F = 30Х₁ +49Х₂ с большим коэффициентом.

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

Х2 = min ; = min{375; 161,4; 120} = 120,

далее Х2 переведём в базисные вместо Х5.

II ш а г. Базисные переменные: Х3, Х4, Х2; свободные переменные: Х1, Х5. Выразим базисные переменные и линейную форму через свободные. В системе (1.2) берем то уравнение, из которого получено минимальное значение отношения свободного члена к коэффициенту при Х2. В данном случае это третье уравнение, которое выделено рамкой. Выразив из этого уравнения Х2, получим:

Х2 = 120 -

Х1 - Х5

Подставив это выражение Х2 во все остальные уравнения системы (1.2) и в линейную форму F, получим:

Х2 = 120 - Х1 - Х5

Х3 = 750 - 5 Х1 – 2(120 -

Х1 - Х5) = 510 - Х1 + Х5

Х4 = 807 - 4 Х1 – 5(120 -

Х1 - Х5) = 207 - Х1 + Х5

Х2 = 120 - Х1 - Х5

Х3 = 510 - Х1 + Х5

[Х4 = 207 -

Х1 + Х5]

F = 30Х₁ +49(120 -

Х1 - Х5) = 5880 + 23 Х1 - 7 Х5

При Х1 = Х5 = 0 имеем F = 5880. Это уже лучше, чем на I шаге, но не искомый максимум. Дальнейшее увеличение функции F возможно за счет введения переменной Х1 в число базисных; так как эта переменная входит в выражение F с положительным коэффициентом, поэтому ее увеличение приводит к увеличению линейной формы и ее невыгодно считать свободной, т. е. равной нулю.

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

Х1 = min

; = min{840; 108,2; 63} = 63,

далее Х1 переведём в базисные вместо Х4.

III шаг. Базисные переменные: Х1, Х2, Х3; свободные переменные: Х4, Х5. Выразим основные переменные и линейную форму через свободные. Из последнего уравнения системы (1.3) имеем:

Х1 = 207 + Х5 – Х4 => Х1 = 63 + Х5 - Х4

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

Х1 = 63 + Х5 - Х4

Х2 = 120 -

(63 + Х5 - Х4) - Х5 = 111 - Х5 - Х4

Х3 = 510 -

(63 + Х5 - Х4) + Х5 = 213 - Х5 + Х4

Х1 = 63 + Х5 - Х4