Методические рекомендации
Формально и реальные и фиктивные столбцы и строки в транспортной матрице абсолютно равноправны. Поэтому при нахождении опорных планов фиктивные строки, столбцы и тарифы необходимо анализировать и использовать точно так же как и реальные. Но при вычислении значения ЦФ фиктивные перевозкине учитываются, поскольку они реально не были выполнены и оплачены.
Если величина фиктивных тарифов превышает максимальный из реальных тарифов задачи [ ], то методы минимального элемента и Фогеля позволяют получить более дешевые планы перевозок, чем в случае с нулевыми фиктивными тарифами.
Задача №5.01
Найти тремя методами опорный план ТЗ, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 125, 90, 130, 100 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие:
.
Решение
Проверка сбалансированности задачи показывает, что суммарный объем запасов равен суммарному объему потребностей, т.е. введение фиктивных столбцов или строк не потребуется
.
Результаты нахождения опорного плана различными методами представлены в табл.5.1, 5.2 и 5.3.
Таблица 5.1
Транспортная таблица с опорным планом северо-западного угла
Пункты
отправления,
| Пункты потребления,
| Запасы,
ед. продукции
|
|
|
|
|
|
|
|
|
| 210/85/0
|
|
|
|
|
| 170/165/35/0
|
|
|
|
|
| 65/0
| Потребность,
ед. продукции
| 125/0
| 90/5/0
| 130/0
| 100/65/0
|
|
Опорный план , найденный методом северо-западного угла
[ед.товара].
Соответствующая ЦФ (общие затраты на перевозку)
[руб.].
Таблица 5.2
Транспортная таблица с опорным планом минимального элемента
Пункты
отправления,
| Пункты потребления,
| Запасы,
ед. продукции
|
|
|
|
|
|
|
|
|
| 210/80/45/0
|
|
|
|
|
| 170/45/0
|
|
|
|
|
| 65/0
| Потребность,
ед. продукции
| 125/0
| 90/45/0
| 130/0
| 100/35/0
|
|
Опорный план , найденный методом минимального элемента
[ед.товара], [руб.].
Таблица 5.3
Транспортная таблица с опорным планом Фогеля
|
|
|
|
|
| Штрафы строк,
|
|
|
|
|
| 210/110/0
|
|
|
|
|
|
|
|
|
| 170/45/25/0
|
|
|
|
|
|
|
|
|
| 65/0
|
|
| –
| –
|
| 125/0
| 90/25/0
| 130/20/0
| 100/0
|
|
|
|
|
| Штрафы столбцов,
|
|
|
|
|
|
|
|
|
| –
|
|
|
|
|
|
|
|
| –
|
|
|
|
|
|
|
|
| –
|
|
| –
|
|
|
|
|
| На первом шаге нахождения опорного плана методом Фогеля возникает ситуация равенства значений максимальных штрафов транспортной матрицы (см. табл. 5.3)
.
Минимальные тарифы в этих столбцах также совпадают
.
Поэтому необходимо сравнить суммарные штрафы клеток (2,1) и (3,2)
;
.
Т.к. , то выбираем на первом шаге для заполнения клетку (2,1).
Опорный план , найденный методом Фогеля
[ед.товара], [руб.].
ОБЩАЯ РАСПРЕДЕЛИТЕЛЬНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Теоретическое введение
Общая распределительная задача ЛП – этоРЗ, в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов.
Исходные параметры модели РЗ
1) n – количество исполнителей;
2) m – количество видов выполняемых работ;
3) – запас рабочего ресурса исполнителя ( ) [ед.ресурса];
4) – план по выполнению работы ( ) [ед. работ];
5) – стоимость выполнения работы исполнителем [руб./ед. работ];
6) – интенсивность выполнения работы исполнителем [ед. работ/ед.ресурса].
Искомые параметры модели РЗ
1) – планируемая загрузка исполнителя при выполнении работ [ед. ресурса];
2) – количество работ , которые должен будет произвести исполнитель [ед. работ];
3) – общие расходы на выполнение всего запланированного объема работ [руб.].
Этапы построения модели
I. Определение переменных.
II. Построение распределительной матрицы (см. табл.6.1).
III. Задание ЦФ.
IV. Задание ограничений.
Таблица 6.1
Общий вид распределительной матрицы
Исполнители,
| Работы,
| Запас ресурса,
ед.ресурса
|
|
| …
|
|
|
|
| …
|
|
|
|
|
| …
|
|
| …
| …
| …
| …
| …
| …
|
|
|
| …
|
|
| План, ед.работы
|
|
| …
|
|
|
Модель РЗ
;
| (6.1)
| где – это количество работ j-го вида, выполненных i-м исполнителем.
Этапы решения РЗ
I. Преобразование РЗ в ТЗ:
1) выбор базового ресурса и расчет нормированных производительностей ресурсов :
;
| (6.2)
| 2) пересчет запаса рабочего ресурса исполнителей :
[ед. ресурса];
| (6.3)
| 3) пересчет планового задания :
;
| (6.4)
| 4) пересчет себестоимостей работ:
.
| (6.5)
| II. Проверка баланса пересчитанных параметров и построение транспортной матрицы.
III. Поиск оптимального решения ТЗ .
IV. Преобразование оптимального решения ТЗ в оптимальное решение РЗ , причем переход выполняется по формуле (6.6)
[ед. ресурса],
| (6.6)
| где и – соответственно элементы решения РЗ и ТЗ.
V. Определение количества работ , соответствующее оптимальному решению РЗ :
.
| (6.7)
| VI. Определение ЦФ распределительной задачи согласно (6.1).
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|