(НАЗАД) (ДАЛЕЕ)

 

4. Линейное програмМирование

 

 4.1. Максимизация выпуска продукции при ограничениях на расход ресурсов

     4.2. Минимизация затрат при заданных объемах производства  продукции

     4.3. Общая постановка задачи линейного программирования

4.3.1. Двойственная задача линейного программирования

     4.4. Производственное планирование со смешанными  ограничениями

     4.5. Раскрой прутьев

     4.6. Раскрой листов

     4.7. Транспортная задача

     4.8. Планирование посевов

     4.9. Использование оборудования

     4.10. Задача о диете (о смесях)

     4.11. Задача о назначениях

     (СОДЕРЖАНИЕ)

 

 

4.1. Максимизация выпуска продукции при ограничениях на расход ресурсов

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

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

Введем обозначения:

i=1,...,m - номера (индексы) используемых ресурсов;

 - запас i-го ресурса, т.е. допустимый расход i-го ресурса в плановом периоде; другое название - ограничение по ресурсу i;

j=1,...,n - номера (индексы) продуктов;

 - рыночная цена j-го продукта;

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

 - плановый объем производства j-го продукта, величина неизвестная, ее нужно найти в процессе решения задачи. Исходные данные задачи запишем в виде матрицы (рис. 4.1.1).

Каждая строка матрицы  соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b₁, ... , b_i, ... , b_m); внизу каждого столбца - цена продуктов (с₁, ... , с_j, ... , с_m).

В каждой клеточке матрицы записаны так называемые технологические коэффициенты a_ij , показывающие расход i-го ресурса на производство единицы  j-го продукта.

          Запишем конкретный числовой пример (рис. 4.1.2). Возьмем намеренно упрощенные условия задачи: три ресурса и три продукта. Упрощение сделано в учебных целях. Разумеется, реальные задачи имеют большую размерность: больше ресурсов и больше продуктов. Но существо дела от этого не меняется, методы и смысл полученных результатов от размерности задачи не зависят.

Посмотрим на матрицу условий задачи. Выберем 1-ю строку. Коэффициенты 1,6; 0,3 и 0,5 обозначают расход 1-го ресурса на производство единицы 1-го, 2-го и 3-го продуктов соответственно, а 500 – запас 1-го ресурса. Теперь выберем 1-й столбец. Коэффициенты 1,6; 0,8 и 10  обозначают расход 1-го, 2-го и 3-го ресурса соответственно на производство единицы 1-го продукта, 60 – цена единицы 1-го продукта.

Введем еще одно понятие: технологический способ. В данной задаче технологических способов столько, сколько производится продуктов. Первый технологический способ – это производство 1-го продукта и т.д. Технологические способы могут применяться с различной интенсивностью. В данной задаче интенсивность технологических способов измеряется объемом выпускаемой продукции. Напр., применение 3-го технологического способа с единичной интенсивностью означает выпуск единицы 3-го продукта, а производство 100 единиц 3-го продукта означает применение технологического способа с интенсивностью 100. Таким образом,  - плановая интенсивность j-го технологического способа.

Мы хотим найти такой план производства или, что то же самое, такие плановые интенсивности использования технологических способов , при которых суммарная цена продукции будет наибольшей. Появляется еще одно понятие – критерий оптимальности: это такой экономический показатель, по которому оценивается решение задачи. В данной задаче критерий оптимальности – общая цена продукции. Экономисты обычно говорят в таком случае о валовом продукте в денежном выражении. Если произведенная продукция будет продана по указанным ценам, то полученные деньги составят валовой продукт или выручку. Обозначим Q – валовой продукт и запишем формулу для его вычисления в данной задаче:

.                                                                                                                          (4.1.1)

В этом выражении цены умножаются на плановые объемы производства продуктов, и все суммируется. Выражение (4.1.1) называют целевой функцией – это математическое выражение критерия оптимальности.

Теперь нам нужно записать математически то обстоятельство, что нельзя в производстве израсходовать больше ресурсов, чем их имеется. Запишем такое выражение для 1-го ресурса:  

.                                                                                                           (4.1.2)

Здесь слева от знака  записан плановый расход 1-го ресурса, а справа – наличие 1-го ресурса. Смысл ограничения – нельзя израсходовать 1-го ресурса больше, чем его имеется. Очевидно, что такие же ограничения должны быть записаны для 2-го и 3-го ресурсов.

          Зададимся вопросом: какие значения может принимать плановая интенсивность любого технологического способа ? Очевидно, что  может принимать любые положительные значения и ноль, но никак не может быть отрицательной величиной. Если бы, напр.,  был меньше нуля, то это означало бы, что технологический способ действует в обратном направлении – из продукции изготовляют ресурсы. А такое либо технически невозможно (попробуйте из костюма восстановить материю, нитки, затраченные труд и электроэнергию), либо экономически нецелесообразно.

Введем еще три понятия:

продукт – то, что появляется в результате использования технологического способа;

ресурс – то, что расходуется при использовании технологического способа;

ингредиенты – это либо продукт,  либо ресурс, т.е. то, что либо производится, либо расходуется, но в любом случае имеет отношение к рассматриваемым технологическим способам.

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

          Теперь приступим к созданию экономико-математической модели, т.е. к математической записи экономической задачи.

Целевая функция:

.

Ограничения:

              x₁                           ³ 0;

                 x₂                  ³ 0;

                                x₃   ³ 0.

Выражение (4.1.3) обозначает, что целевую функцию нужно максимизировать. Совокупность неравенств (4.1.4) составляет систему ограничений.

  Теперь, когда математическая модель создана, можно забыть об экономическом содержании задачи. В действие вступает математика. Для нее не важно, из какой области человеческой деятельности пришла задача. Раз задача записана на математическом языке (в символьном выражении), то она может быть подвергнута математическому анализу.

          Продолжим введение понятий. Любой набор значений переменных , в данном случае  и , называется планом. Напр., набор чисел 10, -5, 4 является планом. Набор значений переменных , удовлетворяющих системе ограничений, называется допустимым планом. Предыдущий план (10, -5,4) недопустим хотя бы потому, то , а требуется, чтобы все переменные были неотрицательны. План (80, 0, 260) допустим - это легко проверить, подставив в систему ограничений 80, 0, 260  вместо  и .

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

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

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

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

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

          Сформулированная задача решается различными методами. Первый по времени возникновения – метод последовательного улучшения плана, предложенный Л.В. Канторовичем. Затем – симплекс-метод Дж. Данцига. Есть и другие методы. Все они весьма трудоемки и поэтому для решения задач используются компьютеры. Есть различные программные продукты, решающие задачи линейного программирования - напр., EXCEL. Он весьма распространен и дает хорошие средства для решения и анализа задач, поэтому студенты должны владеть им.

Введем некоторые дополнительные понятия, используемые для оценки ограничений. Нежесткие (избыточные) значения показывают, на сколько ограничения в виде неравенств отличаются от равенств. Двойственные (теневые) оценки или множители Лагранжа, показывают, как влияет данное ограничение на целевую функцию.

          Решим поставленную выше задачу с применением EXCEL.

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

Рис. 4.1.3.

 

Содержание ячеек:

B1:D1 - имена продуктов (технологических способов);

A2:A4 - имена ресурсов;

B2:D4 - технологические  коэффициенты (расход ресурсов при единичных интенсивностях технологических способов);

B6:D6 - цены продуктов;

B8:D8 - переменные;

F2:F4 - запас ресурсов;

G2:G4 - плановые расходы ресурсов, получаются в результате решения;

G6 - значение целевой функции, получается в результате решения.

Формулы для вычислений:

G2 = СУММПРОИЗВ(B$8:D$8;B2:D2);

G3:G4 – копируются из G2;

G6 = СУММПРОИЗВ(B8:D8;B6:D6).

          Запишем формулы в ячейки G2:G4. Установить курсор на G2. На панели инструментов выбрать значок формул (f). Появятся два окна. В окне «категория» выбрать «математические», затем в окне «функция» выбрать «СУММПРОИЗВ». Появится окно «СУММПРОИЗВ». В нем нужно указать, где располагаются операнды. Первый операнд – строка B$8:D$8, второй операнд – стока B2:D2. В ячейки G3:G4 формулу скопировать из G2. Аналогичным образом записать формулу целевой функции в ячейку G6. Таблица EXCEL подготовлена.

          Теперь нужно указать остальные условия решения задачи. Установить курсор на ячейку целевой функции G6. В главном меню выбрать «сервис», а потом «поиск решения». Появится окно, в котором нужно указать:

1.     Целевая ячейка - G6;

2.     Включить кнопку «максимальное значение»;

3.     Указать изменяемые ячейки (расположение переменных) – B8:D8;

4.     Записать ограничения. Их можно записать прямо в этом же окне, но лучше выбрать «добавить» и в появившемся окне «добавить» последовательно записать ограничения:

B8:D8  0 – неотрицательность переменных;

G2:G4  F2:F4 – плановый расход ресурсов меньше их запаса.

          Теперь электронная модель сформирована и можно решать задачу. Для этого нужно вернуться в окно «поиск решения» и нажать «выполнить». Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL (рис. 4.1.4.)  и в трех отчетах: Результаты, Устойчивость, Пределы.

Рис 4.1.4.

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

1. Значение целевой функции в ячейке G6 = 15880;

2. Значения переменных в ячейках B8:D8: х₁ = 86, х₂ = 0, х₃ = 268; это значит, что 1-й продукт должен производиться в объеме 86 единиц, 2-й – 0, а 3-й – 286.

