Исследование изменений второго ограничения модели (по цеху «шасси») можно провести на одном графике

Задача 2. Задача об оптимальной оптовой закупке товаров

Торговой фирме необходимо сделать ассортиментный выбор из шести видов товаров для их оптовой закупки. На затраты по транспортировке закупленных товаров фирма решает выделить 7,95 млн. рублей, на рекламу – 5,54 млн. рублей, на хранение и сбыт – 18,17 млн. рублей.

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

Статья	товар 1	товар 2	товар 3	товар 4	товар 5	товар 6	Лимит	Набор 1	Набор 2
Транспорт							7.95	товар 6	товар 6
Реклама							5,54	товар 5	товар 5
Сбыт							18,17	товар 2	товар 1
Надбавка	11,8	15,4	25,7	11,4	25,7	26,6

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

1. Составить экономико-математическую модель расчета оптимальной оптовой закупки товаров в рамках запланированных затрат.

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

3. Дать экономическую интерпретацию оптимальным решениям прямой и двойственной задач.

Решение:

1. Пусть х_j – сумма средств (млн. руб.), выделяемых на оптовую закупку товара под номером j,или сумма оптовой закупки товара j-го вида (млн. руб.).

Экономико-математическая модель задачи.

Найти вектор X = (х₁; х₂; х₃; х₄; х₅; х₆), для которого выполняются следующие ограничения:

0,04х₁ + 0,03х₂ + 0,05х₃ + 0,03х₄ + 0,03х₅ + 0,05х₆ 7,95,

0,02х₂ + 0,03х₃ + 0,04х₅ + 0,02х₆ 5,54,

0,04х₁ + 0,05х₂ + 0,09х₃ + 0,05х₄ + 0,1х₅ + 0,11х₆ 18,17,

х_j 0, j = ,

Z = 0,118х₁ + 0,154х₂ + 0,257х₃ + 0,114х₄ + 0,257х₅ + 0,266х₆ max.

В целевой функции максимизируется сумма общей торговой надбавки, получаемой при реализации товаров в розницу.

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

Преобразуем ограничения и целевую функцию для удобства расчетов:

4х₁ + 3х₂ + 5х₃ + 3х₄ + 3х₅ + 5х₆ 795,

2х₂ + 3х₃ + 4х₅ + 2х₆ 554,

4х₁ + 5х₂ + 9х₃ + 5х₄ + 10х₅ + 11х₆ 1817,

х_j 0, j = ,

Z = 11,8х₁ + 15,4х₂ + 25,7х₃ + 11,4х₄ + 25,7х₅ + 26,6х₆ max.

2. Для решения задачи об оптимальной оптовой закупке товаров воспользуемся второй теоремой двойственности.

Составим двойственную задачу:

4u₁ + 4u₃ 11,8, (2.1)

3u₁ + 2u₂ + 5u₃ 15,4, (2.2)

5u₁ + 3u₂ + 9u₃ 25,7, (2.3)

3u₁ + 5u₃ 11,4, (2.4)

3u₁ + 4u₂ + 10u₃ 25,7, (2.5)

5u₁ + 2u₂ + 11u₃ 26,6, (2.6)

u₁ 0, u₂ 0, u₃ 0, (2.7)

W = 795u₁ + 554u₂ + 1817u₃ min.

Исследуем набор 1, состоящий из товара 2, товара 5 и товара 6. Это значит, что фирма планирует закупать второй, пятый и шестой товары, т.е. х₂ ¹ 0, х₅ ¹ 0, х₆ ¹ 0.

Первый, третий и четвёртый товары закупать не планируется, поэтому х₁ = 0,
х₃ = 0, х₄ = 0. Тогда допустимый вектор X, соответствующий набору 1, имеет вид:

X= (0; x₂; 0; 0; х₅; х₆).

Воспользуемся второй теоремой двойственности (теоремой о дополняющей нежесткости).

Допустимые решения X = (х₁; х₂; х₃; х₄; х₅; х₆) и U = (u₁; u₂; u₃ ) прямой и двойственной задач оптимальны тогда и только тогда, когда выполняются следующие два условия дополняющей нежесткости:

