Материал: 3597

8

Решение найдено верно.

2. Симплексный метод

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

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

Решить задачу симплексным методом и графически.

Решение. Составим математическую модель. Обозначим через х1 и х2 выпуск продукции А и В соответственно. Затраты материала первого сорта на план х (х1, х2) составят 3х1 + 4х2, и они не должны превосходить запасов, т.е. 45 кг:

Прибыль от реализации х1 единиц А и х2 – В составит z = 7x1 + 5x2 – целевая функция задачи.

Вводом балансовых переменных х3, х4, х5 приводим модель к каноническому виду

9

Составим симплексную таблицу:

Первые три строки этой таблицы содержат в условной форме систему уравнений (ограничений) в задаче (2), а именно: в столбцах ''ai0'' записываются в свободные члены уравнений, в столбцах ''х1'', ''х2'',..., ''х5'' – коэффициенты при соответствующих неизвестных этой системы.

Слева от столбца ''ai0'' в столбце ''xj'' выписываются базисные неизвестные, содержащиеся в соответствующих уравнениях системы.

Верхняя строчка и крайний левый столбец содержат коэффициенты при соответствующих неизвестных в целевой функции z.

Последняя строка называется оценочной, а элементы строки – оценками. Первый элемент а00 оценочной строки представляет собой значение целевой функции z на начальном опорном плане

х0 = (0, 0, 45, 31, 30).

Это значение может быть получено как результат скалярного умножения вектора-столбца ''сj'' на вектор-столбец свободных членов ''аi0''

а00 = 0 45 0 31 0 30 0.

Оценки при неизвестных вычисляются по правилу: оценка при хj равна сумме произведений элементов первого столбца на соответствующие элементы столбца xj минус коэффициент сj, записанный над столбцом хj. Так оценка при х1 равна

а01 = 0 3 0 5 0 2 7 7

Оценки при всех базисных неизвестных всегда равны нулю.

Алгоритм симплексного метода

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

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

11

этот минимум достигается для 2-ой строки. Итак, в базис вводим х1, выводим из базиса х4. В результате первого шага получаем второе опорное решение

z2 = 2175 .

После выполнения 2-го шага получаем оптимальное решение:

хопт = (3, 8, 4, 0, 0); zmax = 61

Дальнейшее увеличение z невозможно, т.к. все оценки стали неотрицательными.

Оптимальное решение исходной задачи (1) получается отбрасыванием

из хопт компонент, связанных с балансовыми переменными х3, х4, х5, т.е.

х*опт = (3,8).

При этом значение zmax не изменится.

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

Прямая 3х1 + 4х2 = 45 плоскостью ХОУ разделила на две части. Чтобы определить полуплоскость, точки которой удовлетворяют неравенству 3х1 + 4х2 45, следует ''испытать'' одну точку. Проще подставить 0 (0,0).

Получим верное неравенство: 0<45. Следовательно, полуплоскость включает точку 0 (0,0). Этот факт отмечается стрелочками.

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

12

Линии уровня целевой функции z задаются уравнениями

7х1 + 5х2 = const

Легко видеть, что они образуют семейство параллельных прямых. Вектор N = (7, 5) называется целевым, он перпендикулярен линиям уровня. Этот вектор указывает направление, двигаясь в котором, мы переходим от меньших значений z к большим, т.е. он указывает направление возрастания функции z. Вершина многоугольника, через которую проходит последняя линия уровня, даст наибольшее значение целевой функции. На рисунке видно, что максимальное значение будет достигнуто в вершине В. Найдем координаты точки В. Эта точка лежит на пересечении прямых

5х1 + 2х2 = 31, 2х1 + 3х2 = 30

Решая систему из двух уравнений с двумя неизвестными, находим, что точка В имеет координаты х1 = 3, х2 = 8. Подставляя в целевую функцию найденные значения, получим: zmax 7 3 5 8 61

3. Двойственность в линейном программировании

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