Пример решения задачи. Тогда математическая модель задачи примет вид: найти х1, х2, х3, х4 (объёмы производства каждого вида продукции)

Рассмотрим конкретную задачу. Пусть в производстве 4-х видов продукции участвуют 4 вида ресурсов. Известны нормы расхода ресурсов на производство единицы продукции (матрица А), цены её реализации (матрица С) и запасы ресурсов (матрица В). Определить план производства продукции, максимизирующий выручку от реализации производственной продукции.

Тогда математическая модель задачи примет вид: найти х₁, х₂, х₃, х₄ (объёмы производства каждого вида продукции), удовлетворяющие ограничениям:

4х₁ + 2x₂ + 5x₃ + 2x₄ 550,

3x₁ + 3x₃ + x₄ 400,

5x₂ + 2x₃ + 6x₄ 650,

4x₁ + x₂ + 3x₃ + 2x₄ 520,

(),

при которых функция z=4x₁+5x₂+7x₃+9x₄ достигает максимума.

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

4х₁ + 2x₂ + 5x₃ + 2x₄ +s₁ =550,

3x₁ + 3x₃ + x₄ +s₂ =400,

5x₂ + 2x₃ + 6x₄ +s₃ =650,

4x₁ + x₂ + 3x₃ + 2x₄ +s₄ =520,

.

Значения балансовых переменных показывают объёмы неизрасходованных ресурсов в соответствующем плане. Отчёт о решении этой задачи с помощью ППП QM for Windows по модулю Linear Proqramminq имеет следующий вид.

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

Таблица оптимального решения задачи

Рис. 2.1. Окно результатов решения

Итак, для получения максимального дохода от реализации производственной продукции её необходимо выпустить в объёмах: х₁^*=67,083; х₂^*=0; х₃^*=15; х₄^*=103,333. При этом z_max=1303,333.

Двойственная задача. Найти значения переменных у₁, у₂ у₃, у₄, удовлетворяющих ограничениям:

4y₁ + 3y₂ +4y₄ 4,

2y₁ +5y₃ + y₄ 5,

5y₁ + 3y₂ +2y₃ + 3y₄ 7,

2y₁ + y₂ + 6y₃ + 2y₄ 9,

, для которых целевая функция будет минимальной.

w=550y₁+400y₂+650y₃+520y₄.

Решения этой задачи выпишем из последнего столбца таблицы y₁^*=0,833, y₂^*=0, y₃^*=1,167, y₄^*=0,167.

Проиллюстрируем свойства двойственных оценок на основе этой задачи.

1. Каждая из оценок указывает, на сколько изменится максимальное значение целевой функции (максимальная выручка), если изменить на единицу запасы соответствующих ресурсов. Наибольшее изменение выручки произойдёт, если изменить объём 3-го ресурса ( = 1,167), а изменение второго ресурса (в границах устойчивости) не приведёт к изменению целевой функции (у₂^*= 0).

2. Оценки у₁^*, у₃^*, у₄^* положительны. Это означает, что при реализации оптимального плана соответствующие ресурсы расходуются полностью. Проверим это. Подставим в 1-е сопряжённые условия исходной задачи. .

Аналогично для третьего и четвёртого ресурсов (проверить самостоятельно). Следовательно, 1,3,4-й ресурсы дефицитны. у₂^*= 0. Это означает, что в оптимальном решении второй ресурс расходуется не полностью. Проверим это. Подставим во второе ограничение исходной задачи:

Остаток второго ресурса составляет 400-349,582 50,4. Это и есть значение балансовой переменной в оптимальном решении исходной задачи.

3. Рентабельными являются 1, 3 и 4-я продукции (х₁^*, х₂^*, х₃^* в оптимальном плане положительны), а нерентабельной 2-я – х₂^*. Проверим это, подставив у_i^* в сопряжённые условия двойственной задачи. Для первой продукции: . Получили строгое равенство.

Аналогично для 3 и 4-й продукции (проверить самостоятельно). Покажем нерентабельность второй продукции, подставив во второе ограничение двойственной задачи. Получим:

.

Итак, оценка ресурсов, необходимых для производства единицы 2-й продукции, больше цены единицы этой продукции на 7,668 – 5 = 2,668.

Варианты заданий к задаче № 2

Задание: составить модель задачи и на примере её решения проиллюстрировать свойства двойственных оценок.

Рассмотреть задачу по определению оптимального плана выпуска продукции, максимизирующего выручку при известных нормах расхода ресурсов, объёмах ресурсов и ценах реализации продукции.

Ниже представлены таблицы, включающие условия и результаты решения задач по вариантам (по аналогии с рис. 2.1), в которые включены исходные данные. В строке Maximize даны цены реализации единицы продукции, в строках Constraint 1,2,3,4 записаны нормы расхода ресурсов на производство единицы каждой продукции, в столбце RHS записаны запасы ресурсов (см. таблицу решения примера). Задания выполнять по аналогии рассмотренного примера.

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10