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

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

     1. Некоторые примеры экономических задач, приводящих к модели

линейного программирования (ЛП)

  Пример 1. Задача об использовании ресурсов.

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

                                                                                                                        Таблица 1

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

     1. Выбор  переменных модели. Обозначим  планируемые объемы производства продукции вида    соответственно. Тогда по условию расходы ресурсов   составят  и

   соответственно, а реализация продукции принесет доход . Таким образом,  все  величины выражаются через    переменные    и будут переменными модели. Пару чисел  естественно назвать планом производства (или просто планом).

     2. Целевая  функция. Целью планирования является  максимизация величины

 (целевой функции).

     3. Ограничения на переменные. Возможность осуществления плана   эквивалентна выполнению следующих условий: расходы ресурсов  не превосходят соответствующих запасов 19, 13, 15, 18; объемы производств   - неотрицательные числа.

Все изложенное в 1 - 3  позволяет записать математическую модель рассматриваемой  задачи в виде

                                                                                                   (1)

                                                                                                             (2)

                                                           .                                                   (3)

Более подробно задача (1) – (3) понимается следующим образом:  среди всех пар чисел   (планов задачи), удовлетворяющих ограничениям (2) и (3), найти такую, для которой функция   принимает наибольшее значение.

     Для  n  видов продукции и  m  видов ресурсов математическая модель задачи о ресурсах имеет вид

                                                                                                         (4)

                                                                                               (5)

                                                                                                         (6)

где  - расход  i-го  ресурса на производство единицы  j - й  продукции; b_i - запас

i-го ресурса;  с_j - доход от реализации единицы j - й продукции. В плане задачи

 компонента x_j  означает планируемый объем производства  j-й продукции. Матрицу    принято называть технологической матрицей задачи о ресурсах.

     Пример 2. Задача о диете (витаминах, смесях). Имеется  n  видов продуктов питания   содержащих питательные вещества (витамины)    Известно, что единица продукта   имеет стоимость    и содержит   единиц витаминов    необходимый минимум витамина   составляет   единиц в день,   Требуется составить дневной рацион питания минимальной стоимости, содержащий необходимое количество каждого витамина.

Дневной рацион характеризуется набором из  n  чисел   где   - количество продукта   в рационе, и математическая модель задачи имеет вид

                                                                                                         (7)

                                                                                                (8)

                                                                                                            (9)

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