Графический метод решения задач лп

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Во многих ситуациях, встречающихся в промышленности, сельском хозяйстве, экономической деятельности и т.д., задача оптимизации плана некоторых экономико-производственных действий может быть записана в виде линейных уравнений и неравенств с линейным же, относительно искомых, определяющих этот план, переменных целевой функцией. К задачам этого же вида сводятся очень многие задачи оптимизации и принятия решений из некоторых других самостоятельных направлений прикладной математики.

Соответственно возникает потребность в математической теории, позволяющей решать такие задачи. Такая теория существует и называется линейным программированием. Данное название возникло в 30-е годы, когда представления о программировании на компьютере ещё не существовало. Под программированием фактически подразумевается планирование. Однако, этот термин уже укоренился, и не только в линейном случае. Имеются так же и такие названия математических теорий решения задач оптимизации, как нелинейное программирование и динамическое программирование.

В общем виде задача линейного программирования (ЛП) заключается в отыскании таких неотрицательных чисел x1, x2..., хnкоторые максимизируют (минимизируют) линейную функцию:

графический метод решения задач лп - student2.ru

при условии выполнения системы неравенств:

графический метод решения задач лп - student2.ru

При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевую функцию (ЦФ) и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если продавая какой либо товар в общем случае по одной цене рублей, фирма будет делать скидку при определенном уровне закупки, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной. Т.е. в разных ситуациях одна единица товара будет приносить разный доход. Аддитивность означает, что ЦФ и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого.

При решении задачи линейного программирования целесообразно бывает введение следующих определений.

Допустимое решение– это совокупность чисел (план) графический метод решения задач лп - student2.ru , удовлетворяющих ограничениям исходной задачи.

Оптимальное решение – это план, при котором ЦФ принимает свое максимальное (минимальное) значение.

Прежде чем построить математическую модель задачи, т.е. записать ее с помощью математических соотношений, необходимо четко разобраться с экономической ситуацией, описанной в условии. Для этого необходимо с точки зрения экономики, а не математики, ответить на следующие вопросы:

1) Что является искомыми величинами задачи?

2) Какой параметр задачи служит критерием эффективности (оптимальности) решения? (это может быть: прибыль, время, количество отходов и т.д.)

3) В каком направлении должно изменяться значение этого параметра (к max или к min) для достижения наилучших результатов?

4) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию и т.д.

Только после экономического ответа на все эти вопросы можно приступать к записи этих ответов в математическом виде, т.е. к записи математической модели.

а) Искомые величины являются переменными задачи, которые как правило обозначаются малыми латинскими буквами с индексами, например, однотипные переменные удобно представлять в виде графический метод решения задач лп - student2.ru .

б) Цель решения записывается в виде целевой функции, обозначаемой, например, графический метод решения задач лп - student2.ru . Математическая формула ЦФ графический метод решения задач лп - student2.ru отражает способ расчета значений параметра – критерия эффективности задачи.

в) Условия, налагаемые на переменные и ресурсы задачи, записываются в виде системы равенств или неравенств, т.е. ограничений. Левые и правые части ограничений отражают способ получения (расчет или численные значения из условия задачи) значений тех параметров задачи, на которые были наложены соответствующие условия.

В процессе записи математической модели целесообразно указывать единицы измерения переменных задачи, целевой функции и всех ограничений.

Задача

Фабрика производит два вида красок: первый – для наружных, а второй – для внутренних работ. Для производства красок используются два ингредиента: А и В. Известны расходы ингредиентов А и В на 1 т соответствующих красок и максимально возможные суточные запасы этих ингредиентов на складе. Данные по расходам ингредиентов на краски первого и второго вида представлены в таблице.

Ингредиенты Расход ингредиентов, т ингр./т краски Запас, т ингр./сутки
Краска 1-го вида Краска 2-го вида
А
В

