Цех может производить стулья и столы

Цех может производить стулья и столы

1. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола – 20 единиц. На изготовление стула требуется 10- человеко-часов, стола – 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула – 45 руб., при производстве стола – 80 руб. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

2. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:

3. В отделе технического контроля некоторой фирмы работают контролеры 1-го и 2-го разрядов. Норма выработки ОТК за смену составляет не менее 1800 изделий. Контролер первого разряда проверяет 25 изделий в час с вероятностью ошибки 2%. Контролер второго разряда проверяет 15 изделий в час с вероятностью ошибки 5%. Заработная плата контролера первого разряда составляет 4 руб./час, контролера второго разряда – 3 руб./час. При каждой ошибке фирма несёт убытки в 2 руб. В распоряжении фирмы имеется 8 контролеров первого разряда и 10 – второго разряда. Требуется определить оптимальный состав ОТК при минимальных затратах.

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

Вид материалов Изделие Запас материалов
Х1 Х2
А
В
Прибыль на одно изделие

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

Номер цеха Изделие Максимальная загрузка
Х1 Х2
А
В
Цена изделия

6. Фирме «Сталь» предстоит решить: какое количество x1 чистой стали и какое количество x2 металлолома следует использовать для приготовления (из соответствующего сплава) литья для одного из своих заказчиков. Пусть производственные затраты в расчете на 1 т чистой стали равняются 3 усл.ед., а затраты в расчете на 1 т металлолома — 5 усл.ед. (последняя цифра больше предыдущей, так как использование металлолома сопряжено с его предварительной очисткой). Заказ предусматривает поставку не менее 5 т литья; при этом заказчик готов купить и большее количество литья, если фирма «Сталь» поставит перед ними такие условия.

Предположим, что запасы чистой стали ограничены и не превышают 4т, а запасы металлолома не превышают 6 т. Отношение веса металлолома к весу чистой стали в процессе получения сплава не должно превышать 7 : 8. Производственно-технологические условия таковы, что на процессы плавки и литья не может быть отведено более 18 ч; при этом на 1 т стали уходит 3 ч, а на 1 т металлолома — 2 ч производственного времени.

Дата публикования: 2015-07-22 ; Прочитано: 359 | Нарушение авторского права страницы

studopedia.org — Студопедия.Орг — 2014-2020 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.002 с) .

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

Среди оптимизационных задач в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая функция F(X) является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера (см. [2]).

Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола — 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол — 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула — 45 долларов США, при производстве стола — 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х1 — число изготовленных стульев, Х2 — число сделанных столов. Задача оптимизации имеет вид:

В первой строке выписана целевая функция — прибыль при выпуске Х1 стульев и Х2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х1 и Х2 . При этом должны быть выполнены ограничения по материалу (вторая строчка) — истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) — затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х1 = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х1 положительно. Но невозможно представить себе отрицательный выпуск — Х1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Читайте также:  Как рутуб вывести на телевизор с телефона

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х1 , а по вертикальной оси ординат — значения Х2 . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х1 , Х2) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х1, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство — материал останется.

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

Таким образом, ограничения по труду также изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х1, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство — часть рабочих будет простаивать.

Мы видим, что очевидного решения нет — для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

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

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х1 , Х2 ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны — это (0,0), (45,0) и (0,20). Четвертая — это пересечение двух прямых — границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений

Из первого уравнения: 5 Х1 = 400 — 20 Х2 , Х1 = 80 — 4 Х2 . Подставляем во второе уравнение: 10 (80 — 4 Х2) + 15 Х2 = 800 — 40Х2 + 15 Х2 = 800 — 25 Х2 = 450, следовательно, 25 Х2 = 350, Х2 = 14, откуда Х1 = 80 — 4 х 14 = 80 -56 = 24. Итак, четвертая вершина четырехугольника — это (24, 14).

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

Читайте также:  Почему виндовс 10 долго выключается

Целевая функция 45 Х1 + 80 Х2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х1 + 80 Х2 = 2200 проходит между прямыми ограничений 5 Х1 + 20 Х2 = 400 и 10 Х1 + 15 Х2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.

Двойственная задача. Каждой задаче линейного программирования соответствует так называемая двойственная задача. В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума — максимум). Задача, двойственная к двойственной — эта сама исходная задача. Сравним исходную задачу (слева) и двойственную к ней (справа):

Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W1 и W2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W1 и W2 называют "объективно обусловленными оценками" сырья и рабочей силы.

Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения — системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.

Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.

Рассмотрим несколько задач линейного программирования.

Задача об оптимизации смеси (упрощенный вариант). На химическом комбинате для оптимизации технологического процесса надо составить самую дешевую смесь, содержащую необходимое количество определенных веществ (обозначим их Т и Н). Энергетическая ценность смеси (в калориях) должна быть не менее заданной. Пусть для простоты смесь составляется из двух компонентов — К и С. Сколько каждого из них взять для включения в смесь? Исходные данные для расчетов приведены в табл.3.

Табл.3. Исходные данные в задаче об оптимизации смеси.

Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола — 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол — 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула — 45 долларов США, при производстве стола — 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х1 — число изготовленных стульев, Х2 — число сделанных столов. Задача оптимизации имеет вид:

В первой строке выписана целевая функция — прибыль при выпуске Х1 стульев и Х2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х1 и Х2 . При этом должны быть выполнены ограничения по материалу (вторая строчка) — истрачено не более 400 футов красного дерева. А также ограничения по труду (третья строчка) — затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны.

Читайте также:  Инструкция к сканеру canon

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х1 , а по вертикальной оси ординат — значения Х2 . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х1 , Х2) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Прямая пересекает ось Х1, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а в противном случае материал останется.

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

Таким образом, ограничения по труду также изображаются в виде треугольника. Прямая пересекает ось Х1, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, в противном случае часть рабочих будет не задействовано.

Мы видим, что очевидного решения нет — для изготовления 80 стульев есть материал, но не хватает рабочих, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

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

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х1 , Х2 ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны — это (0,0), (45,0) и (0,20). Четвертая — это пересечение двух прямых — границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений

Из первого уравнения:

Подставляем во второе уравнение:

10 (80 — 4 Х2) + 15 Х2 = 800 — 40Х2 + 15 Х2 = 800 — 25 Х2 = 450,

Х2 = 14, откуда Х1 = 80 — 4 х 14 = 80 -56 = 24.

Итак, четвертая вершина четырехугольника — это (24, 14).

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

Целевая функция 45 Х1 + 80 Х2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х1 + 80 Х2 = 2200 проходит между прямыми ограничений 5 Х1 + 20 Х2 = 400 и 10 Х1 + 15 Х2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Ответ: Наилучшим вариантом является выпуск 24 стульев и 14 столов, при этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 у.е.

Ссылка на основную публикацию
Форге оф импаерс великие строения
Другое название: Кузница Империй Ниже мы приводим подробный гайд по игре Forge of Empires с советами как вам быстрее отстроить...
Троттлинг процессора что это
Простой компьютерный блог для души) Всем привет. Сегодня мы затронем тему процессоров, а если быть точнее, то такое явление как...
Троянские программы и хакерские утилиты
В данную категорию входят программы, осуществляющие различные несанкционированные пользователем действия: сбор информации и ее передачу злоумышленнику, ее разрушение или злонамеренную...
Форза хорайзен 3 список машин
Серия игр Forza всегда поражала количеством доступных автомобилей. На момент выхода игры доступно уже более 150 автомобилей, а разработчики обещают...
Adblock detector