«Аналитическое исследование на оптимум экономических функций одной переменной»
Download 0.98 Mb.
|
Kur r Gordeev
|
Решение задачи10:
Найдем начальное решение методом минимального элемента. 1). Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение. Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие. В нашем случае, потребность всех потребителей - 2050 единиц продукции равна запасам всех поставщиков. Согласно условию задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)
2). Минимальный элемент матрицы тарифов находится в ячейке A1B4 и равен 20, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B4 наиболее рентабельный. Запасы поставщика A1 составляют 600 единиц продукции. Потребность потребителя B4 составляет 520 единиц продукции. (см. таблицу пункта 1) От поставщика A1 к потребителю B4 будем доставлять min = { 600 , 520 } = 520 единиц продукции. Разместим в ячейку A1B4 значение равное 520. Мы полностью удовлетворили потребность потребителя B4. Вычеркиваем столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения.
3). Минимальный элемент матрицы тарифов находится в ячейке A3B2 и равен 20, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B2 наиболее рентабельный. Запасы поставщика A3 составляют 650 единиц продукции. Потребность потребителя B2 составляет 750 единиц продукции. (см. таблицу пункта 2). От поставщика A3 к потребителю B2 будем доставлять min = { 650 , 750 } = 650 единиц продукции. Разместим в ячейку A3B2 значение равное 650 Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
4). Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 40, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный. Запасы поставщика A1 составляют 80 единиц продукции. Потребность потребителя B1 составляет 480 единиц продукции. (см. таблицу пункта 3) От поставщика A1 к потребителю B1 будем доставлять min = { 80 , 480 } = 80 единиц продукции. Разместим в ячейку A1B1 значение равное 80 Мы полностью израсходoвали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
5). Минимальный элемент матрицы тарифов находится в ячейке A2B1 и равен 50, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B1 наиболее рентабельный. Запасы поставщика A2 составляют 800 единиц продукции. Потребность потребителя B1 составляет 400 единиц продукции. (см. таблицу пункта 4) От поставщика A2 к потребителю B1 будем доставлять min = { 800 , 400 } = 400 единиц продукции. Разместим в ячейку A2B1 значение равное 400 Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.
6). Минимальный элемент матрицы тарифов находится в ячейке A2B2 и равен 60, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B2 наиболее рентабельный. Запасы поставщика A2 составляют 400 единиц продукции. Потребность потребителя B2 составляет 100 единиц продукции. (см. таблицу пункта 5) От поставщика A2 к потребителю B2 будем доставлять min = { 400 , 100 } = 100 единиц продукции. Разместим в ячейку A2B2 значение равное 100 Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.
7). Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 90, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный. Запасы поставщика A2 составляют 300 единиц продукции. Потребность потребителя B3 составляет 300 единиц продукции. (см. таблицу пункта 6) От поставщика A2 к потребителю B3 будем доставлять 300 единиц продукции. Разместим в ячейку A2B3 значение равное 300 Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Заполненные нами ячейки будем называть базисными, остальные - свободными. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице. Количество базисных ячеек (задействованных маршрутов) равно 6, что и требовалось. Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей. S0 = 40 * 80 + 20 * 520 + 50 * 400 + 60 * 100 + 90 * 300 + 20 * 650 = 79600 ден. ед. Общие затраты на доставку всей продукции, для начального решения , составляют 79600 ден. ед. . Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем: • Находим потенциалы поставщиков и потребителей для имеющегося решения. • Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена. • Выбираем свободную ячейку (с отрицательной оценкой), чтобы максимально снизить стоимость доставки всей продукции на данном шаге решения. • Находим новое решение, как минимум, не хуже предыдущего. • Вычисляем общую стоимость доставки всей продукции для нового решения. Download 0.98 Mb. Do'stlaringiz bilan baham: 
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||