183746 (629921), страница 2

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

Текст из файла (страница 2)

Общая прибыль от реализации Х₁ изделий А₁ и Х₂ изделий вида А₂ составит

F = 30Х₁ +49Х₂ .

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

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

Эти прямые изображены на рис №1. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае — другая полуплоскость.

Найдем, например, полуплоскость, определяемую неравенствами.

Построим область допустимых решений:

для прямой

С(0;0) => 5·0+2·0=0, а 0≤750, значит прямая стремится к нулю (рис.1)

для прямой

В(0;0) => 4·0+5·0=0, а 0≤807, значит прямая стремится к нулю (рис.1)

для прямой

А(0;0) => 1·0+7·0=0, а 0≤840, значит прямая стремится к нулю (рис.1). Это и показано стрелками.

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

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

Чтобы найти указанную точку, построим вектор ñ =(30; 49) и прямую 30Х1 + 49Х2 = h, где h — некоторая постоянная такая, что прямая 30Х1 + 49Х2 = h имеет общие точки с многоугольником решений. Положим, например, h = 510 и построим прямую 30Х1 + 49Х2 = 510 (рис. №1).

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

Перемещая построенную прямую 30Х1 + 49Х2 = 510 в направлении вектора ñ, видим, что последней общей точкой ее с многоугольником решений задачи служит точка В. Координаты этой точки и определяют план выпуска изделий А1 и А2, при котором прибыль от их реализации является максимальной.

Найдем координаты точки В как точки пересечения прямых и . Следовательно, ее координаты удовлетворяют уравнениям этих прямых

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

Х1 = 840 – 7Х2, подставим полученное в первое уравнение => 3360 – 28Х2 + 5Х2 = 807 => 23Х2 = 2553 =>

Х2 = 111, из этого решения следует, что Х1 = 840 – 7·111 = 63 => Х1 = 63

Следовательно, если предприятие изготовит 63 изделий вида А1 и 111 изделий вида А2, то оно получит максимальную прибыль, равную Fmax = 30·63 + 49·111= 7329 руб.

Решение задачи аналитическим симплекс-методом

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

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

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

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

Дадим математическую формулировку задачи. Пусть Х1 и Х2 — количество изделий А1 и А2, запланированных к производству. Так как количество сырья по каждому виду ограничено, то должны выполняться следующие неравенства:

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

F = 30Х₁ +49Х₂ .

Итак, задача сводится к нахождению максимума функции F = 30Х₁ +49Х₂ при ограничениях:

Для сведения системы ограничений-неравенств к системе уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные Х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

Характеристики

Список файлов курсовой работы