Методические указания по изучению дисциплины и выполнению контрольной работы Для студентов заочного факультета всех специализаций (стр. 6 из 6)

Мы получили математическую запись задачи линейного программирования: ограничения (1) и целевую функцию (2). Для решения воспользуемся симплекс-методом, но предварительно нужно условия задачи записать в каноническом виде. Чтобы от неравенств перейти к равенствам введем слабые переменные:

(3)

где x₃

0 ; x₄

0 .

Чтобы от максимума перейти к минимуму целевой функции, условие экстремума перепишем в форме:

f= - 2x₁ - x₂

min . (4)

Запись задачи в виде условий (3) и (4) позволяет применить симплекс-метод. В равенствах (3) переменные х₃ и x₄ составляют базис, а х₁ и x₂ - свободные переменные. Базисным решением будет X₁=(0,0,300,150), для него f₁=0.

Из условия (4) видно, что f можно уменьшить, увеличивая x₂. Разрешая систему (3), переведем х₂ из свободных в базисные, а х₄ - в свободные переменные. В новом базисе х₂, х₃ перепишем задачу в виде:

(5)

Ей соответствует следующее базисное решение:

X₂=(0, 150,150,0) и f₂ = - 150 .

Теперь для минимизации f следует увеличивать x₁, но так, чтобы x₂ и x₃ оставались неотрицательными. Из системы (5) ясно, что х₁ увеличиваем до 75. При этом переменная х₃ из базисных становится свободной (зато x₁- базисной). В новом базисе x₁x₂ система (5) будет выглядеть:

Ей отвечает решение X₃ = (75,75,0,0) и f ₃= - 225.

Поскольку в целевой функции все коэффициенты при неизвестных положительные, то возможность дальнейшей минимизации f исчерпана, и мы пришли к оптимальному решению

.

Возвращаясь к исходной функции f₁ = - f(x) = 225, заключаем, что при загрузке х₁=75 и х₂=75 мы получаем максимальный выигрыш в 225 единиц.

Этот же результат мы получим геометрически. Введем прямоугольную систему х₁0х₂. Множество допустимых решений системы (1) изобразится заштрихованной областью (рис.4).

Рис. 4

Для построения проведем сначала прямую 3x₁+x₂=300 по двум точкам: пусть x₁=0, тогда x₂=300, при x₂=0 x₁=100. Нанесём точки (0; 300) и (100; 0) на график и проведём прямую АВ. Чтобы определить, какая часть плоскости определяется неравенством (1), подставим в него координаты точки (0; 0). Получили верное неравенство, определяющее полуплоскость, содержащую начало координат. Стрелки на прямой АВ указывают эту полуплоскость. Аналогично строится прямая и для второго неравенства.

Для построения линейной функции воспользуемся следующим приемом: - запишем её в виде

2х₁+х₂=С ,

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

Пусть для начала С=100, тогда прямая пройдёт через точки (0;100) и (50;0). Изобразим её пунктирной линией, показывая, что изменяя С линия будет перемещаться параллельно самой себе. Из рис. 4 следует, что решением системы неравенств при условии max{f} является точка Р(75;75). Ей отвечает максимум f=225. Таким образом, аналитическое и геометрическое решения совпали.