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

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

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

Х4 = 807 - 4 Х1 – 5(120 - Х1 - Х5) = 207 - Х1 + Х5

Х 2 = 120 - Х1 - Х5

Х

(1.3)

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

Х

(1.4)

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.1)

Х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Х₂ принимает максимальное значение.

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

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

4

(1.1)

Х1+5 Х2+ Х4 = 807

Х1+7Х2+Х5 = 840

Хi≥0, i=1….5

Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, Х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-го столбца => этот столбец является разрешающим.Определяем вектор, подлежащий исключению из базиса и выбираем разрешающую строку. Для этого находим:

Х 2 = min ; ; = 120.

Найдя число = 120, => 3-я строка (Х5) является разрешающей. Следовательно, в базис введем Х2 вместо Х5. Тем самым мы, с экономической точки зрения определили, какое количество изделий А2 предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида.

Таблица (2.1)

На пересечении разрешающего столбца и строки находится разрешающий элемент - это число 7. Производим пересчет всех коэффициентов таблицы, таким образом , чтоб на месте разрешающего элемента получить 1, а в разрешающем столбце все элементы = 0.

Для этого: 1) Третью строку разделим на 7, в результате получим на месте разрешающего элемента 1.

2) Третью строку умножим на 2 и из первой строки вычтем то, что получилось при умножении. Результат записываем в первую строку.

3) Третью строку домножим на 5 и из второй строки вычтем то, что получилось при умножении. Результат записываем во вторую строку.

4) Третью строку умножим на 49 и прибавим к строке F.

При пересчете у нас в столбике F, таблицы (2.2), опять оказалось отрицательное число, а это говорит о том что решение нужно продолжать.

Далее, разрешающим столбцом у нас будет Х1,т.к отрицательное число -23 находится в нем.

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

Х 1 = min ; ; = 63.

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

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