Модель без дефицита
В соответствии с терминологией транспортной модели поставщики представлены обычным и сверхурочным производством для различных этапов. Потребители задаются спросом соответствующих этапов. Затраты на «транспортировку» единицы продукции от любого поставщика к любому потребителю представляются суммой соответствующих производственных затрат и затрат на хранение единицы продукции.
Матрица полных затрат для эквивалентной транспортной задачи приведена в следующей таблице:
спрос на этапе j |
| избыток | |||||
| 1 | 2 | 3 | ... | N |
|
|
R1 | C1 | C1 + h1 | C1 + h1 + h2 |
| C1 + h1 + …+ hN–1 | 0 | aR1 |
T1 | d1 | d1 + h1 | d1 + h1+ h2 |
| d1 + h1+ …+ hN–1 | 0 | aT1 |
R2 |
| C2 | C2 + h2 |
| C2 + h2 + …+ hN–1 | 0 | aR2 |
T2 |
| d2 | d2 + h2 |
| d2 + h2+ …+ hN–1 | 0 | aT2 |
... |
|
|
|
|
|
| ... |
RN |
|
|
|
| CN | 0 | aRN |
TN |
|
|
|
| dN | 0 | aTN |
| b1 | b2 | b3 | ... | bN | S |
|
Дополнительный столбец используется для балансировки транспортной задачи, т.е. S = . Затраты на единицу продукции в дополнительном столбце равны нулю. Так как дефицит не допускается, то продукцию, выпускаемую на рассматриваемом этапе, нельзя использовать для удовлетворения спроса предыдущих этапов. В таблице это ограничение представлено заштрихованными ячейками, что, в сущности, эквивалентно очень большим затратам на единицу продукции.
Так как задолженность в модели не допускается, то для каждого этапа k в нее необходимо включить ограничение, состоящее в том, что накопленный спрос не должен превышать соответствующий общий объем произведенной продукции, т.е.
³ , k = 1, 2,..., N.
Так как спрос на этапе i должен быть удовлетворен прежде, чем спрос на этапах i + 1, i + 2,..., N, и поскольку на функцию производственных затрат наложены специальные требования, нет необходимости применять общий алгоритм решения транспортной задачи. Сначала путем последовательного назначения максимально возможных поставок по наиболее дешевым элементам первого столбца удовлетворяется спрос на этапе 1. Затем корректируются значения ai, которые после этого определяют оставшиеся мощности для различных этапов. Далее рассматривается этап 2, и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжается до тех пор, пока не будет удовлетворен спрос этапа N.
Пример 6.6.
Период I | Мощность (в единицах продукции) | Спрос bi (в единицах продукции) | ||
aRi | aTi | |||
1 2 3 4 | 100 150 100 200 | 50 80 100 50 | 120 200 250 200 | |
Всего | 550 | 280 | 770 |
Производственные затраты на всех этапах одинаковы, т.е. ci = 2 и di = 3 при всех i. Издержки на хранение также постоянны на всех этапах и равны hi = 0,1 для любого i. Условия эквивалентной транспортной задачи приведены в таблице:
| 1 | 2 | 3 | 4 | Избыток |
|
R1 | 2 100 | 2,1 – | 2,2 – | 2,3 – | 0 – | 100 |
T1 | 3 20 | 3,1 – | 3,2 20 | 3,3 – | 0 10 | 50; 30; 10 |
R2 |
| 2 150 | 2,1 – | 2,2 – | 0 – | 150 |
T2 |
| 3 50 | 3,1 30 | 3,2 – | 0 – | 80; 30 |
R3 |
|
| 2 100 | 2,1 – | 0 – | 100 |
T3 |
|
| 3 100 | 3,1 – | 0 – | 100 |
R4 |
|
|
| 2 200 | 0 – | 200 |
T4 |
|
|
| 3 – | 0 50 | 50 |
| 120 | 200 | 250 | 200 | 60 |
|
| 20 | 50 | 150 |
| 10 |
|
|
|
| 50 |
|
|
|
|
|
| 20 |
|
|
|
В оптимальности решения можно убедиться, воспользовавшись условием оптимальности алгоритма транспортной задачи. Заметим, что полученное оптимальное решение является вырожденным.
Упражнение:
а) Определите следующие величины:
объем производства на этапе 1 для этого же этапа (120 единиц);
объем производства на этапе 1 для этапа 2 (нулевой);
объем производства на этапе 1 для этапа 3 (20 единиц);
объем производства при обычном режиме работы и в сверхурочное время на этапе 1 (100 и 40 единиц соответственно);
запас, переходящий из этапа 1 в этап 3 (20 единиц);
запас, переходящий из этапа 2 в этап 3 (50 единиц);
запас, переходящий из этапа 3 в этап 4 (нулевой);
б) Предположив, что на этапе 4 требуется 55 дополнительных единиц продукции, определите, каким образом эту продукцию нужно выпустить (50 единиц в сверхурочное время на этапе 4 и 5 единиц в сверхурочное время на этапе 1).
- Учебное пособие
- Оглавление
- 2. Элементы линейной алгебры 21
- 3. Линейное программирование 48
- 4. Теория двойственности в линейном программировании 98
- 5. Целочисленные модели исследования операций 137
- 6. Экономические задачи, сводящиеся к транспортной модели 160
- Введение в исследование операций
- 1.1 Основные определения
- Этапы исследования операций
- Домашнее задание №1
- 2. Элементы линейной алгебры
- 2.1. Алгебра матриц
- 2.1.1. Виды матриц
- 2.1.2. Действия над матрицами
- Домашнее задание №2
- 2.2. Вычисление определителей
- Домашнее задание №3
- 2.3. Решение систем алгебраических уравнений
- 2.3.1. Основные понятия и определения
- 2.3.2. Формулы крамера и метод обратной матрицы
- 2.3.3. Метод жордана-гаусса
- Домашнее задание №5
- 2.4. Векторное пространство
- 2.4.2. Размерность и базис векторного пространства
- Домашнее задание №6
- 2.5. Решение задач линейной алгебры с помощью ms excel
- 3. Линейное программирование
- 3.1. Постановки задачи линейного программирования
- 3.1.1. Общая постановка задачи линейного программирования
- 3.1.2. Основная задача линейного программирования
- 3.1.3. Каноническая задача линейного программирования
- 3.2. Графический метод решения злп
- Домашнее задание №7
- Домашнее задание №8
- 3.3. Анализ решения (модели) на чувствительность
- Домашнее задание №9
- 3.4. Решение линейных моделей симплекс-методом.
- Переход от одной к-матрицы злп к другой к-матрице
- Алгоритм симплекс-метода
- Домашнее задание №10
- 3.4. Двойственный симплекс-метод (р-метод)
- Определение р-матрицы злп
- Условия перехода от одной р-матрицы злп к другой
- Алгоритм р-метода
- Решение задач р-методом
- Домашнее задание №11
- Домашнее задание №12
- 3.5. Решение злп двухэтапным симплекс-методом
- Первый этап - решение вспомогательной задачи
- Второй этап - решение исходной задачи
- Домашнее задание №13
- 4. Теория двойственности в линейном программировании
- 4.1. Определение и экономический смысл двойственной злп
- 4.2. Основные положения теории двойственности
- Получение оптимального плана двойственной задачи на основании теоремы 4
- На первой итерации получен оптимальный план злп (4.24).
- 4.3. Решение злп с помощью Ms Excel
- 4.4. Анализ решения злп на основе отчетов ms excel
- 5. Целочисленные модели исследования операций
- 5.1. Метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)
- X1, х2 0, целые.
- Подробное описание метода
- 5.2. Задача коммивояжера
- Применение метода ветвей и границ для решения задачи коммивояжера
- Ветвление
- Построение редуцированных матриц и и вычисление оценок снизу
- Формирование списка кандидатов на ветвление
- 6. Экономические задачи, сводящиеся к транспортной модели
- 6.1.Транспортная задача линейного программирования
- Методы составления первоначальных опорных планов
- Метод потенциалов решения транспортной задачи
- Проверка выполнения условия оптимальности для незанятых клеток
- Выбор клетки, в которую необходимо поместить перевозку
- Построение цикла и определение величины перераспределения груза
- Проверка нового плана на оптимальность
- Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке
- 6.2.Экономические задачи, сводящиеся к транспортной модели
- Оптимальное распределение оборудования
- Формирование оптимального штата фирмы
- Задача календарного планирования производства
- Модель без дефицита
- Модель с дефицитом
- 6.3.Задача о назначениях
- Венгерский алгоритм
- Оптимальное исследование рынка
- Оптимальное использование торговых агентов