3. Плановый расход ресурсов в ячейках G2:G4: расход 1-го ресурса = 271,6, расход 2-го ресурса = 310, расход 3-го ресурса = 2200.

Как видно 1-й ресурс недоиспользован, а 2-й и 3-й израсходованы полностью.

Кроме результатов в электронной таблице EXCEL готовит три отчета: Результаты, Устойчивость, Пределы. Отчет по результатам изображен на рис 4.1.5, где изображены три таблицы.

Отчет по  результатам

Целевая ячейка (максимум)

 

Изменяемые Ячейки

 

Ограничения

Рис 4.1.5.

1-я таблица – целевая ячейка – дает значение целевой функции, которая уже имеется в таблице EXCEL, значит, эти данные избыточны.

2-я таблица – изменяемые ячейки – дает значение переменных, которые уже имеются в таблице EXCEL, эти данные тоже избыточны.

3-я таблица – ограничения – дает оценку ограничений. Колонка «значение» дает значения планового расхода ресурсов и переменных – эти данные имеются в таблице EXCEL и здесь избыточны. Столбец «статус» значением «связанное» отмечает ограничения (не больше или не меньше), которые в результате решения превратились в строгие равенства, прочие ограничения имеют статус «несвязанные». Столбец «разница» показывает, на какую величину ограничения отклонились от строгого равенства. Так, например, ограничение 1-го ресурса 500, плановое значение 271,6, разница = 500 – 271,6 = 228,4.

Отчет по устойчивости изображен на рис. 4.1.6. Он состоит из двух таблиц.

Отчет по устойчивости

 

Изменяемые ячейки

 

Ограничения

Рис. 4.1.6.

 

Таблица «изменяемые ячейки» показывает значения переменных, которые уже имеются в таблице EXCEL. Столбец «нормируемый градиент» показывает, как влияет увеличение переменных на единицу на величину целевой функции. Таблица «ограничения» содержит важную информацию в столбце «Лагранжа множители». Эти величины в литературе имеют различные названия: объективно обусловленные оценки (О.О.О.) по Л. Канторовичу, двойственные оценки по Д. Данцигу, оптимальные цены, теневые цены и другие. В дальнейшем будем называть их наиболее распространенным именем – двойственные оценки и обозначать - v_i, где i- номер ограничения. В данном примере v₁ = 0, v₂ = 20,0, v₃ = 4,4. Отчет по пределам показан на рис. 4.1.7.

Отчет по пределам

 

 

 

Рис. 4.1.7.

В этом отчете уже в третий раз дается значение целевой функции 15880, в пятый раз значение переменных (х₁ = 86, х₂ = 0, х₃ = 268). Нижний предел для всех переменных = 0, так, установлены ограничения по переменным. Верхний предел равен соответственно 86, 0 и 268, так устанавливают ограничения по ресурсам. Целевой результат показывает значение целевой функции при соответствующих значениях переменных. Если х₁ = 0, то ЦФ = 10720 и т.д.

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

          Двойственные оценки чрезвычайно важны для экономического анализа. Они относятся к ограничениям. Математически двойственная оценка показывает, насколько изменится значение целевой функции при изменении правой части ограничения на единицу. Двойственная оценка есть частная производная от целевой функции по ограничению. Так, v₂=20, эта двойственная оценка относится ко 2-му ограничению. В данной задаче это означает, что если к имеющимся 310 единицам 2-го ресурса добавить еще единицу, т.е. вместо 310 записать в правой части ограничения 311, то целевая функция возрастет на 20 единиц и будет равна 15880+20=15900. Наоборот, если уменьшить правую часть ограничения на единицу, то целевая функция уменьшится на 20. Почему же v₂  и v₃ больше нуля, а v₁=0? Дело в том, что 2-й и 3-й ресурсы израсходованы полностью. Естественно, что добавление этих ресурсов увеличивает объем производства, а уменьшение - сокращает этот объем. Соответственно возрастает или сокращается оптимальное значение целевой функции. Но 1-й ресурс имеется в избытке и полностью не израсходован. Следовательно, добавление или сокращение этого ресурса никак не скажется на объеме производства и на значении целевой функции. Именно поэтому v₁=0.

          До сих пор мы рассматривали математический смысл двойственных оценок – зависимость изменения целевой функции от изменения ограничений. Но нам также важен их экономический смысл. В данной задаче двойственные оценки показывают зависимость прироста объема продукта от последней (предельной) единицы ресурса. Такой показатель известен экономической науке с XIX века. Называется он – предельная производительность фактора производства. Ресурс – это фактор производства. Предельная производительность фактора производства – вклад последней (предельной) единицы фактора производства в увеличение объема продукции. Но именно это и показывают двойственные оценки. То, что пришлось заново открывать математику Л.В.Канторовичу в советской экономической науке, давно было известно мировой экономической науке. Но разница существенная. Экономисты имели понятие о предельной производительности фактора производства, но не знали, как ее вычислять. Л.В.Канторович дал метод, теорию оптимального планирования производства и одновременного вычисления предельной производительности факторов производства.

          Посмотрим снова на математическую модель задачи (4.1.3, 4.1.4). Мы видим, что и целевая функция, и ограничения являются линейными выражениями от переменных . Во все выражения переменные  входят в первой степени. Именно поэтому такое программирование (планирование) и названо линейным.

Запишем математическую модель рассмотренной задачи в общем виде:

          Во всех выражениях индекс j принимает значения от 1 до n. Суммирование по j также производится от 1 до n.

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

          Как устанавливаются ограничения на ресурсы? Обычно в производстве используется много ресурсов. Это не значит, что на каждый из них должно быть установлено ограничение. Такие ограничения могут быть установлены на все ресурсы или на часть их, но хотя бы одно ограничение обязательно. В противном случае область допустимых значений не ограничена,  целевая функция (валовой объем продукции) будет возрастать до бесконечности. Если условия такой задачи ввести в компьютер, будет получен ответ, что целевая функция не ограничена.

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

          При социализме, т.е. в случае «принудительно направляемой экономики» (по выражению Л.Эрхарда), ограничения по ресурсам устанавливались в натуральных измерителях: тонны металла, цемента и горючего, кубометры леса и т.д. Это объясняется тем, что ресурсы не продавались свободно, а распределялись государственными органами. В рыночной экономике такие ограничения обычно отсутствуют, т.к. все можно купить. Здесь основным и почти единственным ограничением выступают деньги.

          Пусть:

В – бюджет, т.е. количество денег, которое можно израсходовать на приобретение ресурсов для производства продукции, а s_i – рыночная цена i-го ресурса. Тогда единственное ограничение по ресурсам будет выглядеть следующим образом:

.

          Смысл этого ограничения - нельзя израсходовать ресурсов на сумму больше, чем  В.

Здесь:   - расход i-го ресурса в натуральном выражении по j-му технологическому способу;

- расход  i-го ресурса в натуральном выражении по всем способам;

- суммарная цена i-го ресурса, израсходованного по всем способам;

- суммарная цена всех ресурсов по всем технологическим способам.

Решим задачу на максимум продукции с ограничением по бюджету. За основу возьмем электронную модель на рис. 4.1.3. и дополним ценами ресурсов s_i и бюджетом В (рис. 4.1.8)

Рис. 4.1.8.

          Дополнительные величины:

H2:H4 – цены ресурсов (задаются);

I2:I4 – издержки (вычисляются);

I2 = G2*H2;

I3:I4 – копируется из I2;

H6 = 5000 – бюджет (задается);

I6 – издержки всего (вычисляются);

I6 = СУММ(I2:I4).

Ограничения:

B8:D8  0 – неотрицательность переменных;

I6  H6 – совокупные издержки не больше бюджета.

Будет получено решение

x₁ = 0; x₂ = 0; x₃ = 409,84.

v = 3,08 – двойственная оценка ограничения по бюджету – увеличение бюджета на единицу увеличивает валовой продукт на 3,28.

          Когда сформулирована модель, математически проводят анализ на предмет ее разрешимости: во-первых, существует ли хотя бы один допустимый план, и, во-вторых, если допустимые планы существуют, то есть ли оптимальный план, т.е. план с предельным значением целевой функции? Проведем такой анализ и мы, но сделаем это экономическим методом, т.е. проведем содержательный анализ. Если все ограничения по ресурсам имеют смысл - израсходовать не больше заданного количества ресурсов - то допустимые планы существуют. Напр., таким является план, когда все переменные =0. Этот план удовлетворяет всем ограничениям. Теперь попробуем определить, существует ли оптимальный план, т.е. ограничена ли целевая функция. Обратим внимание на то, что технологические коэффициенты  не могут быть в данной постановке отрицательными, но могут быть равны нулю. Если для некоторого j-го технологического способа все =0, т.е. j-й способ не использует ресурсы, по которым установлены ограничения, то объем производства можно наращивать до бесконечности, целевая функция не ограничена и оптимального решения нет. Если нет ни одного технологического способа, у которого все =0, то целевая функция ограничена и оптимальный план существует.

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

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.2.  Минимизация затрат при заданных объемах производства продукции

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

Матрица условий задачи показаны на рис. 4.2.1.

Запишем математическую модель задачи.

 - индексы продуктов;

 - необходимый объем производства i-го продукта;

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

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

Продолжим составление математической модели:

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

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

 - технологический коэффициент, выход (объем производства) i-го продукта из единицы j-го сорта леса, или, что то же самое, при единичной интенсивности j-го технологического способа.

