LP: основная форма (упражнения – решения)

первоначальная форма

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

Руководство

Производитель фрезерного инструмента производит два типа фрез: A и B. Фрезы типа A продаются по 300 штук каждая и изготавливаются из 1 единицы стали, 2 единиц съемного твердого сплава и 1 единицы алмазного синтетического материала. Резцы типа B продаются по 200 штук каждая и состоят из 2 единиц стали, 1 единицы съемного твердого сплава и 1 единицы синтетического алмаза. 

Запасы составляют 5 единиц стали, 5 единиц карбида и 2 единицы алмаза. Изготовитель хочет построить не менее 5 резаков типа А и 5 резаков типа В. Стоимость содержания фабрики составляет 2500. Как производитель должен распределять свою продукцию, чтобы максимизировать свою прибыль, выгодно ли это?

Коррекция

Во-первых, необходимо создать линейную программу:

  • Целевая функция: z = 300A+200B-2500
  • Ограничения:
    • А+2В ≤ 5
    • 2А+В ≤ 5
    • А+В ≤ 2
    • А ≥ 5
    • В ≥ 5

Программа не под каноническая форма, он должен быть отрендерен в таком виде перед его решением.

Давайте установим х1 = А-5 и х2 = В-5. Линейная программа становится следующей:

линейное программирование исправленные упражнения в первичной форме

Линейная программа имеет 2 переменные, поэтому ее можно решить графически. Ограничения дают следующую область решений:

линейное программирование исправленные упражнения в первичной форме

Градиент целевой функции равен (3,2), что дает конечную точку пересечения второго и третьего ограничений. Итак, нам нужно решить систему:

линейное программирование исправленные упражнения в первичной форме

Решением которой является вектор (10, 2). Что дает в исходной задаче вектор (15, 7) и для целевой функции равно 900. Операция положительна и, следовательно, прибыльна для предприятия.

Упражняться

Упражнение 1

Брокеру необходимо для своих клиентов 108 МВтч электроэнергии для города 1 и 96 МВтч электроэнергии для города 2. Однако законы Кирхгофа не позволяют дистрибьютору нацеливать поток энергии на один город. Два дистрибьютора обслуживают эти города: дистрибьютор А может отправить 12 МВтч в город 1 и 8 МВтч в город 2 за купленный лот; Дистрибьютор B может отправить 9 МВтч в город 1 и 12 МВтч в город 2 за купленный лот. Все лоты имеют одинаковую цену. Сколько лотов должен купить брокер, чтобы удовлетворить потребности двух городов в энергии? Решить графическим методом.

Коррекция

Линейная программа выглядит следующим образом: X1 для первой партии и X2 для второй партии.

линейное программирование исправленные упражнения в первичной форме

Что дает для графическое разрешение :

линейное программирование исправленные упражнения в первичной форме

Градиент равен (-1, -1), поскольку он является минимальным (min f(x) = – max -f(x)). в поле определения зеленым цветом точка C является единственным экстремумом, являющимся глобальным оптимумом. Разложение предыдущей системы в виде равенства дает для координат (6, 4) с Z = 10.

Упражнение 2

Решить графическим методом, затем методом симплекс следующие проблемы:

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

линейное программирование исправленные упражнения в первичной форме

  1. Аналогично со следующей линейной программой:

линейное программирование исправленные упражнения в первичной форме

Коррекция

То методология всегда одинакова для части графического разрешения. Вот исправления симплекса с начальным состоянием и конечным состоянием массива для первого примера.

Проблема 0:

линейное программирование исправленные упражнения в первичной форме

И для решения:

линейное программирование исправленные упражнения в первичной форме

Целевая функция имеет значение Z = 1875 с P1 и P2 в основании (поэтому не равно нулю), имеющее соответственно значение (25.15), как указано в столбце b, представленном P0.

Вторая линейная программа имеет решение Z = 8.2 с вектором основных переменных (3.2, 1.8).

Упражнение 3

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

линейное программирование исправленные упражнения в первичной форме

Ежедневные требования к рабочему следующие:

линейное программирование исправленные упражнения в первичной форме

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

Коррекция

Линейная программа выглядит следующим образом:

линейное программирование исправленные упражнения в первичной форме

Разрешение по excel такое:

линейное программирование исправленные упражнения в первичной форме

Результат следующий:

линейное программирование исправленные упражнения в первичной форме

Заметим, что оптимальное решение не единственно. Решение дает целые числа, что практично с учетом задачи (кажется очевидным, что нужны «целые» индивидуумы).

Подтвердите свои навыки

Упражнение 4

Компания производит три типа продуктов: A, B и C. Для каждого продукта требуются сырье и рабочая сила, а также место для хранения. Вот требования к сырью, рабочей силе и хранению для одной единицы каждого из 3 типов продуктов:

  • Продукт А: 4 кг сырья, 2 часа труда, 1 единица объема.
  • Продукт Б: 2 кг сырья, 1/2 часа труда 1 единица объема.
  • Продукт С: 1 кг сырья, 3 часа труда, 1 единица объема.

Каждый продукт зарабатывает 6 евро, если это тип A, 2 евро, если это тип B, и 4 евро, если это тип C. Доступные ресурсы составляют 6000 кг сырья, 4000 часов труда и 2500 единиц складского объема.

Моделирование линейной программы и ее решение вручную с использованием симплекса.

Конкурент, которому не хватает сырья, предлагает выкупить у этой компании 300 кг по цене 1,5 евро за кг. Считаете ли вы, что компания должна принять это предложение? (Будет считаться, что он ее принимает, если это выгодно, решая задачу вручную с помощью симплекса.)

Коррекция

Задача в стандартной форме:

линейное программирование исправленные упражнения в первичной форме

С симплексным решением:

линейное программирование исправленные упражнения в первичной форме

Задача выкупа имеет дополнительно в целевой функции 450. Первая переменная имеет для элемента b = 5700. В этом случае оптимальное решение (1310, 0, 460) с Z = 10150, поэтому предложение выгодно.

Упражнение 5

Компания производит три типа аккумуляторов: сухой тип 1 (ПС1), сухой тип 2 (ПС2) и топливный (ПК). Производственный процесс состоит из трех этапов: сборка, проверка качества, обработка изоляции. Только батареи, прошедшие проверку качества, подвергаются изоляционной обработке. Аккумуляторы, не прошедшие проверку качества, выбрасываются. В течение следующего месяца у компании будет 9 000 часов машинного времени на сборку, 1 200 часов на проверку качества и 8 500 часов на обработку изоляции. В следующей таблице обобщена соответствующая информация о производственном процессе:

линейное программирование исправленные упражнения в первичной форме

Какое оптимальное количество батарей каждого типа будет произведено в следующем месяце, если компания обязательно продаст всю свою продукцию?

Коррекция

Пусть X1, X2, X3 будут тремя переменными, представляющими количество допустимых стеков каждого типа, а X4, X5, X6 — тремя переменными, представляющими количество недопустимых стеков каждого типа.

Линейная программа в канонической форме выглядит следующим образом:

линейное программирование исправленные упражнения в первичной форме

линейное программирование исправленные упражнения в первичной форме

Что дает решение (419417,476, 0, 741176,471) для действительных стеков и целевой функции Z=1278957,05. Поскольку решение не дает целочисленного результата, можно обрезать плавающую часть (будьте осторожны, это уже не будет оптимальным решением!).

Упражнение 6

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

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

линейное программирование исправленные упражнения в первичной форме

Этот график читается следующим образом:

  • S — фиктивный источник, описывающий производство источников энергии, представленных вершинами 1 и 2.
  • T — фиктивный сток, описывающий получение энергии городами, представленными вершинами 3 и 4.
  • Линии ориентированы, т.е. энергия проходит только в одном направлении. Например, связь (1, 3) может циркулировать до 4 единиц энергии между вершиной 1 и вершиной 3.
  • Связи между S и источниками описывают производство энергии источником. Например ссылка (S, 1) говорит о том, что источник 1 может производить до 10 единиц энергии.
  • Связи между поглотителями и T описывают потребление энергии поглотителем. Например ссылка (3, T) говорит о том, что город 3 требует 10 единиц энергии.

Целевая функция этого типа задач:

  • максимизировать количество энергии, которое может перетекать от S к T. Решение обеспечит количество энергии, протекающей по каждой линии. Чтобы вычислить этот поток, добавляется дуга между фиктивным стоком и фиктивным неограниченным источником. Оптимальное решение равно потоку, проходящему через эту дугу.

Эта задача связана с двумя типами ограничений:

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

Таким образом, переменные:

  • для каждой линии переменная описывает количество энергии, проходящей по ней.

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

Коррекция

Линейная задача записывается в Excel следующим образом:

линейное программирование исправленные упражнения в первичной форме

Что дает в результате:

линейное программирование исправленные упражнения в первичной форме

Делиться
ru_RURU