Основы математики и ее приложения в экономическом образовании (стр. 38 )

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

Рассмотрим следующую задачу.

Предприятие должно выпустить два вида продукции А и В, для изготовления которых используются три вида сырья. Нормы расхода сырья каждого вида на производство единицы данного вида приведены в табл 25.1. В ней указаны такие запа­сы сырья каждого вида, которые могут быть использованы на производство единицы продукции данного вида. Известно, что цена единицы продукции может изменяться для изделия А от 2 до 12 усл. ед., а для изделия В — от 13 до 3 усл. ед., причем эти изменения определяются выражениями 2 + λ и 13 — λ, где 0 ≤ λ ≤ 10.

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

Решение. Обозначим через х1 количество единиц продук­ции А, через x2 — количество единиц продукции В. Матема­тическая модель задачи имеет вид

при ограничениях:

Область допустимых решений — многоугольник OABCD (рис. 25.2). Полагая λ = 0, L() = 2x1 + 13х2 строим (2, 13). Перемещая линию уровня по направлению , находим, что в точке А(0, 11) задача имеет оптимальное решение. Таким об­разом, при λ = 0 1опт(0, 11), L(1)max = 143.

Если уравнение прямой имеет вид

то угловой коэффициент равен k = - А/В.

Угловой коэффициент линии уровня, перпендикулярной , при произвольном значении λ равен k = (2 + λ) / (13 – λ).

Найдем область оптимальности 1опт : 1опт будет оставать­ся оптимальным для всех λ, при которых соответствующая линия уровня находится внутри угла, образованного прямы­ми x1 = 0 и (25.2). Угловой коэффициент прямой (25.2) k = - 2/2 = -1. По условию λ1 = 0, λ2 = (2 + λ) / (13 - λ) = -1, откуда λ2 = 11/2. Решение 1опт остается оптимальным при λ [0, 11/2].

При λ = 11/2 линия уровня совпадает с прямой (25.2) и оптимальными будут все точки, лежащие на прямой (25.2), в том числе и точка В(1, 10), лежащая на пересечении прямых (25.2) и (25.3).

Оптимальное решение будет сохраняться до тех пор, пока при изменении λ линия уровня не совпадет с прямой (25.3), что будет соответствовать новому оптимальному решению 2опт. Найдем новый диапазон изменения λ: λ1 = 11/2, λ2 = (- 2 + λ) / (13 - λ) = -2, так как k3 = -2. Откуда λ2 = 8.

Получили при λ [11/2, 8] 2опт = (1, 10), L(2)max = 132 – 9λ.

Аналогично определяем, что при λ [8,10], 3опт = (2, 8), L(3)mах = 108 – 6λ.

Таким образом, при λ = [0, 11/2] необходимо производить только 11 изделий В, при этом стоимость продукции будет максимальной и равной (143 – 11λ) усл. ед.; при λ [11/2, 8] необходимо производить одно изделие А и 10 изделий В, при этом стоимость продукции является максимальной и равной (132 – 9λ) усл. ед.; при λ [8, 10] необходимо производить 2 изделия А и 8 изделий В, при этом стоимость продукции будет максимальной и равной (108 – 6λ) усл. ед.

Найдем решение этой же задачи симплексным методом (табл. 25.2-25.4), для чего приведем задачу к каноническому виду:

при ограничениях:

Получим λ1 = - , так как все Δ”j ≤ 0;

Таким образом, λ [0, 11/2], 1опт = (0, 11, 5, 0, 3), L(1)max = 143 – 11λ.

Получим

Таким образом, λ [11/2, 8], 2опт = (1, 10, 2, 0, 0), L(2)mах = 132 – 9λ.

Получим

Таким образом, λ [8, 10], 3опт = (2, 8, 0, 2, 0), L(3)mах = 108 – 6λ.

Получили следующие оптимальные решения в зависимости от диапазона изменения λ:

25.4. Транспортная параметрическая задача

Задача формулируется следующим образом: для всех зна­чений параметра δ ≤ λ ≤ φ, где δ, φ — произвольные дейст­вительные числа, найти такие значения xij (i = ; j =), которые обращают в минимум функцию