Изучение рынка сбыта показало, что суточный спрос на краску 2-го вида никогда не превышает спроса на краску 1-го вида более, чем на 1 т. Кроме того, установлено, что спрос на краску 2-го вида никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3 тыс. руб. для краски 1-го вида; 2 тыс. руб. для краски 2-го вида.

Необходимо построить математическую модель, позволяющую установить, какое количество краски каждого вида надо производить, чтобы доход от реализации продукции был максимальным.

Решение

В задаче требуется установить, сколько краски каждого вида надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого вида красок:

графический метод решения задач лп - student2.ru – суточный объем производства краски 1-го вида, [т краски/сутки];

графический метод решения задач лп - student2.ru – суточный объем производства краски 2-го вида, [т краски/сутки].

В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму.Чтобы рассчитать величину суточного дохода от продажи красок обоих видов, необходимо знать объемы производства красок, т.е. графический метод решения задач лп - student2.ru и графический метод решения задач лп - student2.ru т краски в сутки, а также оптовые цены на краски 1-го и 2-го видов – согласно условию, соответственно 3 и 2 тыс. руб. за 1 т краски. Таким образом, доход от продажи суточного объема производства краски 1-го вида равен графический метод решения задач лп - student2.ru тыс. руб. в сутки, а от продажи краски 2-го вида – графический метод решения задач лп - student2.ru тыс. руб. в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи красок 1-го и 2-го видов (при допущении независимости объемов сбыта каждой из красок)

графический метод решения задач лп - student2.ru [тыс. руб./сутки],

графический метод решения задач лп - student2.ru .

Возможные объемы производства красок графический метод решения задач лп - student2.ru и графический метод решения задач лп - student2.ru ограничиваются следующими условиями:

· количество ингредиентов А и В, израсходованное в течение суток на производство красок обоих видов, не может превышать суточного запаса этих ингредиентов на складе;

· согласно результатам изучения рыночного спроса суточный объем производства краски 2-го вида может превышать объем производства краски 1-го вида, но не более, чем на 1 т краски;

· объем производства краски 2-го вида не должен превышать 2 т в сутки, что также следует из результатов изучения рынков сбыта;

· объемы производства красок не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом ингредиентов;

2) рыночным спросом на краску;

3) неотрицательностью объемов производства.

Ограничения по расходу любого из ингредиентов имеют следующую содержательную форму записи:

графический метод решения задач лп - student2.ru .

Запишем эти ограничения в математической форме.

Левая часть ограничения – это формула расчета суточного расхода конкретного ингредиента на производство красок. Так из условия известен расход ингредиента А на производство 1 т краски 1-го вида (1 т ингр. А) и 1 т краски 2-го вида (2 т ингр. А). Тогда на производство графический метод решения задач лп - student2.ru т краски 1-го вида и графический метод решения задач лп - student2.ru т краски 2-го вида потребуется графический метод решения задач лп - student2.ru т ингр. А.

Правая часть ограничения – это величина суточного запаса ингредиента на складе, например, 6 т ингредиента А в сутки. Таким образом, ограничение по расходу А имеет вид

графический метод решения задач лп - student2.ru .

Аналогична математическая запись ограничения по расходу В

графический метод решения задач лп - student2.ru .

Примечание. Следует всегда проверять размерность левой и правой частей каждого из ограничений, поскольку их несовпадение свидетельствует о принципиальной ошибке при составлении ограничений.

Ограничение по суточному объему производства краски 1-го вида по сравнению с объемом производства краски 2-го вида имеет

содержательную форму

графический метод решения задач лп - student2.ru

и математическую форму

графический метод решения задач лп - student2.ru .

Ограничение по суточному объему производства краски 1-го вида имеет

содержательную форму

графический метод решения задач лп - student2.ru

и математическую форму

графический метод решения задач лп - student2.ru .

Неотрицательность объемов производства задается как

графический метод решения задач лп - student2.ru .

Таким образом, математическая модель этой задачи имеет вид

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

