Орлов А.И. Менеджмент (2003) (1142166), страница 56
Текст из файла (страница 56)
При этом прямая 45 Х1 + 80 Х2 =2200 проходит между прямыми ограничений 5 Х1 + 20 Х2 = 400 и 10 Х1 + 15 Х2 =450, пересекающимися в той же точке. Отсюда, как и из непосредственнойпроверки двух оставшихся вершин, вытекает, что максимум целевой функции,равный 2200, достигается в вершине (24,14).Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этомиспользуется весь материал и все трудовые ресурсы, а прибыль равна 2200долларам США.Двойственная задача.
Каждой задаче линейного программированиясоответствует так называемая двойственная задача. В ней по сравнению сисходной задачей строки переходят в столбцы, неравенства меняют знак, вместомаксимума ищется минимум (или, наоборот, вместо минимума - максимум).Задача, двойственная к двойственной - эта сама исходная задача. Сравнимисходную задачу (слева) и двойственную к ней (справа):45 Х1 + 80 Х2 → max ,400 W1 + 450 W2 → min ,5 Х1 + 20 Х2 ≤ 400 ,5 W1 + 10 W2 ≥ 45,10 Х1 + 15 Х2 ≤ 450 ,20 W1 + 15 W2 ≥ 80,Х1 ≥ 0 ,W1 ≥ 0,Х2 ≥ 0 .W2 ≥ 0.Почему двойственная задача столь важна? Можно доказать, чтооптимальные значения целевых функций в исходной и двойственной задачахсовпадают (т.е.
максимум в исходной задаче совпадает с минимумом вдвойственной). При этом оптимальные значения W1 и W2 показывают стоимостьматериала и труда соответственно, если их оценивать по вкладу в целевуюфункцию. Чтобы не путать с рыночными ценами этих факторов производства, W1и W2 называют "объективно обусловленными оценками" сырья и рабочей силы.Линейное программирование как научно-практическая дисциплина.Из всех задач оптимизации задачи линейного программирования выделяются тем,что в них ограничения - системы линейных неравенств или равенств.
Ограничениязадают выпуклые линейные многогранники в конечном линейном пространстве.Целевые функции также линейны.Впервые такие задачи решались советским математиком Л.В.Канторовичем (1912-1986) в 1930-х годах как задачи производственногоменеджментасцельюоптимизацииорганизациипроизводстваипроизводственных процессов, например, процессов загрузки станков и раскройкилистов материалов. После второй мировой войны аналогичными задачамизанялись в США. В 1975 г.
Т. Купманс (1910-1985, родился в Нидерландах,работал в основном в США) и академик АН СССР Л.В. Канторович былинаграждены Нобелевскими премиями по экономике.Рассмотрим несколько типовых задач линейного программирования (см.также [1,2]).Задача о диете (упрощенный вариант). Предположим дляопределенности, что необходимо составить самый дешевый рацион питанияцыплят, содержащий необходимое количество определенных питательныхвеществ (для простоты, тиамина Т и ниацина Н).Вещество ТВещество НКалорииСтоимость1 унции, в центахТаблица 1.Исходные данные в задаче об оптимизации смеси.СодержаниеСодержаниеПотребностьв 1 унции Кв 1 унции С0,10 мг0,25 мг1,00 мг1,00 мг0,25 мг5,00 мг110,00120,00400,003,84,2Пищевая ценность рациона (в калориях) должна быть не менее заданной.Пусть для простоты смесь для цыплят изготавливается из двух продуктов - К и С.Известно содержание тиамина и ниацина в этих продуктах, а.
также питательнаяценность К и С (в калориях). Сколько К и С надо взять для одной порциикуриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т икалорий (или больше), а стоимость порции была минимальна? Исходные данныедля расчетов приведены в табл.1.Задача линейного программирования имеет вид:3,8 К + 4,2 С → min ,0,10 К + 0,25 С ≥ 1,00 ,1,00 К + 0,25 С ≥ 5,00 ,110,00 К + 120,00 С ≥ 400,00 ,К≥0,С≥0.Ее графическое решение представлено на рис.4. Ради облегчения восприятиячетыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая 1,00 К +0,25 С = 5,00 (ограничение по веществу Н).
Она проходит, как и показано нарисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратитевнимание, что допустимые значения параметров (К, С) лежат выше прямой (1) илина ней, в отличие от ранее рассмотренных случаев в предыдущейпроизводственной задаче линейного программирования.С204(1)АРис.4. Графическое5 решение задачи об оптимизации смеси.0КПрямая(2) - это прямая 110,0010К + 120,00 С = 400,00 (ограничение покалориям). Обратим внимание, что в области неотрицательных С она(4)расположенавсюду ниже прямой (1).
Действительно, это верно при К = 0, прямая (1) проходитчерез точку (0,20), а прямая (2) - через расположенную ниже точку (0, 400/120).(3)(2)Точка пересечения двух прямых находится при решении системы уравнений1,00 К + 0,25 С = 5,00 ,110,00 К + 120,00 С = 400,00 .Из первого уравнения К = 5 - 0,25 С.
Подставим во второе: 110 (5- 0,25 С) + 120 С= 400, откуда 550 - 27,5 С + 120 С = 400. Следовательно, 150 = - 92,5 С, т.е.решение достигается при отрицательном С. Это и означает, что при всехположительных С прямая (2) лежит ниже прямой (1). Значит, если выполненоограничения по Н, то обязательно выполнено и ограничение по калориям. Мыстолкнулись с новым явлением - некоторые ограничения с математической точкизрения могут оказаться лишними. С точки зрения менеджера они необходимы,отражают существенные черты постановки задачи, но в данном случае внутренняяструктура задачи оказалась такова, что ограничение по калориям не участвует вформировании допустимой области параметров и нахождении решения.Прямая (4) - это прямая 0,1 К + 0,25 С = 1 (ограничение по веществу Т).Она проходит, как и показано на рисунке, через точки (10,0) на оси абсцисс и (0,4)на оси ординат. Обратите внимание, что допустимые значения параметров (К, С)лежат выше прямой (4) или на ней, как и для прямой (1).Следовательно, область допустимых значений параметров (К, С) являетсянеограниченной сверху.
Из всей плоскости она выделяется осями координат(лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых, атакже включает граничные отрезки). Область допустимых значений параметров,т.е. точек (К, С), можно назвать "неограниченным многоугольником". Минимумцелевой функции 3,8 К + 4,2 С может достигаться только в вершинах этого"многоугольника". Вершин всего три.
Это пересечения с осями абсцисс (10,0) иординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то,которое удовлетворяет обоим ограничениям). Третья вершина - это точка Апересечения прямых (1) и (4), координаты которой находятся при решениисистемы уравнений0,10 К + 0,25 С = 1,00 ,1,00 К + 0,25 С = 5,00 .Из второго уравнения К = 5 - 0,25 С, из первого 0,10 (5 - 0,25 С) + 0,25 С =0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1, откуда С = 0,5/0,225 = 20/9 и К = 5 - 5/9 =40/9. Итак, А = (40/9; 20/9).Прямая (3) на рис.4 - это прямая, соответствующая целевой функции 3,8 К+ 4,2 С .
Она проходит между прямыми (1) и (4), задающими ограничения, иминимум достигается в точке А, через которую и проходит прямая (3).Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 =236/9. Задача обоптимизации смеси полностью решена.Двойственная задача, построенная по описанным выше правилам, имеетприведенный ниже вид (мы повторяем здесь и исходную задачу об оптимизациисмеси, чтобы наглядно продемонстрировать технологию построения двойственнойзадачи):3,8 К + 4,2 С → min ,W1 + 5 W2 + 400 W3 → max ,0,10 К + 0,25 С ≥ 1,00 ,0,1 W1 + 1,10 W2 + 110 W3 ≤ 3,8 ,1,00 К + 0,25 С ≥ 5,00 ,0,25W1 + 0,25 W2 + 120 W3 ≤ 4,2 ,110,00 К + 120,00 С ≥ 400,00 ,W1 ≥ 0 ,К≥0,W2 ≥ 0 ,С≥0.W3 ≥ 0 .Минимальное значение в прямой задаче, как и должно быть, равномаксимальному значению в двойственной задаче, т.е. оба числа равны 236/9.Интерпретация двойственных переменных: W1 - "стоимость" единицы вещества Т,а W2 - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевуюфункцию.
При этом W3 = 0, поскольку ограничение на число калорий никак неучаствует в формировании оптимального решения. Итак, W1 , W2 , W3 - это т.н.объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т иН, калорий).Планирование номенклатуры и объемов выпуска.
Вернемся корганизации производства. Предприятие может выпускать автоматические кухни(вид кастрюль), кофеварки и самовары [2]. В табл.2 приведены данные опроизводственных мощностях, имеющихся на предприятии (в штуках изделий).ШтамповкаОтделкаСборкаОбъем выпускаУдельная прибыль (наодно изделие)Кухни200003000020000Х115Таблица 2.Производственные мощности (в шт.)КофеваркиСамовары30000120001000010000120008000Х2Х31214При этом штамповка и отделка проводятся на одном и том же оборудовании. Онопозволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок,либо и то, и другое, не в меньшем количестве. А вот сборка проводится наотдельных участках.Задача линейного программирования имеет вид:Х1 ≥ 0 , Х2 ≥ 0 , Х3 ≥ 0 ,(0)Х1 / 200 + Х2 / 300 + Х3 / 120 ≤ 100 ,(1)Х1 / 300 + Х2 / 100 + Х3 / 100 ≤ 100 ,(2)Х1 / 200 ≤ 100 ,(3)Х2 / 120 ≤ 100 ,(4)Х3 / 80 ≤ 100 ,(5)F = 15 Х1 + 12 Х2 + 14 Х3 → max .Здесь:(0) - обычное в экономике условие неотрицательности переменных,(1) - ограничение по возможностям штамповки (выраженное для облегчениявосприятия в процентах),(2) - ограничение по возможностям отделки,(3) - ограничение по сборке для кухонь,(4) - то же для кофемолок,(5) - то же для самоваров (как уже говорилось, все три вида изделий собираютсяна отдельных линиях).Наконец, целевая функция F - общая прибыль предприятия.Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4)- из (2).
Поэтому неравенства (3) и (4) можно из формулировки задачи линейногопрограммирования исключить.Отметим сразу любопытный факт. Как будет установлено, в оптимальномплане Х3 = 0, т.е. самовары выпускать невыгодно.Методы решения задач линейного программирования. Методы решениязадач линейного программирования относятся к вычислительной математике, а нек экономике и менеджменту. Однако инженеру, менеджеру и экономисту полезнознать о свойствах интеллектуального инструмента, которым он пользуется.С ростом мощности компьютеров необходимость применения изощренныхматематических методов снижается, поскольку во многих случаях время счетаперестает быть лимитирующим фактором, оно весьма мало (доли секунд).Поэтому разберем лишь три метода.Простой перебор.
Возьмем некоторый многомерный параллелепипед, вкотором лежит многогранник, задаваемый ограничениями. Как его построить?Например, если имеется ограничение типа 2Х1 + 5Х2 ≤ 10, то, очевидно, 0 ≤ Х1 ≤10/2 = 5 и 0 ≤ Х2 ≤ 10/5 = 2. Аналогичным образом от линейных ограниченийобщего вида можно перейти к ограничениям на отдельные переменные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