Запишем математическую модель задачи сначала в общем виде:

 

Теперь запишем эту же модель в численном виде:

;

 

 

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

 Ограничения  - плановый объем производства i-го вида продукции не может быть меньше заданной величины.

Ограничения  - плановый объем использования j-го вида сырья не должен быть отрицательной величиной.

Решение задачи.

Электронная модель задачи дана на рис. 4.2.2.

Рис 4.2.2.

Содержание ячеек:

B1:D1 – наименование ресурсов (сортов леса);

A2:A4 – наименование продуктов;

B2:D4 – матрица технологических коэффициентов;

B6:D6 – издержки при единичных интенсивностях использования каждого технологического способа;

B8:D8 – переменные;

F2:F4 – заданные объемы производства продуктов;

G2:G4 – плановые объемы производства продуктов (вычисляются);

G2 = СУММПРОИЗВ(B$8:D$8;B2:D2);

G3:G4 – копируется из G2;

G6 – целевая функция (минимизируется);

G6 = СУММПРОИЗВ(B8:D8;B6:D6).

Ограничения:

G2:G4  F2:F4 – по объемам производства;

B2:D8  0 – неотрицательность переменных.

Целевая функция = 156600.

Переменные:

x₁=760; x₂=0; x₃=960.

Двойственные (теневые) оценки:

v₁=266,6; v₂=0; v₃=143,3.

Проанализируем решение.

Наименьшие издержки, с которыми можно произвести заданные объемы продукции, равны 156600.

Для производства выгодно использовать 760 м³ 1-го сорта леса ( ) и 960 м³ 3-го сорта леса ( ), а 2-й сорт леса не следует использовать ( ).

1-е и 3-е ограничения превращаются в равенства, т.е. 1-го и 3-го продуктов будет произведено ровно столько, сколько нужно, избытка не будет. Левая часть 2-го ограничения больше его правой части на 64 единицы. Экономически это означает, что 2-го продукта будет произведено на 64 единицы больше, чем нужно.

Почему же это произошло? Разве это оптимальный план? Ведь если произвести 2-го продукта меньше на 64 единицы, то и издержки сократятся. Это верно, но дело в том, что в данном случае лес подвергается комплексной переработке – из каждой единицы сырья производят все три вида продукции. И для того чтобы произвести 1-го и 3-го продукта ровно столько, сколько требуется, пришлось произвести 2-го продукта на 64 единицы больше необходимого. Не существует плана с меньшими издержками при данных ограничениях.

Как и в любой задаче линейного программирования двойственные оценки показывают влияние правых частей ограничений на значение целевой функции. v₁=266,6 - это означает, что дополнительная единица 1-го продукта сверх того, что требуется произвести, обойдется в 266,6. Такой экономический показатель давно известен и называется - предельные издержки. Они показывают, во что обходится производство предельной (последней) единицы продукции.

          Обсудим смысл ограничений по объемам производства продукции.  Мы хотим минимизировать издержки (затраты), и если не ввести ни одного ограничения типа - произвести данного продукта не менее заданной величины - то оптимальным планом будет - ничего не производить, т.е. все  и целевая функция равна нулю, издержки минимальны. Значит, по одному, либо по некоторым, либо по всем продуктам должно быть установлено ограничение: произвести не меньше. Совокупный смысл математической модели - произвести столько-то продукции с наименьшими затратами. Но могут быть ограничения типа: такого-то продукта, напр., с индексом k, произвести не больше заданной величины: , причем все переменные величины не отрицательные. Такие ограничения могут возникать в том случае, когда нет возможности некоторые продукты реализовать больше известной величины b_k .

          Проанализируем модель на ее разрешимость, т.е. попробуем определить есть ли хотя бы один допустимый план, и если да, то существует ли план оптимальный. Если ограничения по объемам продукции двусторонние, т.е. имеются ограничения типа «не меньше» и «не больше», то в общем случае решения может и не быть. Если же все ограничения по продуктам одного типа «не меньше», то решения нет только в том случае, когда для некоторого продукта k нет ни одного технологического способа, при котором этот продукт производится, т.е. все . Формальный признак: если в матрице технологических коэффициентов хотя бы одна строка состоит из нулей, то не существует допустимого плана. Если нулевых строк нет, то все продукты могут быть произведены, т.е. хотя бы один допустимый план существует. Но раз есть допустимые планы, при которых не все  и не все , то существует и оптимальный план с издержками больше нуля.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.3.  Общая постановка задачи линейного программирования

Любое предприятие производит продукты, затрачивая ресурсы. Продукт - результат производства, то, что  выходит из производства. Это может быть материальный продукт (хлеб, машина, кирпич, дом, книга, видеокассета), либо услуга (транспортная, парикмахерская, предоставление в аренду жилья). Ресурс – то, что используется в производстве (труд, земля, сырье, техника). Причем ресурс - это не сам человек, земля или машина, а время использования их в производстве. Продукты и ресурсы в совокупности называются ингредиентами, под которыми понимается все, что имеет отношение к производству: ресурсы входят в производство, затрачиваются, продукты выходят из производства, создаются, порождаются.

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

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

С каждым технологическим способом связан интерес человека, занятого планированием. Две противоположные постановки проблемы планирования:

а) при заданном наличии ресурсов произвести как можно больше продукции;

б) произвести заданное количество продуктов при наименьшем расходе ресурсов.

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

Введем обозначения:

j=1,…, n – номер технологического способа, его идентификатор;

i =1,…, m – номер ингредиента;

i=1,…, k - номер продукта, номера от единицы до k  присваиваем продуктам;

i = k + 1,…, m – номер ресурса,  ресурсам присваиваем номера от  k+1 до m;

a_ij - технологический коэффициент i-го ингредиента при единичной интенсивности использования j-го технологического способа;

a_ij при I ≤ k – выход( производство) i-го продукта при единичной интенсивности  j-го технологического способа;

a_ij при i > k – расход i-го ресурса при единичной  интенсивности использования j-го технологического способа;

b_i  -  ограничение на величину i-го ингредиента;

b_i при i≤ k - минимально допустимый объем производства i-го продукта; если такого ограничения нет, то b_i = 0;

b_i  при i > k - максимально допустимое значение расхода i-го ресурса; если такого ограничения нет, то b_i = ∞;

c_j  –  показатель качества плана при единичной интенсивности использования j-го технологического способа; это может быть обьем производства одного из продуктов, который нужно максимизировать, либо расход одного из ресурсов, который нужно минимизировать; это могут быть другие показатели, напр., выпуск продукции или прибыль (их нужно максимизировать) или издержки (необходимо минимизировать);

x_j – плановая интенсивность использования j-го технологического способа (переменная, неизвестная величина) .

           Условия задачи удобно записать в виде матрицы (рис. 4.3)

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

c_jx_j  -  плановый выпуск продукции j-м способом;

 –  плановый выпуск продукции в совокупности всеми способами; само выражение называется целевой функцией и ее нужно максимизировать; численная величина целевой функции называется критерием оптимальности;

a_ijx_j -  плановая величина i-го ингредиента;

a_ijx_j при i ≤ k – плановый выпуск i-го продукта j-м способом;

 при i ≤ k - плановый выпуск i-го продукта всеми способами;

 при i ≤ k - нижняя граница выпуска i-го продукта; напомним, что если такого ограничения нет, то b_i = 0;

a_ijx_j  при i > k – плановый расход i- го ресурса j-м способом;

  при i > k - плановый расход i-го ресурса всеми способами;

    при i > k - ограничение по расходу i-го ресурса (нельзя израсходовать больше b_i).

Видно, что ограничения по продуктам (не меньше) и по ресурсам (не больше) имеют противоположный смысл. С целью упрощения записи желательно привести ограничения к одному виду. Для этого обе части ограничения по продуктам умножим на -1, а знак отношения сменим на противоположный (“не больше” заменим на “не меньше”).

Последнее ограничение – величина x_j не может быть отрицательной. Технологический способ либо используется, и тогда x_j > 0, либо нет, и тогда x_j = 0. Если же допустить, что x_j < 0, это означало бы, что технологический способ работает в обратном направлении. Напр., вместо производства бензина, керосина, мазута и других продуктов будет создаваться нефть из нефтепродуктов. В большинстве случаев это технически невозможно и в любом случае - экономически нецелесообразно.

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

Найти max при ограничениях:

  

        x_j ≥ 0.

Обратим внимание на то, что данную постановку задачи можно легко превратить в противоположную. Умножив на -1 целевую фукцию и ограничения по ингредиентам, получим.

Найти  min при ограничениях:

     

      x_j ≥ 0.

Обе постановки задачи эквивалентны. Модель составлена так, что на каждый ингредиент i имеется одно и только одно ограничение.

Может случиться так, что не по каждому ингредиенту (продукту или ресурсу) устанавливается ограничение. С другой стороны, по некоторым ингредиентам могут быть два ограничения - сверху и снизу. Пусть b_i - плановая величина i-го ингредиента ,  – нижняя допустимая граница значения b_i , а - верхняя граница. Тогда количество ограничений по таким ингредиентам удвоится:

Для общности будем считать, что всегда есть нижняя  и верхняя границы. По умолчанию = 0, а = ∞. В каждом конкретном решении значения  и  уточняются.

Вектор ( x₁,…,x_j,…,x_n ) называется планом. Любой план, удовлетворяющий ограничениям, называется допустимым. При решении модели могут возникнуть три случая:

1) нет ни одного допустимого плана; в таком случае говорят,  что система ограничений несовместна, необходимо ослабить ограничения;