Для задач линейного программирования, содержащих только две переменные графический метод решения задач лп - student2.ru и графический метод решения задач лп - student2.ru применим графический способ решения. Этот способ основан на том факте, что в случае двух переменных множество допустимых решений можно построить на двухмерной плоскости.

Задача

Найдем оптимальное решение задачи о красках, математическая модель которой имеет вид:

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

Построим прямые ограничений (рис. 1).

графический метод решения задач лп - student2.ru

Рис. 1. Графическое решение задачи

графический метод решения задач лп - student2.ru

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим 0 ≤ 1 , что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис. 1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF.

Найдем координаты точек пересечения прямых ограничений, т.е. координаты угловых точек. В некоторых случаях хороший рисунок позволяет сразу определять координаты угловых точек.

графический метод решения задач лп - student2.ru ;

графический метод решения задач лп - student2.ru ;

графический метод решения задач лп - student2.ru ;

графический метод решения задач лп - student2.ru ;

Для определения координаты точки Е решим систему уравнений с ограничениями (5) и (6).

графический метод решения задач лп - student2.ru

Решая данную систему получаем: графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru .

Найдем значение целевой функции в угловых точках, т.е. подставим их координаты в уравнение графический метод решения задач лп - student2.ru .

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

Е – это точка максимума ЦФ.

Таким образом, наилучшим режимом работы фирмы является ежесуточное производство краски 1-го вида в объеме 3 1/3 т и краски 2-го вида в объеме 1 1/3 т. Доход от продажи красок составит 12 2/3 тыс. руб. в сутки.

Решая графическим методом, предполагающим построение целевого вектора, проводим вектор, координатами которого служат коэффициенты в уравнении с целевой функцией графический метод решения задач лп - student2.ru ; сдвигая прямую, перпендикулярную построенному вектору (от начала к концу), найдем точку, являющуюся последней в пересечении сдвигаемой прямой с ОДР (это точка Е), ее координаты, найденные из решения системы соответствующих уравнений, будут являться оптимальным планом, а значение целевой функции в ней будет max.

В более общем случае разработан и широко применяется универсальный метод решения любой задачи ЛП, называемый симплекс-методом.

Симплекс – метод, как метод решения задач ЛП был предложен американским математиком-экономистом Данцигом в 1951 году.

Графически симплекс метод представляет из себя передвижение по выпуклому многограннику от вершины к вершине, при этом значение целевой функции на каждом шаге улучшается до тех пор, пока не достигается оптимум.

Идея симплекс – метода состоит в том, чтобы преобразовать уравнение содержащее целевую функцию к виду: графический метод решения задач лп - student2.ru , т.к. в этом случае становиться возможным выразить графический метод решения задач лп - student2.ru , а в силу того что перед нами ставится задача максимизировать L, то эта задача достигается в случае, когда все переменные, присутствующие в данном уравнении, принимают нулевые значения (т.к. переменные не отрицательны по условию).

Решение

Введем свободные переменные x3, x4, x5, x6, для того, чтобы систему неравенств превратить в систему уравнений.

графический метод решения задач лп - student2.ru

Выбираем переменную, входящую в целевую функцию с максимальным коэффициентом, это x1. Сравниваем частные от деления свободных членов на коэффициенты при x1 6; 4; -1; +¥. Выбираем строку с min > 0 частным от деления и нормируем ее, из остальных строк исключаем x1 методом Гаусса.

графический метод решения задач лп - student2.ru

Выбираем переменную, входящую в целевую функцию с max коэффициентом, это x2. Сравниваем частные от деления свободных членов на коэффициенты при x2 4/3; 8; 10/3; 2. Выбираем строку с min > 0 частным от деления и нормируем ее, из остальных строк исключаем x2 методом Гаусса.

графический метод решения задач лп - student2.ru

Так как все коэффициенты перед переменными в уравнении с целевой функцией < 0, то решение законченно.

В силу не отрицательности переменных из уравнения, содержащего целевую функцию следует, что она достигает максимального значения, в случае, когда x3 = 0 и x4 = 0, в этом случае графический метод решения задач лп - student2.ru

АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

Теоретическое введение

Неизбежное колебание значений таких экономических параметров, как цены на продукцию и сырье, запасы сырья, спрос на рынке и т.д. может привести к неоптимальности или непригодности прежнего режима работы. Для учета подобных ситуаций проводится анализ чувствительности, т.е. анализ того, как возможные изменения параметров исходной модели повлияют на полученное ранее оптимальное решение задачи ЛП.

Для решения задач анализа чувствительности ограничения линейной модели классифицируются следующим образом. Связывающиеограничения проходят через оптимальную точку. Несвязывающиеограничения не проходят через оптимальную точку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным,а ресурс, представляемый несвязывающим ограничением – недефицитным. Ограничение называют избыточнымв том случае, если его исключение не влияет на ОДР и, следовательно, на оптимальное решение. Выделяют следующие три задачи анализа на чувствительность.

1. Анализ сокращения или увеличения ресурсов:

• на сколько можно увеличить (ограничения типа ≤) запас дефицитного ресурса для улучшения оптимального значения ЦФ?

• на сколько можно уменьшить (ограничения типа ≤) запас недефицитного ресурса при сохранении оптимального значения ЦФ?

2. Увеличение(ограничения типа ≤) запаса какого из ресурсов наиболее выгодно?

3. Анализ изменения коэффициентов ЦФ:каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

Правило № 1

Чтобыграфически определить максимальное увеличение запаса дефицитного ресурса, вызывающее улучшение оптимального решения, необходимопередвигать соответствующую прямую в направлении улучшения ЦФ до тех пор, пока это ограничение не станет избыточным. При прохождении прямой (1) через точку К (рис. 2) многоугольник ABCKF становится ОДР, а ограничение (1) – избыточным. Действительно, если удалить прямую (1), проходящую через точку К, то ОДР ABCKF не изменится. Точка К становится оптимальной, в этой точке ограничения (2) и (4) становятся связывающими.

графический метод решения задач лп - student2.ru

Рис. 2 Анализ увеличения ресурса А.

Правило № 2

Чтобычисленно определить максимальную величину запаса дефицитного ресурса, вызывающую улучшение оптимального решения, необходимо:

1) определить координаты точки (x1;x2), в которой соответствующее ограничение становится избыточным;

2) подставить координаты (x1;x2)в левую часть соответствующего ограничения.

Координаты точки К(3;2) находятся путем решения системы уравнений прямых (2) и (4). Т.е. в этой точке фирма будет производить 3 т краски 1-го вида и 2 т краски 2-го вида. Подставим x1=3 и x2=2 в левую часть ограничения (1) и получим максимально допустимый запас ингредиента А.

графический метод решения задач лп - student2.ru

Дальнейшее увеличение запаса ингредиента А нецелесообразно, потому что это не изменит ОДР и не приведет к другому оптимальному решению (см. рис. 2). Доход от продажи красок в объеме, соответствующем точке К, можно рассчитать, подставив ее координаты (3;2) в выражение ЦФ

графический метод решения задач лп - student2.ru

Рассмотрим вопрос о целесообразности увеличения запаса ингредиента В. Согласно правилу № 1, соответствующее ограничение (2) становится избыточным в точке J, в которой пересекаются прямая (1) и ось переменной x1 (рис. 3). Многоугольник ABCDJ становится ОДР, а точка J(6;0) – оптимальным решением.

графический метод решения задач лп - student2.ru

Рис. 3 Анализ увеличения ресурса В.

В точке J выгодно производить только краску 1-го вида (6 т в сутки). Доход от продажи при этом составит:

графический метод решения задач лп - student2.ru

Чтобы обеспечить такой режим работы, согласно правилу № 2, запас ингредиента В надо увеличить до величины:

графический метод решения задач лп - student2.ru

