Линейное программирование: контрольные работы с решением

Сначала идёт подробная теория и потом контрольная работа с решением по каждой теме.

Введение

К оглавлению…

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

Возможно эта страница вам будет полезна:

Предмет математическое программирование

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

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

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

Допустимое решение — это совокупность чисел (план)

Контрольная работа по линейному программированию с решением

удовлетворяющих ограничениям исходной задачи.

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

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

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

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

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

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

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

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

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

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

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

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

Решение задач по математическому программированию

Контрольная работа №1

К оглавлению…

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

Контрольная работа по линейному программированию с решением

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

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

Решение:

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

Контрольная работа по линейному программированию с решением — суточный объем производства краски 1-го вида, [т краски/сутки]; Контрольная работа по линейному программированию с решением — суточный объем производства краски 2-го вида, [т краски/сутки].

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

Контрольная работа по линейному программированию с решением

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

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

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

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

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

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

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

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

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

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

Контрольная работа по линейному программированию с решением

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

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

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

Контрольная работа по линейному программированию с решением

Аналогична математическая запись ограничения по расходу Контрольная работа по линейному программированию с решением

Контрольная работа по линейному программированию с решением

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

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

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Примеры решения задач по математическому программированию

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

К оглавлению…

Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи. Каждое из неравенств задачи ЛП определяет на координатной плоскости Контрольная работа по линейному программированию с решением некоторую полуплоскость, а система неравенств в целом — пересечение соответствующих полуплоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки Контрольная работа по линейному программированию с решением и Контрольная работа по линейному программированию с решением принадлежат этой фигуре, то и весь отрезок Контрольная работа по линейному программированию с решением принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучем, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

Оптимальное решение всегда находится на границе ОДР т.е. ЦФ

Контрольная работа по линейному программированию с решением

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

При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений — единственная точка; задача не имеет решений.

Заказать работу по математическому программированию

Методика решения контрольных работ линейного программирования графическим методом

К оглавлению…

I. В ограничениях задачи замените знаки неравенств на знаки точных равенств и постройте соответствующие прямые.

II. Найдите и заштрихуйте полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого подставьте в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверьте истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

III. Определите ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделите ее. При отсутствии ОДР задача не имеет решений, о чем сделайте соответствующий вывод.

IV. Если ОДР — не пустое множество, то определите координаты угловых точек. Определение координат сводится к решению системы соответствующих линейных уравнений.

V. Подставьте координаты угловых точек в уравнение для ЦФ и найдите Контрольная работа по линейному программированию с решением значение целевой функции.

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

IV.a Провести вектор, координатами которого служат коэффициенты в уравнении с целевой функцией. Сдвигать прямую перпендикулярную построенному вектору от начала по направлению вектора до момента, когда пересечение сдвигаемой прямой с ОДР будет составлять одну точку.

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

Помощь по математическому программированию

Контрольная работа №2

К оглавлению…

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

Контрольная работа по линейному программированию с решением

Решение:

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

Контрольная работа по линейному программированию с решением

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

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

Решая данную систему получаем:

Контрольная работа по линейному программированию с решением
Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением
Контрольная работа по линейному программированию с решением

Контрольная работа по линейному программированию с решением — это точка максимума ЦФ.

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

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

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

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

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

Идея симплекс — метода состоит в том, чтобы преобразовать уравнение содержащее целевую функцию к виду:

Контрольная работа по линейному программированию с решением

т.к. в этом случае становиться возможным выразить

Контрольная работа по линейному программированию с решением

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

Задачи математического программирования

Симплекс метод решения задач линейного программирования

К оглавлению…

