Материал: УП - Методы оптимальных решений

1.4. Замена неравенств уравнениями

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

Эти преобразования основываются на следующей теореме: каждому решению неравенства

а₁х₁ + а₂х₂ + … + а_nх_n ≤ (≥) В (1)

соответствует единственное решение уравнения

а₁х₁ + а₂х₂ + … + а_nх_n (±) х_n+1 = В, при условии х_n+1 ≥ 0. (2)

Неотрицательная переменная х_n+1 называется дополнительной переменной.

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

х_n+1  0,

в результате получаем уравнение, содержащее уже (n + 1) неизвестных

a₁х₁ + a₂x₂ + ... + а_nx_n (±) x_n+1 = В. (3)

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

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

2 х₁ +5х₂ + х₃ = 20,

8х₁ +5x₂ +х₄ = 40, Z = 50х₁ + 40x₂ + 0х₃ + 0х₄ + 0х₅,

5x₁ +6x₂ +x₅= 30,

х₁  0, х₂  0, х₃  0, х₄  0, х₅  0.

Пример 2. Задача составления рациона

3 х₁ + х₂ – х₃ = 9,

х₁ + 2x₂ – х₄ = 8, Z = 4х₁ + 6x₂ + 0х₃ + 0х₄ + 0х₅,

x₁ + 6x₂ – x₅ = 12,

х_j  0, (j = ).

Таким образом, систему ограничений любой задачи линейного про­граммирования можно привести к системе m линейных уравнений с n не­известными, а значения переменных х_j, при которых линейная целевая функция достигает min или mах значения, надо искать среди множества решений системы.

1.5. Основные виды записи задач линейного программирования

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

найти max (min)

_{при ограничениях вi (i = ),}

_{xj  0 (j =} ),

где , а_ij, в_i – заданные числа, Z – целевая функция, ={х₁ ... х_n} – план. Ограничения _{могут быть записаны и в виде: вi, вi, где (i =} ).

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

найти max

при ограничениях _{вi (i = ),}

_{xj  0}

_{Или задачу вида:}

найти min

_{при ограничениях вi (i = ),}

_{xj  0}

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

найти max(min)

_{при ограничениях вi, (i = ),}

_{xj  0 (j =} ).

От симметричной формы записи всегда можно перейти к канониче­ской форме записи согласно рассмотренной выше теореме.

Задание для самостоятельной работы

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

1. Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калий­ных удобрений. Известно, что для некоторого газона требуется, по меньшей мере, 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 у. е., а улучшенный – 4 у. е. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

2. Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем производства первой линии – 60 изделий, второй линии – 75 изделий. На радиоприемник первой модели расходуется 10 однотипных элементов электронных схем, на радиоприемник второй модели – 8 таких же элементов. Максимальный суточный запас используемых элементов равен 800 единицам. Прибыль от реализации одного радиоприемника первой и второй модели равна 30 и 20 у. е., соответственно. Определить оптимальный суточный объем производства первой и второй моделей.

3. Процесс изготовления двух видов промышленных изделий состоит в последовательной обработке каждого из них на трех станках. Время использования каждого из этих станков для производства данных изделий ограничено 10-ю часами в сутки. Время обработки и прибыль от продажи одного изделия каждого вида приведены в табл. 4. Найти оптимальный объем производства изделий каждого вида.

Таблица 4

4. Фирма производит два вида продукции – А и В. объем сбыта продукции А составляет не менее 60 % общего объема реализации продукции обоих видов. Для изготовления продукции А и В используется одно и тоже сырье, суточный запас которого ограничен величиной 100 кг. Расход сырья на единицу продукции А составляет 2 кг., а на единицу продукции В – 4 кг. Цены продукции А и В равны 20 и 40 у. е., соответственно. Определить оптимальное распределение сырья для изготовления продукции А и В.

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

Таблица 5

6. В суточный рацион включают два продукта питания П₁ и П₂, причем продукта П₁ должно войти в двойной рацион не более 200 ед. Стоимость 1 ед. продукта П₁ составляет 2 р., продукта П₂ – 4р. Содержание питательных веществ в 1 ед. продукта, минимальные нормы потребления указаны в табл. 6.

Определить оптимальный рацион питания, стоимость которого будет наименьшей.

Таблица 6

Провести анализ задач с использованием графического метода.

7. Фирма выпускает изделия двух типов: А и В. При этом используется сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции и запасы сырья заданы в табл. 7.

Таблица 7

Выпуск одно изделия типа А приносит доход 300 р., одного изделия типа В – 200 р.

Составить план производства, обеспечивающий фирме наибольший доход.

8. Обработка деталей А и В может производиться на трех станках, причем каждая деталь должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А – 100р., детали В – 160 р. Исходные данные приведены в табл. 8.

Таблица 8

Определить производственную программу, максимизирую-щую прибыль при условии: спрос на деталь А – не менее 300 шт., на деталь В – не более 200 шт.

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

Таблица 9

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

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

Таблица 10