первое условие дополняющей нежесткости

х₁ (4u₁ + 4u₃ – 11,8) = 0,

х₂ (3u₁ + 2u₂ + 5u₃ – 15,4) = 0,

х₃ (5u₁ + 3u₂ + 9u₃ – 25,7) = 0,

х₄ (3u₁ + 5u₃ – 11,4) = 0,

х₅ (3u₁ + 4u₂ +10u₃ – 25,7) = 0,

х₆ (5u₁ + 2u₂ +11u₃ – 26,6) = 0,

второе условие дополняющей нежесткости

u₁(795 – 4х₁ – 3х₂ – 5х₃ – 3х₄ – 3х₅ – 5х₆ ) = 0,

u₂(554 – 2х₂ – 3х₃ – 4х₅ – 2х₆ ) = 0,

u₃(1817 – 4х₁ – 5х₂ – 9х₃ – 5х₄ – 10х₅ – 11х₆ ) = 0.

Обратимся к первому условию дополняющей нежесткости.

Первое равенство:

х₁(4u₁ + 4u₃ – 11,8) = 0.

Для набора 1 переменная х₁ = 0, поэтому выражение в скобках может принимать значения как равное нулю, так и больше нуля, т.е. 4u₁ + 4u₃ 11,8.

Второе равенство:

х₂(3u₁ + 2u₂ + 5u₃ – 15,4) = 0.

Так как для набора 1 переменная х₂ > 0, то выражение, стоящее в скобках, должно быть равно нулю и, следовательно, получаем следующее уравнение:

3u₁ + 2u₂ + 5u₃ = 15,4.

Рассуждая аналогично, имеем систему равенств:

х₂ > 0 3u₁ + 2u₂ + 5u₃ = 15,4,

х₅ > 0 3u₁ + 4u₂ + 10u₃ = 25,7,

х₆ > 0 5u₁ + 2u₂ + 11u₃ = 26,6.

Решим полученную систему из 3-х уравнений с 3-мя неизвестными.

Её решением будет вектор: U = (1,7; 1,9; 1,3).

Все координаты найденного вектора Uявляются неотрицательными, т.е. удовлетворяют условию (2.7) двойственной задачи: 1,7 > 0, 1,9 > 0, 1,3 > 0.

Для найденных значений переменных u₁, u₂, u₃ неравенства (2.2), (2.5) и (2.6) выполняются как равенства.

Проверим выполнение неравенств (2.1), (2.3), (2.4):

4 1,7 + 4 1,3 = 12 > 11,8, 5 1,7 + 3 1,9 + 9 1,3 = 25,9 > 25,7,

3 1,7 + + 5 1,3 = 11,6 > 11,4.

Убеждаемся, что найденные значения удовлетворяют всем ограничениям двойственной задачи, значит U = (1,7; 1,9; 1,3) – решение, допустимое для двойственной задачи. Определим значение целевой функции двойственной задачи:

W = 795 1,7 + 554 1,9 + 1817 1,3 = 4766,2.

Обратимся ко второму условию дополняющей нежесткости для набора 1.

Первое равенство:

u₁(795 – 4х₁ – 3х₂ – 5х₃ – 3х₄ – 3х₅ – 5х₆ ) = 0.

Поскольку u₁ = 1,7 ¹ 0, то выражение, стоящее в скобках, должно быть равно нулю, значит, 4х₁ + 3х₂ + 5х₃ + 3х₄ + 3х₅ + 5х₆ = 795.

Рассуждая аналогично, получим следующую систему равенств:

u₁ = 1,7 ¹ 0 4х₁ + 3х₂ + 5х₃ + 3х₄ + 3х₅ + 5х₆ = 795,

u₂ = 1,9 ¹ 0 2х₂ + 3х₃ + 4х₅ + 2х₆ = 554,

u₃ = 1,3 ¹ 0 4х₁ + 5х₂ + 9х₃ + 5х₄ + 10х₅ + 11х₆ = 1817.

Подставим в эту систему уравнений известные значения х₁ = 0, х₃ = 0, х₄ = 0:

3х₂ + 3х₅ + 5х₆ = 795,

2х₂ + 4х₅ + 2х₆ = 554,