2) целевая функция не ограничена; это значит, что целевая функция несовместима с системой ограничений; необходимо пересмотреть модель, уточнив ограничения и целевую функцию;

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

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.3.1. Двойственная задача линейного программирования

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

 

Запишем и сопоставим математические модели основной и двойственной задач.

Доказаны следующие свойства основной и двойственной задач.

1)     Если существует решение основной задачи, то существует решение двойственной задачи, и наоборот.

2)     В оптимальном плане значения целевых функций основной и двойственной задач совпадают  .

3)     Для технологических способов, включенных в план, т.е. в случаях, когда x_j > 0 (строго больше нуля), ограничения двойственной задачи превращаются в строгие равенства: .

4)     Если в оптимальном плане ограничения  основной задачи есть строгие неравенства, т.е. если  (строго меньше), соответствующие переменные двойственной задачи равны нулю:

     (v_i = 0 ).

       Доказательств высказанных утверждений не приводим, - они являются предметом математики и рассматриваются в курсе линейного программирования.

       Остановимся на смысле двойственных оценок v_i. Математически двойственная оценка v_i есть частная производная от целевой функции основной задачи по i-му ограничению.

 

Двойственная оценка показывает, насколько изменится целевая функция основной задачи, если правую часть ограничения основной задачи (b_i) изменить на единицу. Экономический смысл двойственных оценок зависит от экономического содержания модели.

1.     Целевая функция  – продукция. Ограничение  по ресурсу. Двойственная оценка v_i есть предельная производительность i-го ресурса. Она показывает, насколько возрастет (сократится) продукция при добавлении (сокращении) i-го ресурса на единицу.

2.     Целевая функция  – издержки. Ограничения  по минимально допустимому объему производства i-го продукта.  Двойственная оценка v_i  есть предельные издержки производства i-го продукта. Она показывает во сколько обойдется производство дополнительной единицы i-го продукта.

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

 

 

В литературе встречаются различные названия двойственных оценок: объективно обусловленные оценки, оптимальные цены, теневые цены. В EXСEL они называются множителями Лагранжа.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.4 . Производственное планирование со смешанными ограничениями

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

Обозначим:

j= 1, …, n  –  номера технологических способов;

i= 1,…, m  –  номера ингредиентов;

i= 1,…, k  –  номера продуктов;

i=k+1,…, m  –  номера  ресурсов;

a_ij при i ≤ k – выход i-го продукта при единичной интенсивности j-го технологического способа;

a_ij при i > k – расход i-го ресурса при единичной   интенсивности j-го технологического способа;

p_i  -  рыночная цена i-го ингредиента (продукта или ресурса);

p_j – цена продукции, выпускаемой при единичной интенсивности j-го технологического способа;

c_j – цена издержек ресурсов при единичной интенсивности j-го  технологического способа;

r_j  -  прибыль, получаемая при единичной интенсивности j-го технологического способа;

 ,  - нижняя и верхняя границы для j-го ингредиента, выпуск продукции или расход ресурса должен находиться в этих пределах;

P  –  цена всей произведенной продукции (выпуск, выручка);

C  –  издержки производства всей продукции;

R – прибыль предприятия, полученная от выпуска всей продукции;

P_min, P_max  – нижняя и верхняя границы (ограничения) выпуска;

C_min, C_max – нижняя и верхняя границы издержек;

R_min, R_max – нижняя и верхняя границы прибыли;

x_j - плановая интенсивность использования j-го технологического способа.

Запишем формулы для вычисления промежуточных величин:

 – цена продукции, произведенной при единичной интенсивности j-го технологического способа;

 – издержки при единичной интенсивности j-го технологического способа;

 r_j = p_j-c_j - прибыль, получаемая при единичной интенсивности j-го технологического способа;

 –  цена всей продукции по плану (выпуск, выручка);

 –  полные издержки по плану;

= P-C  –  прибыль по плану;

 – величина i-го ингредиента по плану (при i ≤ k это выпуск i-го продукта, при i > k – расход i-го ресурса).

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

 Варианты целевой функции: max P; min C; max R .

 Варианты ограничений:

≤ b_i ≤ ;

P_min ≤ P ≤ P_max;

C_min ≤ C ≤ C_max;

R_min ≤ R ≤ R_max.

Методы использования модели.  Первоначально дать самые широкие возможности выбора решения - снять все ограничения, для этого назначить: = 0,  = ∞, P_min = 0, P_max = ∞, C_min = 0, C_max = ∞, R_min = 0, R_max = ∞. Далее возможны разнообразные варианты.

Вариант 1: найти максимум продукции при ограничениях на ресурсы. Придать значения  для i > k , целевая функция -  max P .

Вариант 2: найти максимум продукции при ограничениях на издержки. Все  = ∞, придать значение C_max , целевая функция  -  max P.

Варианты 3 и 4 : максимизировать прибыль. Все так же, как в вариантах 1 и 2, с заменой P на R ( цены на прибыль).

Вариант 5: минимизировать издержки при заданном выпуске продукции. Придать значения b   для i ≤ k, целевая функция  =    min C ( минимум издержек).

Вариант 6: произвольные ограничения на b_i. Выбирается одна из целевых функций P, C или R. На две другие величины устанавливаются ограничения. Может случиться так, что система ограничений будет слишком жесткой и  не окажется ни одного допустимого плана. Тогда нужно ослабить ограничения.

Пример. Условия задачи задаются матрицей.

Сверху матрицы записаны номера технологических способов: j= 1, 2, 3, 4, слева - записаны номера ингредиентов i = 1, 2, 3, 4, 5, 6, 7, причем i = 1, 2, 3 – номера продуктов, а  i = 4, 5, 6, 7 – номера ресурсов, справа - цены ингредиентов.

В клетках матрицы находятся технологические коэффициенты, причем при i ≤ 3 - выход продукции при единичных интенсивностях технологических способов, а при i > 3 - расход ресурсов при единичных интенсивностях технологических способов.

Рис. 4.4.2

Решать задачу будем с применением EXCEL. Предполагается, что студент умеет им пользоваться, даются пояснения по применению EXCEL  для решения задач линейного программирования. На рис. 4.4.2 показана таблица EXCEL  с условиями задачи.

Содержание ячеек:

В1:Е1 – имена технологических способов;

А2:А4 – имена продуктов;

А6:А9 – имена ресурсов;

В2:Е4 – технологические коэффициенты, выход продуктов при единичных интенсивностях  технологических способов;

В6:Е9 – технологические коэффициенты, расход ресурсов при единичных интенсивностях   технологических способов:

В11:Е11 – переменные ( x_j );

В13:Е13 – цена продукции, произведенной при единичных интенсивностях технологических способов ( p_j );

В14:Е14 – издержки при единичных интенсивностях технологических способов (c_j );

В15:Е15– прибыль при единичных интенсивностях технологических способов  (r_i) ;

G2:G4 – цены продуктов ( p_i );

G6:G9 – цены ресурсов ( c_i );

H2:H4 – нижняя граница объемов производства продуктов ( );

Н6:Н9 – нижняя граница расхода ресурсов ( );

I2:I4 – верхняя граница объемов производства продуктов ( );

I6:I9 – верхняя граница расхода ресурсов ( );

J2:J4 – плановый объем производства продуктов ( b_i );

J6:J9 – плановый расход ресурсов ( b_i );

J13 - плановый объем производства всей продукции в деньгах (выпуск, выручка – Р);

J14 – плановые издержки ( С );

J15 – плановая прибыль ( R );

H13:H15 – нижний предел P, C, R;

I13:I15 – верхний предел P, C, R.

Формулы для вычислений:

В13 = СУММПРОИЗВ ($G2:$G4;B2:B4);

С13:Е13 – копируются из В13;

В14 = СУММПРОИЗВ ($G6:$G9;B6:B9);

С14:Е14 – копируются из В14;

В15= В13-В14;

С15:Е15 – копируются из В15;

J2 = СУММПРОИЗВ ($B$11:$E$11;B2:E2);

J3:J4 – копируются из J2;

J6:J9 – копируются из J2;

J13 = СУММПРОИЗВ ($B$11:$E$11;B13:E13);

J14 – копируются из J13;

J15= J13-J14;

H2:H4 = 0;

H6:H9 = 0;

H13:H15 = 0;

I13:I15 = 999999;

I2:I4 = 999999;

I6:I9 = 999999.

В главном меню выбирается “Сервис”, потом “Поиск решений”. В открывшемся окне указать:

а) где находится целевая функция (J13, или J14, или J15);

б) что делать с целевой функцией (максимизировать или минимизировать);

в) где находятся переменные (В11: Е11);

г) ограничения.

Ограничения:

B11:E11 ≥ 0  -    все переменные не отрицательные;

J2:J4 ≥ H2:H4 – нижняя граница продуктов (b_i ≥  );

J2:J4 ≤ I2:I4   -  верхняя граница продуктов (b_i ≤  );

J6:J9 ≥ H6:H9  - нижняя граница ресурсов (b_i ≥ );

J6:J9 ≤I6:I9   -    верхняя граница ресурсов (b_i ≤ );

J13:J15 ≥ H13:H15 - нижняя граница выпуска (P ≥ P_min ), издержек (C ≥ C_min) и прибыли (R ≥ R_min);

