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

Задача. Предприятие должно выпустить два вида продукции А и В, для изготовления которых используются три вида сырья. Нормы расхода сырья каждого вида на производство единицы данного вида приведены в таблице. В ней указаны такие запасы сырья каждого вида, которые могут быть использованы на производство единицы продукции данного вида. Известно, что цена единицы может изменяться для изделия А от 2 до 12 усл. ед., а для изделия В – от 13 до 3 усл. ед., причём эти изменения определяются выражениями и , где .

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

Вид сырья	Нормы расхода сырья на единицу продукции, т	Запасы сырья, т
А	В
I II III

РЕШЕНИЕ. Обозначим через х₁ количество единиц продукции А, через х₂ – количество единиц продукции В. Математическая модель имеет вид

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

Область допустимых решений – многоугольник ОАВСD. Полагая , , строим . Перемещая линию уровня по направлению , находим, что в точке А(0, 11) задача имеет оптимальное решение. Таким образом, при , .

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

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

Угловой коэффициент линии уровня, перпендикулярной , при произвольном значении равен

(1)

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

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

Оптимальное решение будет сохраняться до тех пор, пока при изменении линия уровня не совпадёт с прямой (3), что будет соответствовать новому оптимальному решению . Найдём новый диапазон изменения : , так как k₃= -2. Откуда . Получили при =(1, 10),

Аналогично определяем, что при =(2, 8),

Таким образом, при необходимо производить только 11 изделий В, при этом стоимость продукции будет максимальной и равной усл. ед.; при необходимо производить одно изделие А и 10 изделий В, при этом стоимость продукции является максимальной и равной усл. ед.; при необходимо производить 2 изделия А и 8 изделий В, при этом стоимость продукции будет максимальной и равной усл. ед.

Найдём решение этой задачи симплексным методом, для чего приведём задачу к каноническому виду:

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

ci	БП			0	0	0	bi
x1	x2	x3	x4	x5
	x3 x4 x5
13-	x3 x2 x1				-1/2 1/2 -3/2

Получим , так как все

Таким образом, .

ci	БП			0	0	0	bi
x1	x2	x3	x4	x5
	x3 x2 x1				-1/2	-1 -1/3 1/3	132-9

Получим

Таким образом, .

ci	БП			0	0	0	bi
x1	x2	x3	x4	x5
	X4 x2 x1			-1 1/2		-1 2/3 -1/6	108-

Получим

Таким образом, .

;

;

.

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

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

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

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

для незанятых клеток

и для занятых клеток,

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

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

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

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

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

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

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

2. Определяем и

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

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

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

Имеются три поставщика однородного товара с объёмами поставок: а₁ = 100 т, а₂ = 200 т, а₃ = 100 т и четыре потребителя с объёмами потребления b₁ = 80 т, b₂ = 120 т, b₃ = 150 т, b₄ = 50 т. Стоимость транспортных расходов изменяется в определённом диапазоне в зависимости от загрузки дороги и задана матрицей

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

РЕШЕНИЕ. В матрицу расходов введём параметр , где . Получим

.

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

bj ai					ui
		4-
vj

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

Полагая u₁ = 0, , получаем

, откуда

или откуда

или

Аналогично находим, что

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

Имеем

Аналогично находим, что

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

или

Имеем

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

Таким образом, при и

.

Чтобы получить оптимальное решение при , перераспределим поставки товаров в клетку (3, 1), где . Вновь полученное распределение представлено в табл.:

bj ai					ui
		4-
vj

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

.

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

Полученное в таблице оптимальное решение сохраняется при При этом

.

Итак,

.

Перераспределим поставки грузов в клетку (3, 3), где . Получим новое распределение:

bj ai					ui
		4-
vj

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

.

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

Оптимальное решение сохраняется при При этом

.

Итак,

.

Перераспределим поставки грузов в клетку (1, 4), где .

bj ai					ui
		4-
vj

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

.

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

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

.

Итак,

.

Перераспределим поставки грузов в клетку (2, 4), где .

bj ai					ui
		4-
vj

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

.

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

Оптимальное решение сохраняется при При этом

.

Итак,

.

Лекция

Задача о назначениях

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

Матрица стоимостей С имеет вид С = (с_ij), где с_ij – затраты, связанные с назначением i -го ресурса на j -й объект, i = j = , где п – число объектов или ресурсов.

Обозначим:

если i-й ресурс назначается на j-й объект; в противном случае.

Таким образом, решение задачи может быть записано в виде X = (x_ij).

Допустимое решение называется назначением. Оно строится путём выбора ровно одного элемента в каждой строке матрицы X = (x_ij) и ровно одного элемента в каждом столбце этой матрицы.

Элементы с_ij матрицы С, соответствующие элементам x_ij = 1 матрицы Х будем отмечать кружками:

С = (с_ij) = , X = (x_ij) =

Математическая постановка задачи:

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

x_ij = 0 или 1.

Алгоритм решения задачи

Рассмотрим метод, называемый венгерским алгоритмом. Он состоит из следующих шагов:

1) преобразование строк и столбцов матрицы;

2) определение назначения;

3) модификация преобразованной матрицы.

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

2-й шаг. Если после выполнения 1-го шага в каждой строке и каждом столбце матрицы С можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением.

3-й шаг. Если допустимое решение, состоящее из нулей, не найдено, то проводим минимальное число прямых через некоторые столбцы и строки так, чтобы все нули оказались вычеркнутыми. Выбираем наименьший невычеркнутый элемент. Этот элемент вычитаем из каждого невычеркнутого элемента и прибавляем к каждому элементу, стоящему на пересечении проведённых прямых.

Если после проведения 3-го шага оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.