5х₂ + 5х₅ + 11х₆ = 1817.

Решим систему полученных уравнений. Найдены значения: х₂ = 85, х₅ = 60, х₆ = 72, следовательно, вектор X = (0; 85; 0; 0; 60; 72) является допустимым решением прямой задачи. Определим значение целевой функции прямой задачи:

Z = 15,4 85 + 25,7 60 + 26,6 72 = 4766,2.

Итак, в результате анализа имеем:

1) Вектор X = (0; 85; 0; 0; 60; 72) – допустимое решение прямой задачи.

2) Вектор U = (1,7; 1,9; 1,3) – допустимое решение двойственной задачи.

3) Условия дополняющей нежесткости для векторов X и Uвыполнены.

По теореме об условиях дополняющей нежесткости вектор Xявляется оптимальным решением прямой задачи, а вектор U – оптимальным решением двойственной задачи. В качестве проверки правильности вычислений отметим, что значения целевых функций прямой и двойственной задач совпадают: Z = W = 4766,2.

Отсюда вывод: ассортиментный набор 1 (товар 6, товар 5, товар 2) рекомендуется торговой фирме для оптовых закупок.

Исследуем набор 2, состоящий из товара 1, товара 5 и товара 6. Это значит, что фирма планирует закупать первый, пятый и шестой товары, т.е. х₁ ¹ 0, х₅ ¹ 0, х₆ ¹ 0.

Второй, третий и четвёртый товары закупать не планируется, поэтому х₂ = 0, х₃ = 0,

х₄ = 0. Вектор, соответствующий этому набору, имеет вид: X ^*= (х₁; 0; 0; 0; х₅; х₆).

Действия при анализе набора 2 аналогичны вышеизложенному при проверке

набора 1.

Используем первую группу условий дополняющей нежесткости.

х₁ > 0 4u₁ + 4u₃ = 11,8,

х₅ > 0 3u₁ + 4u₂ + 10u₃ = 25,7,

х₆ > 0 5u₁ + 2u₂ + 11u₃ = 26,6.

Решив систему из 3-х уравнений с 3-мя неизвестными, получаем:

u₁ = 1,58, u₂ = 1,815, u₃ = 1,37.

Проверим, допустимы ли эти значения. Все значения неотрицательны:

1,58 > 0, 1,815 > 0, 1,37 > 0, т.е. удовлетворяют условию (2.7) двойственной задачи. Для найденных значений переменных u₁, u₂, u₃ неравенства (2.1), (2.5) и (2.6) выполняются как равенства.

Проверим выполнение неравенств (2.2), (2.3) и (2.4).

Проверяем второе ограничение:

3u₁ + 2u₂ + 5u₃ 15,4,

3 1,58 + 2 1,815 +5 1,37 = 15,22 < 15,4.

Условие не выполняется, вектор U– недопустимое решение, следовательно, вектор X не может быть оптимальным решением и, соответственно, набор 2 не входит в оптимальный план закупки товаров.

3. Рассчитанное значение целевой функции Z означает, что для получения максимальной прибыли в виде торговой надбавки для розничной продажи в размере 4766,2 млн. руб. торговая фирма должна выбрать набор 1 и купить товара 2 на сумму 85 млн. руб., товара 5 – на 60 млн. руб., товара 6 – на 72 млн. руб.

Рассчитанное значение целевой функции W означает, что для получения минимальных расходов в размере 4766,2 млн. руб. на приобретение ресурсов (в виде расходов на транспорт, рекламу и сбыт) оптимальные стоимостные оценки этих ресурсов (внутренние цены на ресурсы именно для данной фирмы) должны соответствовать оптимальным значениям u₁ = 1,7 млн. руб./млн. руб., u₂ = 1,815 млн. руб./млн. руб., u₃ = 1,3 млн. руб./млн. руб.

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

Для фирмы смысл найденных двойственных оценок заключается в следующем:

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

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

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

Задача 3. Задача о выборе оптимального плана
производства продукции

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

Вид продукта   Вид ресурса	продукт 1	продукт 2	продукт 3	продукт 4
Сырьё (кг)
Труд (чел. -час)
Цена (руб.)