Ограничения (3) и (4) являются не связывающими, т.к. не проходят через оптимальную точку E (см. рис. 1). Соответствующие им ресурсы (спрос на краски) являются недефицитными. С экономической точки зрения это означает, что в данный момент уровень спроса на краски непосредственно не определяет объемы производства. Поэтому некоторое его колебание может никак не повлиять на оптимальный режим производства в точке E.

Например, увеличение (уменьшение) спроса на краску 2-го вида будет соответствовать перемещению прямой ограничения x2≤2 (4) вверх (вниз). Перемещение прямой (4) вверх никак не может изменить точку Е максимума ЦФ. Перемещение же прямой (4) вниз не влияет на существующее оптимальное решение только до пересечения с точкой Е (см. правило № 3.3). Из рис. 1 видно, что дальнейшее перемещение (4) приведет к тому, что точка Е будет за пределами новой ОДР, выделенной более темным цветом. Кроме того, любое оптимальное решение для этой новой ОДР будет хуже точки Е.

Правило № 3

Чтобыопределить максимальное уменьшение запаса недефицитного ресурса, не меняющее оптимальное решение, необходимопередвигать соответствующую прямую до пересечения с оптимальной точкой.

Правило № 4

Чтобычисленно определить минимальную величину запаса недефицитного ресурса, не меняющую оптимальное решение, необходимоподставить координаты оптимальной точки в левую часть соответствующего ограничения.

Чтобы выяснить, до каких пределов падение спроса на краску 2-го вида не повлияет на производство в точке E графический метод решения задач лп - student2.ru используем правило № 4. Подставляем в левую часть ограничения (4) координаты точки Е, получаем графический метод решения задач лп - student2.ru

Делаем вывод: предельный уровень, до которого может упасть спрос на краску 2-го вида и при котором не изменится оптимальность полученного ранее решения, равен 1 1/3 т краски в сутки.

Экономический смысл ограничения (3)

графический метод решения задач лп - student2.ru

в том, что объем продаж краски 2-го вида может превысить объем продаж краски 1-го вида максимум на 1 т. Дальнейшее увеличение продаж краски 2-го вида по сравнению с краской 1-го вида графически отобразится перемещением прямой (3) влево и вверх, но никак не повлияет на оптимальность точки Е. Но если разность спросов на краску 2-го и 1-го видов будет уменьшаться, то прямая (3) будет перемещаться ниже и правее. Последним положением прямой (3), при котором точка Е остается оптимальной, является пересечение с точкой Е (см. рис. 3.1). Согласно правилу № 4, подставим координаты точки E графический метод решения задач лп - student2.ru в левую часть ограничения (3)

графический метод решения задач лп - student2.ru

Получаем, что разность спросов на краску 2-го и 1-го вида в точке стала отрицательной. То есть, прохождение прямой (3) через точку Е означает, что краску 2-го вида будут покупать в меньшем объеме, чем краску 1-го вида

графический метод решения задач лп - student2.ru

Делаем вывод: максимальное превышение спроса на краску 1-го вида над спросом на краску 2-го вида, при котором оптимальное решение в точке Е не изменится, составляет 2 т краски в сутки. Результаты решения первой задачи анализа оптимального решения на чувствительность представлены в табл.

Правило 5

Чтобыопределить границы допустимого диапазона изменения коэффициента ЦФ, например min c1 и max c1, необходимоприравнять тангенс угла наклона целевой прямой ЦФ tgα поочередно к тангенсам углов наклона прямых связывающих ограничений, например tgα(1) и tgα(2) (рис. 5 и 6)

графический метод решения задач лп - student2.ru

Рис. 5. Определение min c1

графический метод решения задач лп - student2.ru

Рис. 6. Определение max c1

Определим насколько максимально может снизиться цена на краску 1-го вида, не изменяя оптимальную точку Е. Для этого применим правило № 5 и формулу расчета тангенса угла наклона прямой (рис. 7).

графический метод решения задач лп - student2.ru

Рис. 7. Определение тангенса угла наклона tgα прямой Y1x1+ Y2x2=Z

Определим тангенсы углов наклона:

1) целевой прямой L(X)=3x1+2x2 → max, учитывая, что c2=2 фиксировано

графический метод решения задач лп - student2.ru

2) связывающего ограничения x1+2x2 ≤ 6 (1)

графический метод решения задач лп - student2.ru

3) связывающего ограничения 2x1+x2 ≤ 8 (2)

графический метод решения задач лп - student2.ru

Для нахождения min c1 целевая прямая должна совпасть с прямой (1) (рис. 5):

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

Для нахождения max c1 целевая прямая должна совпасть с прямой (2) (рис. 6):

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

графический метод решения задач лп - student2.ru

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Во многих ситуациях, встречающихся в промышленности, сельском хозяйстве, экономической деятельности и т.д., задача оптимизации плана некоторых экономико-производственных действий может быть записана в виде линейных уравнений и неравенств с линейным же, относительно искомых, определяющих этот план, переменных целевой функцией. К задачам этого же вида сводятся очень многие задачи оптимизации и принятия решений из некоторых других самостоятельных направлений прикладной математики.

Соответственно возникает потребность в математической теории, позволяющей решать такие задачи. Такая теория существует и называется линейным программированием. Данное название возникло в 30-е годы, когда представления о программировании на компьютере ещё не существовало. Под программированием фактически подразумевается планирование. Однако, этот термин уже укоренился, и не только в линейном случае. Имеются так же и такие названия математических теорий решения задач оптимизации, как нелинейное программирование и динамическое программирование.

В общем виде задача линейного программирования (ЛП) заключается в отыскании таких неотрицательных чисел x1, x2..., хnкоторые максимизируют (минимизируют) линейную функцию:

графический метод решения задач лп - student2.ru

при условии выполнения системы неравенств:

графический метод решения задач лп - student2.ru

При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевую функцию (ЦФ) и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если продавая какой либо товар в общем случае по одной цене рублей, фирма будет делать скидку при определенном уровне закупки, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной. Т.е. в разных ситуациях одна единица товара будет приносить разный доход. Аддитивность означает, что ЦФ и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого.

При решении задачи линейного программирования целесообразно бывает введение следующих определений.

Допустимое решение– это совокупность чисел (план) графический метод решения задач лп - student2.ru , удовлетворяющих ограничениям исходной задачи.

Оптимальное решение – это план, при котором ЦФ принимает свое максимальное (минимальное) значение.

Прежде чем построить математическую модель задачи, т.е. записать ее с помощью математических соотношений, необходимо четко разобраться с экономической ситуацией, описанной в условии. Для этого необходимо с точки зрения экономики, а не математики, ответить на следующие вопросы:

1) Что является искомыми величинами задачи?

2) Какой параметр задачи служит критерием эффективности (оптимальности) решения? (это может быть: прибыль, время, количество отходов и т.д.)

3) В каком направлении должно изменяться значение этого параметра (к max или к min) для достижения наилучших результатов?

4) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию и т.д.

Только после экономического ответа на все эти вопросы можно приступать к записи этих ответов в математическом виде, т.е. к записи математической модели.

а) Искомые величины являются переменными задачи, которые как правило обозначаются малыми латинскими буквами с индексами, например, однотипные переменные удобно представлять в виде графический метод решения задач лп - student2.ru .

б) Цель решения записывается в виде целевой функции, обозначаемой, например, графический метод решения задач лп - student2.ru . Математическая формула ЦФ графический метод решения задач лп - student2.ru отражает способ расчета значений параметра – критерия эффективности задачи.

в) Условия, налагаемые на переменные и ресурсы задачи, записываются в виде системы равенств или неравенств, т.е. ограничений. Левые и правые части ограничений отражают способ получения (расчет или численные значения из условия задачи) значений тех параметров задачи, на которые были наложены соответствующие условия.

В процессе записи математической модели целесообразно указывать единицы измерения переменных задачи, целевой функции и всех ограничений.

Задача