Алгоритм решения задачи при помощи симплекс метода:

  1. Вводятся переменные, позволяющие систему неравенств превратить в систему уравнений. (Ограничение-неравенство исходной задачи ЛП, имеющее вид Контрольная работа по линейному программированию с решением, можно преобразовать в ограничение-равенство добавлением к его левой части некоторой новой неотрицательной переменной, а ограничение-неравенство вида Контрольная работа по линейному программированию с решением в ограничение равенство вычитанием из его левой части неотрицательной переменной. Переменные, вводимые для преобразования ограничений-неравенств в ограничения -равенства называют дополнительными. Их число равно числу преобразуемых неравенств.)
  2. Выбирается переменная (рабочая переменная) входящая в целевую функцию с Контрольная работа по линейному программированию с решением коэффициентом (Уничтожать переменные целесообразно, начиная с самой «неподходящей для итогового вида», таким образом, выбирается переменная, входящая в уравнение с целевой функцией, которую уничтожим в первую очередь).
  3. Сравниваются частные от деления свободных членов на коэффициенты при этой переменной и выбирается строка с Контрольная работа по линейному программированию с решением > 0 частным от деления (рабочее уравнение). (Выбирается уравнение, в котором рабочая переменная имеет «наибольший вес» относительно других переменных).
  4. Рабочее уравнение нормируется (т.е. делится на коэффициент перед рабочей переменной), из остальных строк исключаем рабочую переменную методом Гаусса. (Проведение данной операции обусловлено необходимостью исключить возможность проявления уже исключенной из уравнения с целевой функцией переменной в дальнейшем при последующих преобразованиях.)
  5. Проверяется, существуют ли положительные коэффициенты перед переменными в уравнении с целевой функцией: если да, то возвращаются к пункту 2, если нет, то решение закончено.

Контрольная работа №3

К оглавлению…

В качестве примера рассмотрим контрольную решенную графическим методом, задачу про краски.

Контрольная работа по линейному программированию с решением

Решение:

Введем свободные переменные Контрольная работа по линейному программированию с решением для того, чтобы систему неравенств превратить в систему уравнений.

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

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

Контрольная работа по линейному программированию с решением

в этом случае

Контрольная работа по линейному программированию с решением
Задача линейного программирования

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

К оглавлению…

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

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

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

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

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

  1. Увеличение (ограничения типа Контрольная работа по линейному программированию с решением) запаса какого из ресурсов наиболее выгодно?
  2. Анализ изменения коэффициентов ЦФ: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

Методика графического анализа чувствительности оптимального решения:

1. Первая задача анализа на чувствительность (анализ на чувствительность к правой части ограничении)

Проанализируем чувствительность оптимального решения задачи о производстве красок. ОДР задачи (рис. 1) — многоугольник Контрольная работа по линейному программированию с решением. В оптимальной точке Контрольная работа по линейному программированию с решением пересекаются прямые (1) и (2). Поэтому ограничения (1) и (2) являются связывающими, а соответствующие им ресурсы (ингредиенты Контрольная работа по линейному программированию с решением и Контрольная работа по линейному программированию с решением) — дефицитными. Рассмотрим экономический смысл этих понятий. Точка максимума ЦФ Контрольная работа по линейному программированию с решением соответствует суточному производству 3 1/3 т краски 1-го вида и 1 1/3 т краски 2- го вида. В производстве красок используются ингредиенты Контрольная работа по линейному программированию с решением и Контрольная работа по линейному программированию с решением. Суточный запас на складе ингредиентов Контрольная работа по линейному программированию с решением и Контрольная работа по линейному программированию с решением — это правые части связывающих ограничений (1) и (2) (6 и 8 т ингр./сутки). Согласно этим ограничениям, на производство в точке Контрольная работа по линейному программированию с решением расходуется:

Контрольная работа по линейному программированию с решением
Контрольная работа по линейному программированию с решением

Таким образом, понятие «связывающие ограничения» (1) и (2) означает, запасы ингредиентов Контрольная работа по линейному программированию с решением и Контрольная работа по линейному программированию с решением что при производстве красок в точке

Контрольная работа по линейному программированию с решением

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

Правило № 1

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

Контрольная работа по линейному программированию с решением

Правило № 2

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

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

2) подставить координаты Контрольная работа по линейному программированию с решением в левую часть соответствующего ограничения.

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

Контрольная работа по линейному программированию с решением

в левую часть ограничения (1) и получим максимально допустимый запас ингредиента Контрольная работа по линейному программированию с решением.

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

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

Правило № 3

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

