Линейное программирование.Постановка задачи линейного программирования

Тема 1. Линейное программирование Постановка задачи линейного программирования Первой из задач оптимизации была подробно исследована задача отыскания экстремума линейной функции на множестве, заданном линейными неравенствами и равенствами, т.е. задача линейного программирования. Формулировка задачи линейного программирования имеет вид: 1. Задача решается относительно n переменных х1, х2,…,хn. 2. Предполагается, что переменные должны удовлетворять системе m неравенств: а11х1 + а12х2 + … + а1nхn  b1 а21х1 + а22х2 + … + а2nхn  b2 ………………………………… аm1х1 + аm2х2 + … + аmnхn  bm 3. В экономических задачах присутствует дополнительное условие: координаты переменных х должны быть неотрицательными. 4. Целевая функция представляет собой линейную функцию переменных х1, х2,…,хn.: z=f(х1, х2,…,хn)= p1x1 + p2x2 + … +pnxn 5. Общая задача линейного программирования состоит в выборе вектора Х, удовлетворяющего системе неравенств и максимизирующего целевую функцию. Математическая запись задачи линейного программирования: z= p1x1 + p2x2 + … + pnxn  max при условиях а11х1 + а12х2 + … + а1nхn  b1 а21х1 + а22х2 + … + а2nхn  b2 ………………………………… аm1х1 + аm2х2 + … + аmnхn  bm х1 0 Задача линейного программирования в матричной форме имеет вид: (p,x) → max Ax b x 0 Эта задача называется стандартной задачей линейного программирования на максимум. Можно сформулировать задачу линейного программирования на минимум: (p,x) → min Ax b x 0 Примеры задач линейного программирования 1. Задача составления плана производства Некоторое предприятие (фирма) выпускает n видов продукции, используя при этом m видов ресурсов. Технологии производства описываются числами aij, где aij,означает количество i-го ресурса, затрачиваемое на производство единицы j-го ресурса на фирме. Продукция реализуется по заданным ценам p1, p2,…, pn.. Производственный процесс удовлетворяет условиям линейности и аддитивности, т.е. затраты ресурсов растут прямо пропорционально объемам производства каждого вида продукции. Пусть xij показывает планируемый объем производства j-го вида продукции. Тогда, задача составления плана производства состоит в выборе среди всех векторов х такого, при котором доход от реализации принимает наибольшее значение. Это задача линейного программирования на максимум. Пример. Для изготовления двух видов продукции Р1 и Р2 используют 4 вида ресурсов S1, S2, S3, S4 (оборудование, рабочая сила, сырье, энергия). Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление продукции, приведены в таблице (технологическая таблица). Вид ресурса Запас ресурса Р1 Р2 S1 18 1 3 S2 16 2 1 S3 5 - 1 S4 21 3 1 Прибыль, получаемая реализации единицы продукции Р1 и Р2 соответственно 2 и 3 рубля. Необходимо составить такой план производства, при котором прибыль от ее реализации была бы максимальной. Решение. Составим экономико-математическую модель задачи. Обозначим через х1, х2 – число единиц продукции Р1 и Р2. Для их изготовления потребуется 1х1 + 3х2 единиц ресурса S1, 2х1 + 1х2 единиц ресурса S2, 0х1 + 1х2 единиц ресурса S3, 3х1 + 1х2 единиц ресурса S4. Так как потребление ресурсов не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств х1 + 3х2  18 2х1 + х2  16 х2  5 3х1 + х2  21 По смыслу задачи переменные х1  0, х2  0. Суммарная прибыль составит z=2x1 + 3x2 → max. 2. Задачи составления рациона (о диете, о смесях) При организации питания коллектива людей, например, в больницах, санаториях, армии и.т.п. возникает задача о наиболее экономном рационе питания, удовлетворяющем определенным медицинским требованиям. Пусть рацион составлен из n продуктов (хлеб, молоко, картофель и т.д.), в которых учитывается m питательных веществ (жиры, белки, углеводы, витамины и т.п.). Известны следующие параметры: ai,j – количество i-го вещества, содержащегося в единичном количестве j-го продукта (i=1,2,…,m ; j=1,2,…,n) bi – минимальное количество i-го вещества, которое должно потребляться коллективом людей (индивидуумом) в расчете на какой-либо период времени (например, день, месяц и т. д.); pj – цена j-го продукта. Обозначим через xj – количество j-го продукта, закупаемое для питания. Задача заключается в том, чтобы среди всех рационов питания, удовлетворяющих минимальным потребностям в питательных веществах, следует выбрать самый дешевый. Математическая формулировка задачи о рационе (p,x) → min Ax b x 0 Пример. Имеются 2 вида корма А1 и А2, содержащие питательные вещества S1, S2, S3. Содержание числа единиц питательных веществ в 1 кг каждого корма и необходимый минимум питательных веществ приведены в таблице. Питательное вещество Необходимый минимум А1 А2 S1 9 3 1 S2 8 1 2 S3 12 1 6 Стоимость 1 кг корма А1 и А2 соответственно равна 4 и 6 руб. Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела. Решение. Составим экономико-математическую модель задачи. Обозначим через х1, х2 – число единиц продукции А1 и А2, входящих в дневной рацион. Тогда, этот рацион будет включать 3х1 + 1х2 единиц питательного вещества S1, 1х1 + 2х2 единиц питательного вещества S2, 1х1 + 6х2 единиц питательного вещества S3. Так как содержание питательных веществ в рационе должно быть не менее 9, 8, 12 единиц соответственно, то получим систему: 3х1 + х2 9 х1 + 2х2  8 х1 + 6х2 12 По смыслу задачи переменные х1  0, х2  0. Общая стоимость рациона составит z=4x1 + 6x2 → min. 3. Транспортная задача Первая формулировка и анализ транспортной задачи были даны Хичкоком. Хотя первая постановка транспортной задачи была сделана в 1930 году советским экономистом А.Н.Толстым. Пусть некоторый однородный товар (продукт) хранится на m складах и потребляется в n пунктах (магазинах). Известны следующие параметры: ai – запас продукта на i-м складе, ai  0 (i=1,2,…,m); bj – потребность в продукте в j-м пункте, bj  0 (j=1,2,…,n); cij – стоимость перевозки единичного количества товара с i-го склада в j-й пункт. Планируется полностью перевести товар со складов и полностью удовлетворить потребности в пунктах назначения. При этом предполагается, что суммарные запасы равны суммарным потребностям, т.е. . Целевая функция примет вид . , i=1,2,…,m , j=1,2,…,n где xij  0, где xij – количество товара, перевозимого с i-го склада в j-й пункт. Графический метод решения задачи линейного программирования Вернемся к общему виду задачи линейного программирования: (p,x) → max Ax b x 0 Множество всех векторов х, удовлетворяющих выше перечисленным условиям будем называть множеством допустимых планов или просто допустимым множеством. Любой вектор из этого множества будем называть планом. Через вектор х* будем обозначать вектор, который доставляет наибольшее значение целевой функции и называть его решением задачи ЛП. Перечислим основные свойства задачи ЛП 1. Если допустимое множество задачи непустое и ограничено, то задача ЛП имеет решение. 2. Множество всех допустимых решений системы ограничений является выпуклым, а точнее представляет выпуклый многогранник, который в дальнейшем будем называть многогранником решений. Для задач ЛП особый интерес представляют угловые точки (точки, в которых пересекаются грани многогранника). 3. Если задача линейного программирования имеет оптимальное решение, то целевая функция примет максимальное значение в одной из угловых точек многогранника решений. Если целевая функция примет максимальное значение более, чем в одной угловой точке, то она примет его в любой точке, являющихся линейной комбинацией этих точек. 4. Множество точек х, для которых значения целевой функции одинаковы, называется линией уровня ( n=2), поверхностью уровня (n=3), т.е. p1x1 + p2x2 + … +pnxn = const. Задачу ЛП с двумя переменными можно решить графически. Графический метод решения состоит из следующих этапов: 1) Сначала на координатной плоскости Х1ОХ2 строится допустимая многоугольная область, соответствующая ограничениям. Далее строится вектор q, координаты которого являются частными производными целевой функции. Этот вектор показывает направление возрастания целевой функции. 2) Прямая F=p1x1+p2x2 , перпендикулярная вектору q, передвигается в направлении этого вектора в случае максимизации F до тех пор, пока не покинет пределов многоугольной области. Предельная точка (или точки) области при этом движении и является точкой максимума функции F. 3) Для нахождения координат точки максимума достаточно решить систему уравнений прямых, получаемых из системы ограничений и дающих в пересечении точку максимума. В случае минимизации прямую F=p1x1+p2x2 следует двигать в направлении, противоположенном вектору q. Рассмотрим несколько задач линейного программирования, решенных графическим методом. Задача 1. Решим задачу ЛП графическим методом. F(x1,x2)=5x1+4x2  max при условиях 2x1+5x2  20; 8x1+5x2  40; 5x1+6x2  30; x1  0, x2  0. Решение. 1) Построим область допустимых решений задачи. Каждое неравенство системы геометрически определяет полуплоскость с граничной прямой. Построим каждую граничную прямую и соответствующую полуплоскость. 1) 2x1+5x2 =20 х1 10 х2 4 2) 8x1+5x2 =40 х1 5 х2 8 3) 5x1+6x2 =30 х1 6 х2 5 Условие неотрицательности переменных означает, что область решений будет лежать в первой четверти. Итак, получили многогранник решений ОАВСД. 2) Для определения направления движения построим вектор-градиент, определив его координаты, как частные производные. F=5x1+4x2 ; ; . q=(5;4). 3) Построим некоторую линию уровня 5x1+4x2 = const. Пусть, например const=0, тогда 5x1+4x2 =0. Эта прямая перпендикулярна вектору-градиенту q. 4) При максимизации целевой функции необходимо перемещать линию уровня в направлении вектора-градиента. Предельной точкой при таком движении линии уровня является точка С. Найдем ее координаты. Она является точкой пересечения (2) и (3) прямых. Решим систему, состоящую из уравнений этих прямых: ; . Таким образом, целевая функция задачи ЛП принимает максимальное значение при х1=3,9 и х2=1,7. Найдем его: . Ответ: при х1= и х2=. задач на максимум. Задача 2. В двух продуктах содержится 3 питательных вещества, необходимых для правильного рациона питания. Содержание каждого вида питательных веществ в единице продукта приведено в таблице. Питательное вещество Содержание питательного вещества в единице продукта Жиры 2 2 Белки 4 2 Углеводы 20 В рационе должно присутствовать не менее 8 единиц жиров, 12 единиц белков и 10 единиц углеводов. Цена продукта составляет 75 руб., цена продукта составляет 50 руб. Какое количество продуктов необходимо купить, чтобы соблюсти нормы питания и при этом стоимость покупки была минимальной. Решение. 1) Построим математическую модель задачи. Введём переменные: - необходимое количество продукта , - необходимое количество продукта . Система ограничений имеет вид: Целевая функция – Условие неотрицательности переменных сохраняется. 2) Построим область допустимых решений задачи. Каждое неравенство системы геометрически определяет полуплоскость с граничной прямой. Построим каждую граничную прямую и соответствующую полуплоскость. 1) 2x1+2x2 =8 х1 4 х2 4 2) 4x1+2x2 =12 х1 3 х2 6 3) . Условие неотрицательности переменных означает, что область решений будет лежать в первой четверти. Итак, получили открытую область решений. 3) Для определения направления движения построим вектор-градиент, определив его координаты, как частные производные. F=75x1+50x2 ; ; . Итак, =(75; 50). Для удобства построения вектора разделим каждую координату на 25, получим вектор =(3; 2). 3) Построим некоторую линию уровня 75x1+50x2 = const. Пусть, например const=0, тогда 75x1+50x2 =0. Эта прямая перпендикулярна вектору-градиенту . 4) При максимизации целевой функции необходимо перемещать линию уровня в направлении вектора-градиента. Так как задача на минимум, ищем точку входа линии уровня в многогранную область. Такой точкой является точка В. Найдем ее координаты. Она является точкой пересечения (1) и (2) прямых. Решим систему, состоящую из уравнений этих прямых: ; . Таким образом, целевая функция задачи ЛП принимает минимальное значение при х1=2 и х2=2. Найдем его: . Ответ: необходимо купить по 2 кг каждого продукта, стоимость покупки составит 250 руб.