Учитывая собственные запасы и дополнительные поставки ресурсов, фирма предполагает иметь в предстоящем периоде сырье в объеме 585 кг. Трудовые ресурсы фирмы составляют 703 чел.-час.

Требуется:

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

2. Записать двойственную задачу и определить оптимальные двойственные оценки графическим способом.

3. Используя условия дополняющей нежесткости, найти оптимальный план выпуска продукции.

4. Найти диапазон изменения трудовых ресурсов, при котором найденный оптимальный план выпуска продукции сохраняется.

5. Установить, насколько изменится выручка фирмы при сокращении трудовых ресурсов на 99 чел.-час. и росте на 180 чел.-час.

Решение:

1. Пусть х_j – объем продукции j-го вида (j = ), который будет производиться фирмой в предстоящем временном периоде.

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

Экономико-математическая модель задачи имеет вид:

8х₁ + 9х₂ + 13х₃ + 16х₄ 585,

17х₁ + 15х₂ + 9х₃ + 8х₄ 703,

х_j 0, j = ,

Z = 670х₁ + 504х₂ + 530х₃ + 504х₄ max.

2. Пусть u_i – двойственная или стоимостная оценка единицы i-го вида ресурса

(i = ).

Построим двойственную задачу:

8u₁ + 17u₂ 670,

9u₁ + 15u₂ 504,

13u₁ + 9u₂ 530,

16u₁ + 8u₂ 504,

u₁ 0, u₂ 0,

W = 585u₁ + 703u₂ min.

Решим графическим методом двойственную задачу.

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

1) 8u₁ + 17u₂ = 670 (3.1) 3) 13u₁ + 9u₂ = 530 (3.3)

u₁ 0 83,75 u₁ 0 40,76

u₂ 39,4 0 u₂ 58,8 0

2) 9u₁ + 15u₂ = 504 (3.2) 4) 16u₁ + 8u₂ = 504 (3.4)

u₁ 0 56 u₁ 0 31,5

u₂ 33,6 0 u₂ 63 0

u₂

Л С

В

А

7,03 D

u₁

5,85 (3.2)

(3.1)

W = 0 (3.3)

(3.4)

Рисунок 4. Графическое решение двойственной задачи

Область допустимых решений лежит вверху от ломаной линии, образованной прямыми (3.1), (3.3), (3.4) и осями координат, и представляет собой бесконечный многоугольник СВАD (рисунок 4).

Пропорционально уменьшим компоненты вектора-градиента: = (5,85; 7,03).

Построим линию уровня целевой функции вида: 585u₁ + 703u₂ = 0.

Точка минимума А целевой функции находится на пересечении прямых (3.1) и (3.3):

8u₁+17u₂ = 670,

13u₁+9u₂ = 530.

Решив систему, получим оптимальное решение двойственной задачи:

u = 20, u = 30, W = 585 × 20 + 703 × 30 = 32790.

Это решение задает оптимальные двойственные оценки ресурсов для фирмы, т.е. стоимость 1 кг сырья – 20 руб., стоимость 1 чел.-час. трудоресурсов – 30 руб., (u = 20 руб./кг, u = 30 руб./чел.-час).

Общая сумма затрат на использованные в данном производстве ресурсы составит 32790 руб.

3.Воспользуемся условиями дополняющей нежесткости для определения оптимального выпуска продукции X = (х₁; х₂; х₃; х₄).

Первая группа условий:

х₁(8u₁+17u₂ – 670) = 0,

х₂(9u₁+15u₂ – 504) = 0,

х₃(13u₁+9u₂ – 530) = 0,

х₄(16u₁+8u₂ – 504) = 0.

Вторая группа условий:

u₁(585 – 8х₁ – 9х₂ – 13х₃ – 16х₄) = 0,

u₂(703 – 17х₁ – 15х₂ – 9х₃ – 8х₄) = 0.

Проведем анализ первой группы условий:

х₁(8u₁+17u₂ – 670) = 0, подставим рассчитанные ранее значения u₁^* = 20, u₂^*= 30 в выражение, стоящее в скобках, 8 20 + 17 30 – 670 = 0.