J13:J15 ≤ I13:I15 - верхняя граница выпуска (P ≤ P_max ), издержек (C ≤ C_max) и прибыли     ( R ≤ R_max).

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

   Вариант 1. Максимизировать выпуск продукции (max P) при ограничениях на ресурсы: =100, = 200, = 60, = 300. Заносим в ячейки I6 = 100, I7 = 200, I8 = 60, I9 = 300. Ячейку J13 указываем как целевую функцию. Даем команду “Выполнить” и получаем решение:

а) целевая функция (выпуск) Р = 1873,14;

б) переменные: х₁ = 0; х₂ = 0; х₃ = 88,34; х₄ = 151,94;

в) расход ресурсов и двойственные оценки приведены в таблице.

 

 

Видно, что сработали ограничения по второму и четвертому ресурсу, их израсходовано ровно столько, сколько было. А вот первый и третий ресурсы оказались в избытке. Очень важный показатель – двойственные оценки. В EXCEL’e  их можно найти в “отчете по устойчивости” под названием “ Лагранжа множители”. В данном случае двойственные оценки есть  предельные производительности ресурсов. Они показывают, насколько увеличится (уменьшится) целевая функция при добавлении (сокращении) единицы ресурса. Т.к. v₁ = 0, это значит, что добавление единицы первого ресурса к 100 не изменит решение и целевую функцию. Но так оно и должно быть, т.к. первый ресурс имеется в избытке. В избытке третий ресурс, и его двойственная оценка v₃ = 0. Ресурсы второй и четвертый использованы полностью, именно поэтому v₂ = 0,249 v₄ = 6,072. Добавление (убавление) единицы второго ресурса увеличит (уменьшит) целевую функцию на 0,249. Аналогично добавление (убавление) единицы четвертого ресурса увеличит (уменьшит) целевую функцию на 6,072.

   Вариант 2. Максимизировать продукцию (max P) при ограничениях на издержки (C ≤ C_max). Ограничения задаются не на  каждый ресурс, а на сумму издержек. Каждый новый вариант начинается с восстановления первоначального состояния модели, изображенной на    рис. 4.4.2. Это значит, что все минимальные значения в столбце Н должны быть равны нулю, а все максимальные значения в столбце I - равны бесконечности (большому числу); все переменные в строке 11 обнуляются.  Пусть издержки ограничены сверху, напр., C ≤ 5000. В ячейку  I14  заносим 5000, объявляем целевой функцией ячейку I13, и даем команду на выполнение.

Решение:

а) продукция  Р = 11198,7;

б) переменные х₁ = 0; х₂ = 0; х₃ = 1577,29; х₄ = 0;

в) двойственная оценка ограничения по издержкам v = 2,24.

   Вариант 3. Минимизировать издержки при заданных минимальных объемах продукции: = 100, = 60, = 120. Приводим модель в начальное состояние. Затем задаем минимальные значения продукции в ячейках: Н2 = 100, Н3 = 60, Н4 = 120. Целевая функция в ячейке J14.

Решение:

а) целевая функция (издержки) С = 414,85;

б) переменные х₁ = 0; х₂ = 35,8; х₃ = 86,93; х₄ = 1,14;

в) двойственные оценки ограничений по продуктам: v₁ = 1,55; v₂ = 2,68; v₃ = 0,82; двойственные оценки показывают, во что обойдется дополнительная единица каждого продукта, это предельные издержки.

   Вариант 4. Максимизировать прибыль при смешанных ограничениях (на продукты, ресурсы, издержки).

 Ограничения:

а) второго продукта произвести не меньше 100 ( = 100) ;

б) четвертого ресурса истратить не более 200 единиц ( = 200);

в) издержки не должны превышать 400 (С_max= 400) .

 Приводим модель в начальное состояние. Присваиваем значения ячейкам:     H3 = 100, I9 = 200, I14 = 400. Объявляем целевой функцией ячейку  J15.

Решение:

а) целевая функция (прибыль) R =258,52;

б) переменные х₁ = 0; х₂ = 0; х₃ = 20,49; х₄ = 62,57;

в) двойственные оценки по ограничениям:

по второму продукту v = -3,82, это означает, что второй продукт производить невыгодно, дополнительная единица второго продукта снижает прибыль на 3,82;

по четвертому ресурсу v = 0, дополнительная единица второго ресурса не повышает прибыль, т.к. ресурс недоиспользуется;

ограничения по издержкам v = 1,6, дополнительная единица издержек повышает прибыль на 1,6.

 Замечание. В общей постановке задачи линейного программирования говорилось, что переменные основной ( х ) и двойственной ( v ) задач неотрицательны, а в последнем варианте v = -3,82 . Действительно, в модели двойственные оценки не отрицательны (v ≥ 0). Но для облегчения анализа EXCEL присваивает знаки. Если дополнительная единица уменьшает значение целевой функции, то двойственной оценке присваивается знак «минус».

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.5.   Раскрой  прутьев

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

     Обозначим:

i = 1,…, m -  номера деталей в комплекте;

k_i – количество i-х деталей в комплекте;

l - длина заготовки;

l_i - длина i-ой детали;

Q – количество заготовок;

N - количество комплектов.

    Каждую заготовку можно разрезать на различное количество деталей. Нужно составить всевозможные варианты раскроя.

j = 1,…, n  –  номера вариантов раскроя;

x_j  –  количество заготовок, раскраиваемых по j-му варианту;

a_ij  -  количество i-х деталей в j-м варианте раскроя.

Составим матрицу вариантов раскроя (рис. 4.5.1.)

 Задача может решаться в двух вариантах.

Вариант 1. Задано количество заготовок Q, нужно максимизировать количество комплектов.

Целевая функция  -  max N.

Ограничения:

;

;

x_j ≥ 0;

x_j - целое;

N ≥ 0.

Анализируем смысл ограничений:

a_ijx_j – количество i-х деталей, которые можно получить, раскроив x_j заготовок по j-му варианту;

- общее количество i-х деталей, получаемое по всем вариантам раскроя;

k_iN  –  количество i-х деталей, которое требуется для N  комплектов;

x_j ≥ 0 – по j-му варианту разрезается x_j заготовок, либо нисколько не разрезается;

x_j - целое; здесь появляется требование целочисленности решения, т.к. резать нужно целое количество заготовок.

 Нельзя требовать, чтобы количество комплектов N  было целым. Конечно же, можно использовать только целое число комплектов. Но пусть некоторое количество деталей будет лишним, только бы N  было максимальным, пусть и дробным.

Вариант 2. Задано количество комплектов N. Нужно минимизировать количество разрезаемых заготовок. Составим математическую модель.

Целевая функция  -  .

Ограничения:

;

x_j ≥ 0;

x_j – целое.

Экономический смысл модели очевиден.

Численный пример.  Вариант 1. Имеется  882  заготовки длиной 7,15 м. Из них нужно нарезать детали длиной 2 и 1,4 м. В комплект входят 3 детали длиной 2 м. и 5 деталей длиной 1,4 м. Требуется максимизировать количество комплектов. Составим варианты раскроя.

   Из заготовки можно нарезать 0, 1, 2 или 3 длинных деталей (2 м.). Если не резать ни одной длинной детали, то из заготовки можно нарезать  5 коротких (1,4 м). При  одной длинной детали из остатка можно получить 3 коротких, при двух длинных – 2 коротких, при трех длинных – 0 коротких. Вот и все 4 варианта. Варианты раскроя запишем в виде таблицы:

   Составим математическую модель задачи.

Вариант 1.

    Целевая функция: найти max N.

 Oграничения:

x1	+	x2	+	x3	+	x4	≤	882;
0x1	+	1x2	+	2x3	+	3x4	≥	5N;
5x1	+	3x2	+	2x3	+	0x4	≥	5N;
x1							≥	0;
		x2					≥	0;
				x3			≥	0;
						x4	≥	0;

     x₁, x₂, x₃, x₄ – целое.

Таблица EXCEL показана на рис. 4.5.2.

Рис. 4.5.2.

Содержание ячеек:

В1:Е1 – имена вариантов;

А2:А3 – имена деталей;

В2:Е3 – матрица деталей по вариантам;

А5:Е5 – переменные x_j;

F5 – переменная N (количество комплектов);

В6 = 882 – количество заготовок;

G2:G3 – количество деталей в комплекте;

Н2:Н3 – количество деталей в N комплектах (вычисляется);

H2 = F5*G2;

H3 = F5*G3

I2:I3 – количество нарезанных деталей по плану;

I5 = СУММ(В5:Е5) – количество заготовок разрезанных по плану;

I2 = СУММПРОИЗВ(В$5:E$5;B2:E2);

I3 – скопировать из I2.

Ограничения:

В5:F5 - неотрицательность переменных;

В5:Е5 – целое;

I2:I3 Н2:Н3;

I5 B6.

Решение.

Значение целевой функции равно 463,8.

N=463 - округляем до меньшего целого;

x₁=185; x₂=0; x₃=697; x₄=0.

Проанализируем это решение.

По 1-му варианту нужно разрезать 185 прутьев, по 3-у 697, 2-й и 4-й варианты не используются. Будет получено 463 комплекта.

Вариант 2. Изготовить 300 комплектов с минимальным расходом заготовок.

Математическая модель.

Целевая функция

Найти min (x₁ + x₂ +x₃ +x₄) – минимизировать общий расход заготовок.

Ограничения:

0x1	+	1x2	+	2x3	+	3x4	≥	3 ;
5x1	+	3x2	+	2x3	+	0x4	≥	5 ;
x1							≥	0;
		x2					≥	0;
				x3			≥	0;
						x4	≥	0;

     x₁, x₂, x₃, x₄ – целое.