при ограничениях:

Пользуясь методом потенциалов, решаем задачу при λ = δ до получения оптимального решения. Признаком оптимально­сти является условие:

ui + vj — [c'ij + λс"ij) ≤ 0 для незанятых клеток

и ui + vj = с' ij + λс''ij для занятых клеток,

где ui, vj — потенциалы строк, столбцов распределительной таблицы.

Условие совместимости транспортной задачи запишется в виде

Значения αij и βij определяются из условия

где u'i, v'i, u"j, v"j определяются из систем уравнений

Значения λ находятся в пределах λ1 ≤ λ ≤ λ2:

Алгоритм решения.

1) Задачу решаем при конкретном значении параметра λ = δ до получения оптимального решения.

2) Определяем αij и βij.

3) Вычисляем значения параметра λ.

4) Если λ < φ, производим перераспределение поставок и получаем новое оптимальное решение. Если λ = φ, то процесс решения окончен.

25.5. Нахождение оптимальных путей транспортировки грузов при нестабильной загрузке дорог

Имеются три поставщика однородного товара с объемами поставок: а1 = 100 т, а2 = 200 т, a3 = 100 т и четыре потреби­теля с объемами потребления b1 = - 80 т, b2 = 120 т, b3 = 150 т, b4 = 50 т. Стоимость транспортных расходов изменяется в определенном диапазоне в зависимости от загрузки дороги и задана матрицей

Определить оптимальное решение перевозок, обеспечиваю­щее минимальные транспортные затраты.

Решение. В матрицу расходов введем параметр λ, где 0 ≤ λ ≤ 3. Получим

Полагая λ = 0, решаем задачу методом потенциалов, опре­делим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь вид табл. 25.5.

В таблице ui и vj — потенциалы строк и столбцов. Для занятых клеток они определяются из условия

Полагая u1 = 0, v1 + и1 = 5 + 2λ, получаем v1= 5 + 2λ,

v2 + и1 = 4 — λ, откуда v2 = 4 — λ;

v1 + u2 = 4 или 5 + 2λ + u2 = 4, откуда и2 =λ;

v3 + u2 = 4 + 2λ или -1 – 2λ + v3 = 4 + 2λ, v3 = 5 + 4λ.

Аналогично находим, что u3 = -1 + λ, v4 = 2 + 2λ.

Оценки свободных клеток находим по формуле

Имеем

Аналогично находим, что Δ24 = -6 + λ, Δ31 = -1 + 3λ, Δ33 = -2 + 5λ.

Решение, полученное при λ = 0, является оптимальным для всех значений параметра λ, удовлетворяющих условию

Имеем

Так как по условию задачи λ ≥ 0, то оптимальное решение сохраняется при 0 ≤ λ ≤ 1/3. При этом минимальная стои­мость транспортных расходов составляет

Таким образом, при λ [0; 1/3] L(X1)min = 1430 + 440λ и

Чтобы получить оптимальное решение при λ ≥ 1/3, пере­распределим поставки товаров в клетку (3, 1), где λ2 = 1/3. Вновь полученное распределение представлено в табл. 25.6.

Находим оценки свободных клеток:

Определим пределы изменения λ:

Полученное в таблице оптимальное решение сохраняется при 1/3 ≤ λ ≤ 1/2. При этом L(X2)min = 1460 + 350λ. Итак,

Перераспределим поставки грузов в клетку (3, 3), где λ2 = 1/2. Получим новое распределение (табл. 25.7). Находим оценки свободных клеток:

Определим пределы изменения λ:

Оптимальное решение сохраняется при 1/2 ≤ λ ≤ 1. При этом L(Х3)min = 1490 + 290λ. Итак,

Перераспределим поставки товаров в клетку (1, 4), где λ2 = 1 (табл. 25.8).

Оценки свободных клеток:

Пределы изменения λ:

Полученное в предыдущей таблице оптимальное решение сохраняется при λ ≤ 7/5. При этом L(Х4)min = 1540 + 240λ. Итак,

Перераспределим поставки грузов в клетку (2, 4), где λ2 = 7/5 (табл. 25.9).