Правило № 4

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

Чтобы выяснить, до каких пределов падение спроса на краску 2-го вида не повлияет на производство в точке

Контрольная работа по линейному программированию с решением

используем правило № 4.

Подставляем в левую часть ограничения (4) координаты точки Контрольная работа по линейному программированию с решением, получаем

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

Результаты анализа ресурсов задачи

Контрольная работа по линейному программированию с решением

Вторая задача анализа на чувствительность

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

Контрольная работа по линейному программированию с решением

где Контрольная работа по линейному программированию с решением — максимальное приращение оптимального значения ЦФ; Контрольная работа по линейному программированию с решениемКонтрольная работа по линейному программированию с решением — максимально допустимый прирост объема Контрольная работа по линейному программированию с решением-го ресурса.

Например, из табл. следует, что увеличение суточного запаса ингредиента Контрольная работа по линейному программированию с решением [ограничение (1)] на 1 т позволит получить дополнительный доход, равный Контрольная работа по линейному программированию с решением=1/3тыс.руб./сутки, в то время как увеличение запаса Контрольная работа по линейному программированию с решением [ограничение (2)] на 1 т принесет Контрольная работа по линейному программированию с решением=1 1/3 тыс.руб./сутки. Недефицитные ресурсы имеют нулевые ценности, поскольку изменение этих ресурсов не приводит к увеличению дохода.

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

Третья задача анализа на чувствительность

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

Контрольная работа по линейному программированию с решением

При совпадении с прямой (2) оптимальным решением будут точки отрезка Контрольная работа по линейному программированию с решением. Если целевая прямая выйдет за пределы наклона (1) или (2), то оптимальной точкой станет соответственно Контрольная работа по линейному программированию с решением или Контрольная работа по линейному программированию с решением.

Допустим, что цена на краску 2-го вида не меняется, т.е. зафиксируем значение целевого коэффициента Контрольная работа по линейному программированию с решением. Проанализируем графически результаты изменения значения целевого коэффициент Контрольная работа по линейному программированию с решением, т.е. цены на краску 1-го вида. Оптимальное решение в точке Контрольная работа по линейному программированию с решением не будет меняться при увеличении Контрольная работа по линейному программированию с решением до тех пор, пока целевая прямая не совпадет с прямой (2). Аналогично, оптимальное решение в точке Контрольная работа по линейному программированию с решением не будет меняться при уменьшении Контрольная работа по линейному программированию с решением до тех пор, пока целевая прямая не совпадет с прямой (1).

Аналитический поиск допустимого диапазона изменения цен Совпадение в процессе вращения целевой прямой с прямой ограничения означает, что углы их наклона относительно горизонтальной оси сравнялись, а значит, стали равны тангенсы углов наклона этих прямых.

Правило 5

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

Контрольная работа по линейному программированию с решением

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

Контрольная работа по линейному программированию с решением

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

1) целевой прямой

Контрольная работа по линейному программированию с решением

учитывая, что Контрольная работа по линейному программированию с решением=2 фиксировано

Контрольная работа по линейному программированию с решением

2) связывающего ограничения

Контрольная работа по линейному программированию с решением
Контрольная работа по линейному программированию с решением

3) связывающего ограничения

Контрольная работа по линейному программированию с решением
Контрольная работа по линейному программированию с решением

Для нахождения Контрольная работа по линейному программированию с решением целевая прямая должна совпасть с прямой (1) (рис. 5):

Контрольная работа по линейному программированию с решением

Для нахождения Контрольная работа по линейному программированию с решением целевая прямая должна совпасть с прямой (2) (рис. 6):

Контрольная работа по линейному программированию с решением

Возможно эти страницы вам будут полезны:

  1. Примеры решения задач по линейному программированию
  2. Решение задач по линейному программированию
  3. Методы решения задач линейного программирования
  4. Графическое решение задач линейного программирования
  5. Графический метод решения задач линейного программирования
  6. Заказать работу по линейному программированию
  7. Помощь по линейному программированию
  8. Линейное программирование в Excel
  9. Курсовая работа по линейному программированию