Таблица EXCEL показана на рис. 4.5.3.

Рис. 4.5.3.

Содержание ячеек:

В1:Е1 – имена вариантов;

А2:А3 – имена деталей;

B5:Е5 – переменные;

F5 = 300 – количество комплектов;

G2:G3 – количество деталей в комплекте;

Н2:Н3 – количество деталей в заданном количестве комплектов;

H2 = F5*G2;

H3 = F5*G3

I2:I3 – количество деталей по плану;

I2 = СУММПРОИЗВ(В$5:E$5;B2:E2);

I3 – скопировать из I2;

I5 = СУММ(В5:Е5) – целевая функция (количество разрезанных заготовок).

Ограничения:

В5:F5 - неотрицательность переменных;

В5:Е5 = целое;

I2:I3 Н2:Н3;

Решение.

Целевая функция = 570, это значит, что нужно разрезать 570 заготовок, чтобы получить 300 комплектов.

Переменные: x₁=120; x₂=0; x₃=450; x₄=0. По 1-му варианту нужно разрезать 120 заготовок, по 3-му – 450 заготовок, 2-й и 4-й варианты не используются.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.6.  Раскрой листов

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

Обозначим :

i = 1,..,m – номера деталей;

k_i – количество i-х деталей в комплекте ;

j = 1,…,n – номера вариантов раскроя ;

a_ij – количество i-х деталей в j-ом варианте раскроя;

c_j – издержки раскроя листа по j-му варианту ;

x_j – плановое количество листов, раскраиваемых по j-му варианту;

 - издержки раскроя всех листов;

C_min,C_max – нижний и верхний пределы издержек ;

N – количество комплектов.

Условия задачи задаются матрицей (рис. 4.6.1).

Математическая модель.

  Вариант 1. Заданы издержки (C_max), требуется максимизировать количество комплектов N.

Найти max N при ограничениях:

C ≤ C_max;

;

x_j ≥ 0;

N ≥ 0;

x_j - целое.

  Вариант 2. Задано количество комплектов N, требуется минимизировать издержки.

Найти min C при ограничениях:

;

x_j ≥ 0;

x_j – целое.

Таблица EXСEL показана на рис. 4.6.2.

Рис. 4.6.2.

Содержание ячеек:

B1:F1 – имена  вариантов раскроя;

А2:А5 – имена  деталей;

B2:F5 – количество деталей по вариантам раскроя ( a_ij);

B7:F7 – издержки раскроя листа по вариантам (c_j);

H2:H5 – количество деталей в комплекте (k_i);

B9:F9 – переменные (x_j);

G9 – переменная (N);

I2:I5 – плановое количество i–х деталей ( );

J2:J5 – количество i – х деталей, требующихся для  N комплектов (k_iN);

H9 – нижняя граница издержек (C_min);

I9 – верхняя граница издержек (C_max);

J9 – издержки (С).

Формулы для вычислений:

I2 = СУММПРОИЗВ($B$9:$F$9;B2:F2);

I3:I5 –  копируются из I2;

J2 = H2*$G$9;

J3:J5 – копируются из J2;

H9 = 0;

I9 = 99999;

J9 = СУММПРОИЗВ(B9:F9;B7:F7);

Ограничения:

I2:I5 ≥ J2:J5 – по требуемому количеству деталей ;

J9 ≥ H9 – нижний предел издержек (C ≥ C_min);

J9 ≤ I9 – верхний предел издержек (C ≤ C_max);

B9:G9 ≥ 0 – неотрицательность переменных ;

B9:F9 – целые.

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

   Вариант 1. Задан верхний предел издержек C_max=10000, требуется максимизировать количество комплектов N. В ячейку I9 записать 10000. Целевой функцией объявить max G9, переменными B9:G9.

Решение:

а) целевая функция = 1270,75, т.е. будет получено 1270 комплектов и еще детали на 0,75 комплекта;

б) переменные x₁=847,  x₂=0,  x₃=1,  x₄=0,  x₅=1058;

в) издержки по плану = 9998,3 < 10000; израсходовано меньше 10000, т.к. режется целое количество листов;

Вариант 2. Задано количество комплектов N=100, требуется минимизировать издержки.

Переменными объявить клетки B9:F9 (теперь G9 – не переменная ).

Ввести в G9 = 100, I9 = 99999. Целевой функцией объявить min J9.

Решение:

а) целевая функция С =788;

б) переменные x₁=66, x₂=0, x₃=1, x₄=0, x₅=83;

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.7.   Транспортная  задача

Планируется перевозка какого-либо груза от поставщиков к потребителям.

Условия задачи заданы матрицей (рис. 4.7.1).

Обозначим:

i = 1,…, m  –  номера поставщиков;

b_i  –  мощность (запас груза) i-го поставщика;

j = 1,…, n – номера потребителей;

a_j  –  потребность (спрос) j-го потребителя;

c_ij  –  издержки на перевозку единицы груза от i-го поставщика j-му потребителю ;

x_ij  –  плановый объем перевозок груза от i-го поставщика j-му потребителю;

 -  общие затраты на перевозку (целевая функция).

Затраты на перевозку могут измеряться:

а) в деньгах, тогда c_­ij  –  тариф на перевозку;

б) в тонно-километрах перевозочной работы, тогда c_ij - расстояние между i-м поставщиком и j-м потребителем в километрах;

в) в расходе горючего и т.д.

Задача имеет решение только тогда, когда общий запас груза у поставщиков не меньше общей потребности в нем   -   необходимое условие.

Запишем математическую модель задачи.

Найти min ;

при ограничениях:

 ≥ a_j;       ≤ b_i;        x_ij ≥ 0.

Задачу можно решить без компьютера, напр., методом потенциалов. Есть  также разнообразные программные средства: EXCEL,  разработанный в АмГУ пакет “Транспорт”, и другие.

На рис.4.7.2 показан пример транспортной задачи в таблице EXCEL.

Рис.4.7.2

Распределение табличного пространства:

а) B2:F5  –  матрица тарифов (c_ij );

б) B1:F1 –  имена потребителей;

в) A2:A5, А9:A12  – имена поставщиков;

г) Н2:Н5  –  запас груза у поставщиков (b_i);

д) B7:F7  –  спрос потребителей (a_j);

е) В9:F12  –  переменные (x_ij);

ж) B14:F14  –  получено потребителями по плану  ( );

з) H9:H12  –  вывезено от поставщиков ( );

и) B16:F16  –  расходы потребителей на перевозку ( );

к) H16  -  общие расходы на перевозку  (целевая функция = ).

Вычисления по формулам:

B14 = СУММ( B9:B12);

C14:F14 -  получаются копированием из В14;

Н9 = СУММ (B9:F9);

H10:H12 -  получаются копированием из Н9;

В16 = СУММПРОИЗВ(B2:B5;B9:B12);

C16:F16  -  получаются копированием из В16;

Н16 = СУММ (B16:F16).

Ограничения :

B14:F14 = В7:F7  –  по спросу потребителей;

H9:H12 ≤ H2:H5  –  по мощности поставщиков;

B9:F12 ≥ 0  –  неотрицательность переменных;

Целевая функция = min H16.

 

Результат решения показан в таблице EXCEL на рис. 4.7.3.

 

Рис. 4.7.3.

Решение:

а) целевая функция = 790;

б) переменные – х₄₁ = 30; х₃₂ = 50; х₄₂ = 20; х₃₃ = 10; х₃₄ = 15; х₁₅ = 60; х₂₅ = 20; х₃₅ = 10.

в) двойственные оценки по поставщикам v₁ = -5; v₂ = -6; v₃ = 0; v₄ = -1.

г) двойственные оценки по потребителям v₁ = 4; v₂ = 6; v₃ = 3; v₄ = 4; v₅ = 7.

Проанализируем двойственные оценки ограничений:

а) по поставщикам v₁ = -5, v₂ = -6, v₃ = 0, v₄ = -1; увеличение мощности поставщиков на единицу снижает значение целевой функции на величину v_i. Т.к. у третьего поставщика мощность избыточна ( 120, а требуется 85), то v₃=0.

б) по потребителям v₁ = 4, v₂ = 6, v₃ = 3, v₄ = 4, v₅ = 7, эти оценки показывают, во что обойдется дополнительная единица груза, требующаяся каждому потребителю.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.8.          Планирование посевов

Имеется несколько участков сельскохозяйственной земли различного качества (плодородия) и несколько зерновых культур, которые нужно вырастить на этих участках. Введем обозначения.

Известные величины:

i = 1,…, m  – номера культур;

j =1,…, n  –  номера участков;

s_j  –  площадь j-го участка в гектарах (га);

a_ij  -  урожайность i-й культуры на j-м участке в центнерах/га;

с_ij  –  издержки выращивания i-й культуры на j-м участке в тыс. руб./га;

p_i  -  цена i-й культуры в тыс. руб./ц.

Неизвестные (плановые ) величины:

x_ij  -  площадь j-го участка, засеваемая i-ой культурой.

Вычисляемые величины:

A_i -  объем производства i-й культуры на всех участках;

A_i = ;

P_i – цена всей произведенной i-й культуры (объем производства i-й культуры, выпуск, выручка),

P_i= p_iA_i;

C_i – издержки на производство i-ой культуры в тыс. руб./ц.,

C_i= ;

R_i – прибыль от производства i-й культуры,

R_i=P_i-C_i.;

- валовая продукция (выпуск);

- валовые издержки;

R = P – C – валовая прибыль.

              Предельные величины.

