Решение основной задачи линейного программирования геометрическим методом достигает наглядности в случае двух или трех переменных. Для большего количества переменных применение геометрического метода становится невозможным.
Так называемый симплекс-метод принадлежит к числу аналитических методов решения основной задачи линейного программирования. Система ограничений в вычислительных методах обычно задается системой линейных уравнений
a11x1 + a12x2 + …+ a1nxn = b1
a21x1 + a22x2 + …+ a2nxn = b2 (A)
…………………………………………….
am1x1 + am2x2 + …+ amnxn = bm
И среди неотрицательных решений системы (А) надо найти такие, которые максимизировали линейную функцию
L = c1x1 + c2x2 + …+ cnxn + c0
§ Пример
Максимизировать линейную форму L = -x4 + x5 при ограничениях:
x1 + x4 – 2x5 = 1, x2 – 2x4 + x5 = 3, x3 + 3x4 + x5 = 3
Решение.
Данная система уравнений – совместна, так как ранги матрицы системы
и расширенной матрицы
совпадают и равны 3.
Следовательно, система уравнений совместна и три переменных (базисных) можно линейно выразить через две свободные переменные. Выразим, например, x1, x2, x3 через x4 и x5, т.е. приведем систему к единичному базису
|
|
x1 = 1 – x4 + x5
x2 = 2 + 2x4 – x5 ( C)
x3 = 3 – 3x4 – x5
Линейную форму L = x1 + x4 выразим через свободные переменные x4 и x5 (в нашем примере L уже выражено через x4 и x5). Теперь при x4 = 0, x5 = 0 базисные переменные окажутся равными: x1 = 1, x2 = 2, x3 = 3.
Таким образом, первое допустимое решение системы уравнений есть:
x1 = 1, x2 = 2, x3 = 3, x4 = 0, x5 = 0, или (1, 2, 3, 0, 0).
При найденном допустимом решении линейная форма L имеет значение 0, т.е. L1 = 0.
Теперь попытаемся увеличить значение L1; увеличение x4 уменьшит L1, так как перед x4 стоит отрицательный коэффициент, а увеличение x5 дает увеличение и L1. Увеличим поэтому x5 так, чтобы x1, x2, x3 не стали отрицательными, оставив x4 = 0. Из второго уравнения системы (С) видим, что x5 можно увеличить до 2. Тогда значения переменных будут: x1 = 5, x2 = 0, x3 = 1, x4 = 0, x5 = 2, или (5, 0, 1, 0, 2).
Значение линейной формы L при допустимом решении равно L2 = 2. Величина L при втором шаге увеличилась.
Дальше примем за свободные переменные x2 и x4, т.е. именно те переменные, которые в новом решении имеют нулевые значения. С этой целью выразим из второго уравнения системы (С) x5 через x2 и x4. Получим, что x5 = 2 – x2 + 2x4. Тогда
x1 = 5 – 2x2 + 3x4
x3 = 1 + x2 – 5 x4 (D)
x5 = 2 – x2 + 2x4
L = 2 – x2 + x4
Для увеличения значения L будем увеличивать x4. Из второго уравнения системы (D) видно, что для неотрицательности x3 значение x4 можно довести до x4 = 1/ 5. При этом условии новое допустимое решение будет:
x1 = 28 / 5, x2 = 0, x3 = 0, x4 = 1 / 5, x5 = 12 / 5, или (28/5, 0, 0, 1/5, 12/5).
Значение линейной формы при этом будет L = 11/ 5.
Выразим теперь x1, x4, x5 через свободные переменные x2 и x5:
|
|
x1 = 28/5 – 3x3/5 – 7x2/5
x4 = 1/5 – x3/5 + x2/5 (E)
x5 = 12/5 – 2x3/5 – 3x2/5
L = 11/5 – x3 / 5 – 4x2 / 5.
Так как в последней линейной форме оба свободных переменных входят с отрицательными коэффициентами, то наибольшее значение достигается при
x2 = 0, x3 = 0. Это означает, что решение:
x1 = 28 / 5, x2 = 0, x3 = 0, x4 = 1 / 5, x5 = 12 / 5, или (28/5, 0, 0, 1/5, 12/5),
является оптимальным и L max = 11/5.
§ Решение в электронной математике (Mathcad)
Задаем линейную форму
Задаем произвольные начальные условия
Блок решения
Задаем ограничительные условия
Задаем функцию минимизации
Решение
Присваиваем переменным найденные значения
Минимальное значение заданной линейной формы
§ Пример
Цех малого предприятия должен изготовить 100 изделий трех типов, причем каждого вида изделия должно быть произведено не менее 20. При общем запасе металла в 340 кг на производство каждого типа изделий уходит соответственно 4, 3.4 и 2 кг. При общем запасе металла в 700 кг на производство каждого типа изделий уходит соответственно 4.75, 11 и 2 кг. Цена каждого типа изделий по калькуляции соответственно равна: 4, 3 и 2 гривны. Сколько изделий каждого из трех типов необходимо выпустить для максимального объема выпуска в денежном выражении?
Решение.
Обозначим:
x1 – количество изделий первого типа; x2 – количество изделий второго типа;
x3 – количество изделий третьего типа.
Тогда линейная функция, выражающая объем выпуска изделий трех типов в денежном эквиваленте, будет выглядеть следующим образом:
L(x1, x2, x3) = 4x1 + 3x2 + 2x3.
Составим ограничивающие условия:
Так как, каждого изделия должно быть произведено не менее 20 штук, то:
x1 ³ 20, x2 ³ 20, x3 ³ 20.
Так как, при общем запасе металла в 340 кг на производство изделия первого типа уходит 4 кг, второго типа – 3.4 кг, третьего – 2 кг, то:
4x1 + 3.4x2 + 2x3 £ 340.
Так как, при общем запасе в 700 кг на производство изделия первого типа уходит 7.5 кг, второго типа – 11 кг, третьего – 2 кг, то:
7.5x1 + 11x2 + 2x3 £ 700.
Так как, количество произведенных изделий должно быть равно 100, то:
x1 + x2 + x3 = 100.
Решение задачи линейного программирования (т.е. нахождение максимального объема производства изделий трех типов при ограничивающих условиях) в программе Mathcad:
Задается линейная функция
Задаются произвольные начальные условия
Блок решения
Ограничивающие условия
Задаем операцию максимизации
Полученное решение
Таким образом, найдено количество изделий каждого типа:
Цена максимально выпускаемой партии изделий трех типов составит:
Варианты индивидуальных контрольных заданий №5