Фабрика производит два вида красок: первый – для наружных, а второй – для внутренних работ. Для производства красок используются два ингредиента: А и В. Известны расходы ингредиентов А и В на 1 т соответствующих красок и максимально возможные суточные запасы этих ингредиентов на складе. Данные по расходам ингредиентов на краски первого и второго вида представлены в таблице.

Ингредиенты Расход ингредиентов, т ингр./т краски Запас, т ингр./сутки
Краска 1-го вида Краска 2-го вида
А
В

Изучение рынка сбыта показало, что суточный спрос на краску 2-го вида никогда не превышает спроса на краску 1-го вида более, чем на 1 т. Кроме того, установлено, что спрос на краску 2-го вида никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3 тыс. руб. для краски 1-го вида; 2 тыс. руб. для краски 2-го вида.

Необходимо построить математическую модель, позволяющую установить, какое количество краски каждого вида надо производить, чтобы доход от реализации продукции был максимальным.

Решение

В задаче требуется установить, сколько краски каждого вида надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого вида красок:

графический метод решения задач лп - student2.ru – суточный объем производства краски 1-го вида, [т краски/сутки];

графический метод решения задач лп - student2.ru – суточный объем производства краски 2-го вида, [т краски/сутки].

В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму.Чтобы рассчитать величину суточного дохода от продажи красок обоих видов, необходимо знать объемы производства красок, т.е. графический метод решения задач лп - student2.ru и графический метод решения задач лп - student2.ru т краски в сутки, а также оптовые цены на краски 1-го и 2-го видов – согласно условию, соответственно 3 и 2 тыс. руб. за 1 т краски. Таким образом, доход от продажи суточного объема производства краски 1-го вида равен графический метод решения задач лп - student2.ru тыс. руб. в сутки, а от продажи краски 2-го вида – графический метод решения задач лп - student2.ru тыс. руб. в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи красок 1-го и 2-го видов (при допущении независимости объемов сбыта каждой из красок)

графический метод решения задач лп - student2.ru [тыс. руб./сутки],

графический метод решения задач лп - student2.ru .

Возможные объемы производства красок графический метод решения задач лп - student2.ru и графический метод решения задач лп - student2.ru ограничиваются следующими условиями:

· количество ингредиентов А и В, израсходованное в течение суток на производство красок обоих видов, не может превышать суточного запаса этих ингредиентов на складе;

· согласно результатам изучения рыночного спроса суточный объем производства краски 2-го вида может превышать объем производства краски 1-го вида, но не более, чем на 1 т краски;

· объем производства краски 2-го вида не должен превышать 2 т в сутки, что также следует из результатов изучения рынков сбыта;

· объемы производства красок не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом ингредиентов;

2) рыночным спросом на краску;

3) неотрицательностью объемов производства.

Ограничения по расходу любого из ингредиентов имеют следующую содержательную форму записи:

графический метод решения задач лп - student2.ru .

Запишем эти ограничения в математической форме.

Левая часть ограничения – это формула расчета суточного расхода конкретного ингредиента на производство красок. Так из условия известен расход ингредиента А на производство 1 т краски 1-го вида (1 т ингр. А) и 1 т краски 2-го вида (2 т ингр. А). Тогда на производство графический метод решения задач лп - student2.ru т краски 1-го вида и графический метод решения задач лп - student2.ru т краски 2-го вида потребуется графический метод решения задач лп - student2.ru т ингр. А.

Правая часть ограничения – это величина суточного запаса ингредиента на складе, например, 6 т ингредиента А в сутки. Таким образом, ограничение по расходу А имеет вид

графический метод решения задач лп - student2.ru .

Аналогична математическая запись ограничения по расходу В

графический метод решения задач лп - student2.ru .

Примечание. Следует всегда проверять размерность левой и правой частей каждого из ограничений, поскольку их несовпадение свидетельствует о принципиальной ошибке при составлении ограничений.

Ограничение по суточному объему производства краски 1-го вида по сравнению с объемом производства краски 2-го вида и

Наши рекомендации