A , A – нижний и верхний пределы значений А_i; начальные значения A =0,  A = ∞  .

P_min, P_max, C_min, C_max ,R_min, R_max – нижние и верхние пределы объема производства, издержек и прибыли; начальные нижние значения – ноль, верхние – бесконечность.

       Запишем математическую модель, включающую все возможные варианты.

 Варианты целевой функции maх P, min C, maх R.

Ограничения:

≤ s_j   –  по площади участков;

x_ij ≥ 0 – неотрицательность переменных;

A ≤A_i ≤ A – по объемам производства культур;

P_min≤P ≤ P_max – по валовому продукту;

C_min≤C ≤ C_max – по валовым издержкам;

R_min≤R ≤ R_max – по валовой прибыли.

Пример решения. Условия задачи показаны на рис 4.8 в таблице EXCEL.

Рис 4.8

Значения ячеек в таблице:

А2:А6 = А8:А12 = А14:А18 – имена культур;

В1:Е1 – названия участков;

В2:Е6 – урожайность культур по участкам;

В8:Е12 – издержки обработки 1 га земли по участкам и культурам;

В14:Е18 – переменные (x_ij);

В20:Е20 – плановые посевы на каждом участке ( );

В21:Е21 – площади участков (s_j);

G2:G6 – рыночные цены культур;

J2:J6 – плановые объемы производства культур (A_i = );

J14:J16 – плановые величины выпуска, издержек, прибыли (P, C, R);

G8:G12 – плановый объем производства культур в денежном выражении (p_iA_i);

H8:H12 – плановые издержки производства культур   ( c_i= );

I8:I12 – плановая прибыль от производства культур    (R_i=A_i-C_i).

Формулы для вычислений:

В20 = СУММ(В14:В18);

С20:Е20 – копируются из В20;

J2 = СУММПРОИЗВ (В14:Е14;В2:Е2);

J3:J6 – копируется из J2;

G8 = J2*G2;

G9:G12 - копируются из G8;

H8 = СУММПРОИЗВ (В14:Е14;В8:Е8);

H9:H12 - копируются из H8;

I8 = G8 – H8;

I9:I12 - копируются из I8;

J14 = СУММ(G8:G12);

J15 = СУММ(H8:H12);

J16 = J14 - J15.

Ограничения:

В14:Е18 ≥ 0 –  неотрицательность переменных (x_ij ≥ 0);

В20:Е20 ≤ B21:E21 – посевы на каждом участке не превышают его площадь ( ≤ s_j);

Варианты задачи.

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

Целевая функция max J14 = 435000.

Значения переменных:

x₁₁= 100, x₄₂=200, x₄₃=250, x₅₄=400, остальные переменные равны нулю. Это значит, что пшеницей нужно засевать полностью первый участок, гречихой полностью второй и третий участки, соей плностью четвертый участок, рожь и овес сеять невыгодно.

Двойственные оценки ограничений по площадям участков:

v ₁ = 450, v₂ = 400, v₃ = 440, v₄ = 500.

Это означает следующее: увеличение (уменьшение) площади первого участка увеличивает (уменьшает) объем производства на 450 тыс. руб; так оно и есть – на первом участке выгодно сеять пшеницу, ее урожайность равна 30 ц, а цена 15 тыс. руб/ц, т.е. 1 га увеличивает выручку на 450 тыс. руб. Аналогично 1 га второго , третьего и четвертого участков увеличивают выручку на 400, 440 и 500 тыс. руб. Двойственная оценка в данном случае – земельная рента.

Вариант 2. Максимизировать прибыль при ограничении общих издержек ( C ≤ 50 000 тыс. руб.).

Привести систему в начальное состояние. Ввести I15 = 50000. Добавить ограничение J15 ≤ I15. Назначить целевой функцией max J16. Запустить решение.

Решение:

а) целевая функция = 43148,15 тыс. руб;

б) переменные: х₁₁ = 100,  x₅₄ = 96,3 га; это значит, что нужно засеять пшеницей весь первый участок, соей 96,3 га четвертого участка, на остальные культуры и участки средств недостаточно;

в) двойственная оценка ограничения по издержкам v = 1,85 тыс. руб., значит, каждый дополнительный рубль издержек принесет 1,85 рубля прибыли. В данном случае двойственная оценка  - предельная эффективность издержек.

Вариант 3. Минимизировать издержки при заданных объемах производства культур: пшеница = 2500 ц; рожь = 3000 ц; овес = 2000 ц; гречиха = 400 ц; соя = 5000 ц.

          Привести систему в начальное состояние, как на рис 4.8. Устранить  ограничение J15 ≤ I15. Добавить ограничение на J2:J6  Н2:Н6. Ввести значения A в ячейки: H2=2500, H3=3000, Н4 = 2000, H5=400, H6=5000. Назначить целевой функцией min J15.

Решение:

а) целевая функция = 131197 тыс. рублей;

б) переменные: x₁₁=83,33, x₂₁=16,67, x₂₂=100, x₂₃=30,83, x₃₂=100, x₄₃=18,18, x₅₄=250, oстальные переменные равны нулю, - это значит, что на первом участке нужно засеять 83,33 га пшеницей и 16,67 га рожью, на втором участке 100 га засеять рожью и 100 га овсом, на третьем 30,83 га засеять рожью и 18,18 га гречихой,  соей засеять 250 га на четвертом участке.

в) двойственные оценки ограничения по площадям участков:

v₁ = -40, v₂ = -5, v₃ = 0,  v₄ = 0; это значит, что дополнительный гектар на первом участке снижает издержки производства заданных объемов продукции на 40 тыс. рублей, а дополнительный гектар на втором участке снижает издержки на 5 тыс. рублей, соответственно дополнительные гектары на остальных участках ничего не дают,  т.к. их площади  недоиспользуются.

г) двойственные оценки ограничений по продукции v₁ = 9,33, v₂ = 10, v₃ =  5,5, v₄ = 10,91, v₅ = 13,5 – это предельные издержки производства пшеницы, ржи, овса, гречихи и сои.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.9.          Использование оборудования

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

Обозначим :

i = 1,…, m – номера обрабатываемых деталей;

j = 1,…, n – номера комплектов оборудования;

j = 1,…, k – номера имеющегося на предприятии оборудования;

j = k+1,…, n – номера видов оборудования, из которых нужно выбрать самый эффективный;

a_ij – сменная производительность j-го вида оборудования по i-й детали, т.е. сколько i-х деталей изготавливает за смену j-й вид оборудования;

c_ij – издержки обработки i-й детали на j-ом виде оборудования;

k_j – количество имеющихся комплектов j-го вида оборудования;

x_ij – плановая загрузка j-го вида оборудования обработкой i-й детали в сменах;

x_j = - плановая загрузка j-го вида оборудования в смену;

b_ij = a_ijx_ij – плановое производство i-й детали на j-м виде оборудования за смену;

b_i = - плановое производство i-й детали на всех видах оборудования за смену;

b , b – нижний и верхний пределы планового производства i-ой детали за смену;

С =  –  издержки на производство всех деталей на всех видах оборудования за смену.

Условия задачи запишем в виде матриц производительности (рис. 4.9.1) и издержек (рис. 4.9.2).

Математическая модель.

Найти min C при ограничениях:

b_i ≥ b - произвести не меньше b ;

b_i≤ b - произвести не больше b ;

x_j ≤ k_j  - плановая загрузка не может превышать имеющуюся мощность оборудования;

x_j ≥ 0  –  неотрицательность переменных.

Решим пример. Запись условий задачи показана на рис 4.9.3.

Рис. 4.9.3

На предприятии имеется два вида оборудования: первое (j=1) - в неограниченном количестве, второе (j=2) – один комплект. Предполагается закупить или взять в аренду (лизинг) один из двух видов оборудования (j=3 или j=4).

Содержание таблицы EXCEL на рис 4.9.3.

В1:Е1 - имена оборудования;

А2:А4 = А6:А8 =А10:A12 = А17:А19 – имена деталей;

В2:Е4 – производительность оборудования  –  штук в смену (a_ij);

В6:Е8 – издержки производства каждой детали на каждом виде оборудовании (c_ij);

В10:Е12 – переменные (x_ij);

В14:Е14 – загрузка каждого оборудования в сменах ( );

В15:Е15 – наличие каждого оборудования (k_j);

В17:Е19 – плановое производство каждой детали на каждом оборудовании (a_ijx_ij);

G2:G4 – минимальная потребность деталей в смену ( b );

I2:I4 – плановое производство деталей в смену (b_i);

I6:I8 – плановые издержки производства каждой детали ( );

I9 – плановые издержки производства всех деталей ( ) – целевая функция.

Вычисляемые величины:

В14 = СУММ (В10:В12),  С14:Е14 копируются из В14;

В17 = В10*В2; В17:Е17 (кроме В17) копируются из В17;

I2 = СУММПРОИЗВ(В2:Е2; В10:Е10); I3:I4 копируются из I2;

I6 = СУММПРОИЗВ(В10:Е10;В6:Е6); I7:I8 копируются из I6;

I9 = СУММ(I6:I8).

Ограничения:

B10:E12 ≥ 0 – неотрицательность переменных ;

B14:E14 ≤ B15:E15 – по наличию оборудования;

I2:I4 ≥ G2:G4 – по потребности в деталях;

Целевая функция = min I9.

Третьего и четвертого видов оборудования еще нет, т.е. к₃ = к₄ = 0.

Решение:

а) целевая функция = 2734,56;

б) переменные запишем в виде матрицы;

в) двойственные оценки:

по оборудованию v₁=0, v₂=-658, v₃=-1815,25, v₄=-2327,25.

по деталям v₁ = 4,25, v₂ = 3,62, v₃ = 6,28.

Проанализируем результаты решения. Второй вид оборудования нужно полностью загрузить производством первой детали, а вторую и третью детали и недостаток первой до нормы производить на первом, самом неэффективном  виде оборудования. Может показаться странным, что в план включены третий и четвертый виды оборудования, которых у предприятия еще нет. Это сделано для того , чтобы получить двойственные оценки этого оборудования, которые равны соответственно v₃ = -1815,25 руб. и v₄ = -2327,25 руб. Двойственные оценки показывают какую экономию на издержках приносит каждый вид оборудования. Какой вид оборудования выгодно взять, зависит от арендной платы за смену. Если, например, за 3-е оборудование требуется 1000 руб. в смену, а за 4-е – 2000 руб. в смену, то выгоднее взять 3-е оборудование.

Двойственные оценки по деталям являются предельными издержками.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.10.    Задача о диете  (о смесях)

Человек ежесуточно должен потреблять определенное количество калорий, белков, жиров и углеводов; назовем все это ингредиентами.

Известны:

а) набор доступных продуктов;

б) количество ингредиентов в единице каждого продукта;

в) суточная потребность в ингредиентах;

г) цена продуктов.

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

Условия задачи задаются матрицей (рис. 4.10.1).

i=1,…,m – номера ингредиентов;

j=1,…,n – номера продуктов;

a_ij – содержание i-го ингредиента в единице j-й продукции;

x_j  - плановый объем суточного потребления j-го продукта;

b_i= - плановое содержание i-го ингредиента в диете (суточном наборе продуктов);

b ,b - нижняя и верхняя границы для b_i;

p_j – цена единицы j-го продукта;

P= - цена суточного набора продуктов, целевая фунуция;

x , x - ограничения на количество j-го продукта в диете .

Математическая модель задачи:

Найти min P,

при ограничениях :

b ≤ b_i ≤ b ;

x ≤ x_j ≤ x ;

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

 

 

Содержание ячеек в таблице EXCEL на рис. 4.10.2:

В1:J1 – имена продуктов;

А2:А5 – имена ингредиентов;

B2:J5 – содержание ингредиентов в продуктах (a_ij);

B7:J7 – цены продуктов (p_j) в руб. за кг.;

B9:J9 – переменные (x_j);

B11:J11 – максимально допустимое количество j-го продукта (x );

B12:J12 – минимально допустимое количество j-го продукта (x );

L2:L5 - минимально допустимое количество i-го ингредиента (b );

М2:М5 - максимально допустимое количество j-го ингредиента (b );

N2:N5 – количество i-го ингредиента в диете;

N7 – цена суточной диеты по плану.

Запись условий задачи в таблице EXCEL показана на рис 4.10.2.

Рис 4.10.2

Формулы для вычислений:

N2=СУММПРОИЗВ($B$9:$J$9,B2:J2),  N3:N5 получаются копированием из N2;

N7 = СУММПРОИЗВ(B9:J9;B7:J7).

Ограничения:

B9:J9 ≥ B12:J12 – по нижнему пределу потребления продуктов;

B9:J9 ≤ B11:J11 – по верхнему пределу потребления продуктов;

N2:N5 ≥ L2:L5 - по нижнему пределу потребления ингредиентов;

N2:N5 ≤ M2:M5 - по верхнему пределу потребления ингредиентов;

Целевая функция = min N7.

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

Решение:

а) целевая функция = 16,31;

б) x₅=0,099 (масло); х₇=1,561 (хлеб);  остальные переменные равны нулю;

в) при этом будут получены следующие результаты (табл.).

 

По плану можно прожить сутки на 16 руб. 31 коп., если съедать 1,5 кг. хлеба и 100 г. сливочного масла. При этом белки и жиры будут получены в норме, а калории  и углеводы – с избытком. Двойственные оценки показывают во сколько обойдется дополнительная (сверх нормы) единица ингредиентов. Естественно, что двойственные оценки калорий и углеводов равны нулю, т.к. эти ингредиенты получены в избытке, дополнительный грамм белков и жиров обойдется соответственно в 9,1 коп. и 8,4 коп.

Вариант 2. В жизни требуется иногда не только обеспечивать минимум, но и не превышать максимум ингредиентов. Люди, склонные к полноте, вынуждены ограничивать диету в калориях, а при некоторых заболеваниях – также в жирах и углеводах. В первом варианте углеводов получено почти в два раза больше нормы. Поставим условие: чтобы углеводов было получено не более 500 г., для чего введем в ячейку М5 число 500.

Решение:

а) целевая функция = 17,74 руб. вместо 16,31 в  варианте 1; это естественно – ужесточение ограничений всегда ухудшает значение целевой функции;

б) х₁=0,15 (камбала); х₅=0,099 (масло); х₇=1,15; как видно, уменьшено количество хлеба, но добавилось в набор 150 г. рыбы, как содержащей существенно меньше углеводов, чем хлеб;

в) другие данные приведены в таблице.

 

Отрицательное значение двойственной оценки по углеводам говорит о том, что допущение большего количества углеводов, чем 500 г., позволит снизить суточные издержки на питание.

Вариант 3. Полученный набор отвечает медицинским требованиям, но вряд ли покажется вкусным человеку. В литературе рассказывается, что при первоначальном решении задачи о диете для американских студентов было получено самое дешевое меню: овсянка. В нашем наборе овсянки нет, она, скорее всего, стала бы лидером. Если человек не просто желает удовлетворить свои потребности в ингредиентах, но и получить вкусное меню, он должен расширить набор продуктов и ужесточить ограничения  по потреблению тех продуктов, которые он желает или не желает видеть в наборе. В данном примере поставим условие, чтобы в меню было сахара не менее 20 г., а потребление хлеба не превышало 0,5 кг. Для этого назначим С12=0,02,  Н11=0,5. Получим решение:

а) целевая функция = 18,17 руб.;

б) переменные: х₁=0,146 кг (камбала); х₂=0,02 кг (сахар); х₅=0,102 кг (масло); х₆=0,364 кг (макароны); х₇=0,5 кг (хлеб);

в) количество ингредиентов и двойственные оценки показаны в таблице.

 

Можно составить различное меню на каждый день недели или месяца.

 Общие замечания по задаче.

1. Трудно представить, чтобы человек подобным образом планировал свое питание. Это происходит потому, что в развитых государствах затраты на питание незначительны – от 16 до 20% семейного бюджета.

2. Задача о диете может использоваться и в других случаях:

а) рацион откорма скота, птиц, рыб, кормления животных в зоопарке;

б) смеси удобрений для выращивания зерновых культур в сельском хозяйстве;

в) смеси в металлургии и химическом производстве.

      Можно найти и другие применения данной задачи.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

4.11.     Задача о назначениях

Пусть имеется n вакантных мест (должностей) и на них нужно распределить n кандидатов оптимальным образом, чтобы предприятие (организация) получило  от этого наибольший выигрыш. Необходимо как-то оценивать эффект от назначений. Это можно сделать, напр., следующим образом. Менеджер по кадрам оценивает по 10-балльной системе, насколько каждый кандидат подходит к каждой должности. Целевая функция – сумма выигрышей от распределения.

Задача о назначениях может иметь множество приложений. Напр.,  распределение спортсменов по парам в фигурном катании, в спортивных танцах, в теннисе и т.д. В военном деле: имеется n целей и n средств поражения (ракет), нужно так распределить средства поражения, чтобы нанести наибольший урон противнику.

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

Обозначим:

i =1,..,n – множество кандидатов;

j = 1,…,n – множество вакантных мест;

c_ij – оценка распределения i-го кандидата на j-е место;

x_ij – переменная для назначения i-го кандидата на j-ое место, может принимать значения 0 или 1.

Условия задачи определяются матрицей (рис. 4.11.1).

Математическая модель:

Найти maх ;

при ограничениях:

1

xij =

0

- либо 0, либо 1;

            

                                 

= 1 – каждый кандидат должен получить назначение и только на одно место;

= 1 - на каждое место должен быть назначен один и только один кандидат.

Рис. 4.11.2

Условия задачи показаны на рис 4.11.2 в виде таблицы EXCEL.

Содержание ячеек:

B1:F1 – имена должностей (мест);

A2:A6 = A8:A12 – имена кандидатов;

B2:F6 – оценки (c_ij);

B8:F12 – переменные (x_ij);

B14:F14 – итог по местам  ( );

Н8:Н12 – итог по кандидатам  ( );

I14 – целевая функция  ( ).

Формулы для вычислений:

В14 = СУММ (В8:В12),  С14:F14 – копируются из В14;

Н8 = СУММ (В8:F8),  H9:H12 - копируются из H8;

I14 = СУММПРОИЗВ(B2:F6;B8:F12).

Ограничения :

B8:F12 = булевы (двоичные);

B14:F14 = 1;

H8:H12 = 1.

Целевая функция = max I14.

Решение:

а) целевая функция = 42;

б) переменные в матрице (рис. 4.11.3).

x₁₂=1,  x₂₄=1,  x₃₁=1,  x₄₅=1,  x₅₃=1. Остальные переменные равны нулю.

 

(НАЧАЛО) (СОДЕРЖАНИЕ)

 

(НАЗАД) (ДАЛЕЕ)