[ММвЛХ] Лекция 12 Линейное программирование
.pdfПоволжский государственный технологический университет
Исследование операций
ЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ
Разработчик: доцент каф. ЛТ и Л, к. с.-х. наук Власова Н.А.
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
•В сфере лесного комплекса к их числу относятся задачи по темам:
•рациональное использование сырья и материалов, оптимизация раскроя;
•оптимизация производственной программы предприятий;
•оптимальное размещение и концентрация производства;
•составление оптимального плана перевозок, работы транспорта;
•управление производственными запасами;
•прочие, принадлежащие сфере оптимального планирования.
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
•Задачами линейного программирования (ЛП) называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств и для которых методы математического анализа оказываются непригодными. ЛП представляет собой наиболее часто используемый метод оптимизации.
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
•По оценкам американских экспертов около 75% от общего числа применяемых оптимизационных методов приходится на ЛП. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач ЛП и их многочисленным модификациям.
Постановка задачи
•Постановка практической задачи ЛП включает следующие основные этапы: определение показателя эффективности, переменных задачи, задание линейной целевой функции W(x), подлежащей минимизации или максимизации,
функциональных hk(x), gj(x) и областных хli <xi <хui ограничений.
Задача линейного программирования в стандартной форме
•W=c1x1+c2x2+…+cnxn min (max)
•При ограничениях
a11x1+a12x2+…+a1nxn =b1; a21x1+a22x2+…+a2nxn =b2;
…
a11x1+a12x2+…+a1nxn =bm;
х1=> 0; х2=> 0;… хn=> 0; b1=> 0; b2=> 0;… bm=> 0.
Задача линейного программирования в стандартной форме
•В матричной форме: W = c*x1min (max)
•При ограничениях
А*x =b; х=> 0; b=> 0,
где А –матрица размерности mxn;
х– вектор-столбец переменных размерности nx1;
b - вектор-столбец ресурсов размерности mx1; с – вектор-строка оценок задачи ЛП 1xn.
Висходной задаче ЛП ограничения часто имеют вид не равенств, а неравенств. В некоторых инженерных задачах не все переменные являются неотрицательными. Следовательно, требуется уяснить механизм преобразования неравенств к равенствам и неограниченных по знаку переменных к неотрицательным.
Постановка задачи
•Задача 1. Оптимизация размещения побочного производства лесничества
•Лесничество имеет 24га свободной земли под паром и
заинтересовано извлечь из неё доход. Оно может выращивать условную растениеводческую продукцию, которая достигает товарного состояния за 1 год или бычков, отведя часть земли под пастбище. Растениеводческая продукция выращивается и продается партиями по 1000 кг. Требуется 1,5га для выращивания 1 партии продукции и 4га для вскармливания одного бычка. Лесничество может потратить только 200 часов в год на своё производство. Допустим, что требуется 20 часов для выращивания и заготовки 1 партии продукции. Для ухода за одним бычком также требуется 20 часов. Лесничество имеет возможность израсходовать на эти цели 6000 руб. Годовые издержки на одну партию растениеводческой продукции составляют 150 рублей и 1200 на одного бычка. Уже заключен контракт на поставку двух бычков. По сложившимся ценам 1кг продукции принесет чистый доход 2 рубля 50 копеек, а один бычок 5000 рублей.
Постановка задачи
•Показатель эффективности – доход за операцию (годовой чистый доход с земли в рублях)
•Управляемые переменные задачи:
х1 – количество бычков (в год)
х2 – количество партий растениеводческой продукции.
•Целевая функция: 5000*х1 + 2500*х2 max
•Ограничения:
•1. По использованию земли: 4*х1 + 1,5*х2 <= 24;
•2. По бюджету: 1200*х1 + 150*х2 <= 6000;
•3. По трудовым ресурсам: 20*х1 + 20*х2 <= 200;
•4. Обязательства по контракту: х1 => 2;
•5. Областные ограничения: х1 => 0, х2 => 0.
Решение задачи ЛП графическим способом