КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Определение диапазона оптимального решения выпуска продукции при изменении условий реализации
|
|
|
|
Задача. Предприятие должно выпустить два вида продукции А и В, для изготовления которых используются три вида сырья. Нормы расхода сырья каждого вида на производство единицы данного вида приведены в таблице. В ней указаны такие запасы сырья каждого вида, которые могут быть использованы на производство единицы продукции данного вида. Известно, что цена единицы может изменяться для изделия А от 2 до 12 усл. ед., а для изделия В – от 13 до 3 усл. ед., причём эти изменения определяются выражениями 
и 
, где 
.
Для каждого из возможных значений цены единицы продукции данного вида найти такой план их производства, при котором общая стоимость продукции является максимальной.
| Вид сырья | Нормы расхода сырья на единицу продукции, т | Запасы сырья, т | |
| А | В | ||
| I II III |
РЕШЕНИЕ. Обозначим через х1 количество единиц продукции А, через х2 – количество единиц продукции В. Математическая модель имеет вид
при ограничениях:
Область допустимых решений – многоугольник ОАВСD. Полагая 
, 
, строим 
. Перемещая линию уровня по направлению 
, находим, что в точке А(0, 11) задача имеет оптимальное решение. Таким образом, при 
, 
.
Если уравнение прямой имеет вид
, то угловой коэффициент равен k=-A/B.
Угловой коэффициент линии уровня, перпендикулярной , при произвольном значении 
равен 
|
: будет оставаться оптимальным для всех , при которых соответствующая линия уровня находится внутри угла, образованного прямыми 
и (2). Угловой коэффициент прямой (2) k=-2/2=-1. По условию 
откуда 
Решение остаётся оптимальным при 
При 
линия уровня совпадает с прямой (2) и оптимальными будут все точки, лежащие на прямой (2), в том числе и точка В(1, 10), лежащая на пересечении прямых (2) и (3).
Оптимальное решение будет сохраняться до тех пор, пока при изменении 
линия уровня не совпадёт с прямой (3), что будет соответствовать новому оптимальному решению 
. Найдём новый диапазон изменения : 
, 
так как k3= -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. Если 
, производим перераспределение поставок и получаем новое оптимальное решение. Если 
, то процесс решения окончен.
Нахождение оптимальных путей транспортировки грузов при нестабильной загрузке дорог
Имеются три поставщика однородного товара с объёмами поставок: а1 = 100 т, а2 = 200 т, а3 = 100 т и четыре потребителя с объёмами потребления b1 = 80 т, b2 = 120 т, b3 = 150 т, b4 = 50 т. Стоимость транспортных расходов изменяется в определённом диапазоне в зависимости от загрузки дороги и задана матрицей
Определить оптимальное решение перевозок, обеспечивающее минимальные транспортные затраты.
РЕШЕНИЕ. В матрицу расходов введём параметр , где 
. Получим
.
Полагая , решаем задачу методом потенциалов, определим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь вид:
| bj ai | ui | ||||
| 4-
| 
| |||
| 
| 
| |||
| 
| ||||
| vj |
| 
| 
| 
|
В таблице ui и vj – потенциалы строк и столбцов. Для занятых клеток они определяются из условия
Полагая u1 = 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 |
|
|
| 
|
Оценки свободных клеток:
.
Пределы изменения :
Оптимальное решение сохраняется при 
При этом
.
Итак,
.
|
|
|
|
Дата добавления: 2014-01-11; Просмотров: 493; Нарушение авторских прав?; Мы поможем в написании вашей работы!