Задач линейного программирования

Цель работы: изучить теорию и методы решения задач линейного программирования; пробрести навыки построения моделей линейного программирования и решения задач линейного программирования на ЭВМ.
Краткие теоретические сведения
Методы линейного программирования (ЛП) оказались весьма эф­фективными для решения задач из различных областей человеческой деятельности. Слово "программирование" понимается как планирование, и это определяет характер рассматриваемых приложений. Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленно­сти, торговле и в управлении - как в местных, так и в государственных масштабах. Этими методами можно решить многие задачи, связанные с эффективным использованием ограниченных ресурсов.
Пример 1. Фирма производит две модели (А и В) сборных книжных полок. Их производство ограничено наличием сырья (высоко­качественных досок) и временем машинной обработки. Для каждого из­делия модели А требуется 3 м2 досок, а для изделия модели В - 4 м2 . Фирма может получить от своих поставщиков до 1 700 м2 досок в неде­лю. Для каждого изделия модели А требуется 12 мин машинного време­ни, а для изделия модели 5-30 мин. В неделю можно использовать 160 ч машинного времени.
Сколько изделий каждой модели следует фирме выпускать в не­делю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В-А дол. прибыли?
Чтобы сформулировать эту задачу математически, обозначим че­рез х{ количество выпущенных за неделю полок модели Л, а через х2 -количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения х\ и х2 . Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедель­ную прибыль. Еженедельная прибыль составляет
Р = 2x1 , + 4x2 .
Поскольку х1 и х2 выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательны, т.е.
х{ > 0, х2 >0 (1)
Теперь ограничения на наличие досок и машинное время могут быть записаны следующим образом: для досок -
Зх1 + 4х2 < 1700 (2)
для машинного времени -
2X1 + 5 х2 < 1600. (3)
Следовательно, задача состоит в том, чтобы найти значения х1 и х2 , удовлетворяющие условиям неотрицательности (1) и ограничениям типа неравенства (2) - (3) и максимизирующие функцию Р.
Это типичная двумерная задача линейного программирования. Целевая функция, которая должна быть максимизирована, является линейной функцией своих переменных. Ограничения на эти переменные тоже линейны (1).
Рис. 1 Линия уровня целевой функции и допустимое множество задачи ЛП
Условия неотрицательности позволяют ограничиться рассмотре­нием положительного квадранта. Границы определяются прямыми
3x1 + 4х2 = 1700,
2х1 + 5х2 = 1 600.
Стрелка на каждой границе указывает, с какой стороны прямой * выполняется ограничение. Заштрихованная область ОАВС, содержащая точки, для которых соблюдены условия (2) и (3), является допустимой. Точки внутри и на границе этой области изображают допустимые решения. Допустимых решений много. Задача состоит в том, чтобы най­ти точку максимума функции Р.
Штриховыми линиями изображены прямые
2x1 + 4x2 =0,
2x1 + 4x2 = 800,
обозначенные а и b соответственно. Эти прямые параллельны и пред­ставляют собой две линии уровня функции Р со значениями 0 и 800. Яс­но, что значение функции Р возрастает по мере того, как линии уровня удаляются от начала координат в положительном квадранте.
ми (2, 4), указывающий направление возрастания функции Р перпенди­кулярен штриховым линиям и направлен в сторону, противоположную началу координат.
Линией уровня с наибольшим значением функции Р имеющей хотя бы одну точку с допустимой областью, является прямая с, прохо­дящая через вершину В; на ней Р принимает значение 1 400. Точка В, в которой х1 = 300, х2 = 200, соответствует оптимальному решению зада­чи. Эти значения могут быть получены как решения уравнений.
2х1 +4х2 =1700,
2х1 +5х2 =1 600.
Следовательно, максимальная прибыль составляет 2*300 + 4*200 = 1400.
В точке максимума оба ограничения превращаются в равенства, что означает полное использование сырья и машинного времени.
Пример 1 показывает, как возникают задачи линейного програм­мирования на практике и демонстрирует графический метод их решения.
Рассмотренная задача может быть расширена до трех и более ограничений и соответствующего количества неотрицательных перемен­ных. Могут быть введены дополнительные ограничения, связанные с возможностями рынка, упаковкой и т.д. В этом случае задача по-прежнему заключается в максимизации линейной функции от нескольких переменных при линейных ограничениях.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию