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

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

В общем случае задачу оптимального параметрического синтеза можно представить в виде

, (3.7)

где q – критерий задачи (целевая функция); – n-мерный вектор контролируемых входных параметров; D  Eⁿ – область допустимых решений задачи (ОДР). (Значок вектора в дальнейшем будем употреблять лишь в тех случаях, когда это необходимо чтобы избежать недоразумений.) Часто ОДР задается в виде системы неравенств

D = {xEⁿ | j f_j(x)  0}.

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

. Задачей безусловной оптимизации называется задача (3.7), в которой на значения контролируемых входных переменных х_j не наложено ограничений: D = Eⁿ; при D  Eⁿ (строгое включение) имеем задачу условной оптимизации.

В задаче линейного программирования (ЛП) функция критерия q(x) и ограничений f_i(x) линейны; если хотя бы одна из этих функций нелинейна, то имеем задачу нелинейного программирования (НЛП).

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

Пример 3.3. Предприятие выпускает стулья двух типов. Один стул 1-го типа приносит $8 прибыли, в 2-го – $12. Под этот заказ выделены материальные и людские ресурсы. Количество единиц ресурсов, необходимое для выпуска каждого вида стульев приведено в табл. 3.2.

Как спланировать производство для получения максимальной прибыли?

Таблица 3.2
	Расход досок (м2)	Расход ткани (м2)	Расход времени (чел/час)
Стул 1 типа	2	0,5	2
Стул 2 типа	4	0,25	2,5
Ресурс	490	65	319

Решение. Составим модель описания.

Шаг 1. Определим параметры, оптимальные значения которых требуется найти в задаче. В данном случае надо найти оптимальное количество стульев каждого типа. Обозначим x₁ – выпуск стульев первого типа и x₂ – выпуск стульев второго типа.

Шаг 2. Запишем формулы для вычисления целевой функции и функций ограничений через значения параметров х_j.

Критерием эффективности является размер полученной прибыли. Используем следующий ход рассуждений, типичный для синтеза моделей ЛП. За один стул 1-го типа получим $8 прибыли. Следовательно, за х₁ шт. получим 8х₁. Аналогично, за х₂ стульев 2-го типа получим прибыль в размере 12х₂. Общая прибыль от выпуска продукции составит

q = 8x₁+12x₂  max.

При составлении ограничений используются те же рассуждения. Затраты досок составят 2х₁ + 4х₂ м². Так как нельзя тратить сырья больше, чем есть в наличии, то получаем неравенство: 2х₁ + 4х₂  490. Аналогично получаем ограничение на расход ткани: 0.5х₁ + 0.25х₂  65 и времени 2х₁ + 2.5х₂  319.

Кроме того, по физическому смыслу параметров х_j, должны выполняться неравенства х₁  0; х₂  0, т.к. нельзя выпускать отрицательное количество стульев.

Итак, получаем задачу ЛП: найти максимум q = 8х₁ + 12х₂ при ограничениях

.

Пример 3.4. Завод выпускает детали А и Б. Цех №1 может изготовить за смену 600 деталей А или 1200 деталей Б. Эти детали затем поступают в цех №2, где за 1 час могут обработать 150 деталей А или 100 деталей Б. Сколько деталей А и Б может выпускать завод за 8-ми часовую смену, чтобы их общее количество было максимально.

Решение. Обозначим х1 и х2 – выпуск деталей А и Б за смену. Если за смену изготовить 600 деталей А, то на одну деталь тратиться 1/600 часть смены; на х1 деталь – надо х1/600 частей смены. Аналогично на х2 деталей Б надо х2/1200 частей смены. Получаем:

Аналогично, в цехе №2 на обработку деталей А надо х1/150 часа, на детали Б – надо х2/100 часа.

Целевая функция: q = x1 + x2 max.

Пример 3.5. Имеется m = 2 пункта производства А1, А2, и n = 3 пункта потребления В1, В2, В3 некоторого продукта. Перевозка из пунктов производства в пункты потребления 1 ед. продукции обходится в некоторую сумму, указанную в тарифной матрице.

Тарифная матрица
	В1	В2	В3	Количество производимого продукта
А1	10	5	6	50
А2	7	8	12	40
Количество потребляемого продукта	30	30	25

Известно количество производимого продукта в каждом пункте производства и количество потребляемого в пункте потребления.

Составить план перевозок, при котором затраты минимальны.

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

1. Обозначаем Х1 – количество продукта, перевозимого из А1 в В1;

Х2 – из А1в В2;

Х3 – из А1 в В3;

Х4 – из А2 в В1;

Х5 – из А2 в В2;

Х6 – из А2 в В3.

Для запоминания закономерности приведем схему нумерации Х_j:

	В1	В2	В3
A1	X1	X2	X3
A2	X4	X5	X6

2. Общие затраты на перевозку будут равны

q = 10x1 + 5x2 + 6x3 + 7x4 + 8x5 +12x6 → min

3.1 Ограничения на вывоз: из каждого пункта производства нельзя вывезти больше, чем там производят. Из А1 надо вывезти в В1 – х1 ед., в В2 – х2 ед., в В3 – х3 ед. Следовательно, х1+ х2 +х3 ≤ 50. Аналогично для А2: х4+ х5 +х6 ≤ 40.

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

В1: х1+х4 ≥ 30

В2: х2+х5 ≥ 30

В3: х3+х6 ≥ 25

Запишем общую систему ограничений, оставляя пустые места для нулевых элементов:

х1 + х2 + х3 ≤ 50

х4 + х5 + х6 ≤ 40

х1+ х4 ≥ 30

х2 + х5 ≥ 30

х3 + х6 ≥ 25

q = 10x1 + 5x2 + 6x3 + 7x4 + 8x5 +12x6 → min

Замечание. Типичная ошибка: при составлении модели коэффициенты целевой функции матрицы (тариф на перевозку 10, 5 и т. д.) заносят в ограничения. Следует помнить, в ограничениях на ввоз вывоз коэффициенты могут быть равны только 1 или 0, а тарифные коэффициенты встречаются только в целевой функции.