Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное профессиональное учреждение Высшего профессионального образования Всероссийский заочный финансово-экономический институт Филиал в городе Туле ЛАБОРАТОРНАЯ РАБОТА По дисциплине: экономико-математические методы и прикладные модели. Вариант 4
Выполнил: студент 3 курса факультета Менеджмента и маркетинга специальность ГМУ группы дневной
№ личного дела:
Проверил: Тула 2009г. Задача. На складах А, В, С и Д находятся соответственно 50т, 40, 40 и 70т муки, которую нужно доставить четырем хлебозаводам. Первому хлебозаводу требуется 50т муки, второму - 40т, третьему - 50т и четвертому - 60т муки. Стоимости доставки одной тонны муки со склада А каждому хлебозаводу соответственно равны 8, 3, 5 и 2 ден. единиц, со склада В - 7, 4, 9, и 8, со склада С - 6, 3, 3 и 1, со склада Д - 2, 4, 1 и 5 ден. единиц. Составить план перевозки муки, обеспечивающий минимальные транспортные расходы. Решение: Поставщики (склады) Потребители (Хлебозаводы) Запасы
B1 B2 B3 B4
A 8 3 5 2 50
В 7 4 9 8 40
С 6 3 3 1 40
D 2 4 1 5 70
Потребности 50 40 50 60 200 200
Транспортная задача является закрытой, т.к. потребности потребителей равны объему поставщиков. Сформулируем экономико-математическую модель исходной транспортной задачи. F(x) = 8x11 + 3x12 + 5x13 + 2x14 + 7x21 + 4x22 + 9x23 + 8x24 + 6x31 + 3x32 + 3x33 + 1x34 + 2x41 + 4x42 + 1x43 + 5x44 > min Функциональные ограничения для поставщиков: 8x11 + 3x12 + 5x13 + 2x14 ? 50 7x21 + 4x22 + 9x23 + 8x24 ? 40 6x31 + 3x32 + 3x33 + 1x34 ? 40 2x41 + 4x42 + 1x43 + 5x44 ? 70 x ij ? 0 Функциональные ограничения для потребителей: 8x11 + 7x21 + 6x31 + 2x41 ? 50 3x12 + 4x22 + 3x32 + 4x42 ? 40 5x13 + 9x23 + 3x33 + 1x43 ? 50 2x14 + 8x24 + 1x34 + 5x44 ? 60 x ij ? 0 Для получения начального опорного плана воспользуемся методом наименьших стоимостей (наименьшего элемента). В различных модификациях этого метода заполнение клеток матрицы перевозок проводится с учетом значений величин сij. Так, в модификации «двойного предпочтения» отмечают клетки с наименьшими стоимостями перевозок сначала по каждой строке, а затем по каждому столбцу. Клетки, имеющие две отметки, заполняют в первую очередь, затем заполняют клетки с одной отметкой, а данные о нераспределенном грузе записывают в неотмеченные клетки с наименьшими стоимостями. При этом из двух клеток с одинаковой стоимостью перевозок предпочтение отдается клетке, через которую осуществляется больший объем перевозок. Поставщики (склады) Потребители (Хлебозаводы) Запасы
B1 B2 B3 B4
A 8 3 30 5 2 20 50
В 7 30 4 10 9 8 40
С 6 3 3 1 40 40
D 2 20 4 1 50 5 70
Потребности
50
40
50
60 200 200
Суммарные затраты на перевозки, представленные в данной таблице составляют: F(x) = 3*30 + 2*20 + 7*30 + 4*10 + 1*40 + 2*20+ 1*50 = 510 Проверим полученный план на оптимальность. Для этого рассчитаем потенциалы поставщиков и потребителей (vj, ui) по формуле: vj = ui + сij следующим образом: задавая u1 = 0, находим по клетке (1;2) v2 = 3, по клетке (2;2) u2 = -1, а по (2;1) v1 = 6; затем по клетке (1;4) v4 = 2, а по (3;4) u3 = 1, по (4;1) находим u4 = 4 и наконец, по клетке (3;3) находим v3 = 5. Поставщики (склады) Потребители (Хлебозаводы) Запасы ui
B1 B2 B3 B4
A 8 - 3 30 5 + 2 20 50 0
В - 7 30 + 4 10 9 8 40 -1
С 6 3 + 3 - 1 40 40 1
D + 2 20 4 - 1 50 5 70 4
Потребности
50
40
50
60 200 200
vj 6 3 5 2
На основании рассчитанных потенциалов определяем оценки для всех клеток матрицы перевозок по следующей формуле:
Условием оптимальности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок. Поскольку в нашем случае имеется отрицательное значение, то это говорит о неоптимальности плана. Для улучшения плана воспользуемся методом потенциалов. Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой (в данном случае клетка (3,3)). Для выбранной клетки строим замкнутый контур, начальная вершина которого лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках. В вершинах контура расставляем поочередно знаки «+» и «–», начиная со знака «+» в выбранной свободной клетке. Величина перераспределяемой поставки определяется как наименьшая из величин поставок в вершинах контура со знаком «–» (клетка (1,2)). На эту величину (30) увеличиваются поставки в вершинах «+» и уменьшаются поставки в вершинах со знаком «–». Если величина перераспределяемой поставки равна поставкам не в одной, а в нескольких вершинах контура со знаком «–», то освобождается только одна клетка, обычно с наибольшей стоимостью перевозки, а все другие такие клетки остаются занятыми с нулевой поставкой. Результат указанных операций: Поставщики (склады) Потребители (Хлебозаводы) Запасы ui
B1 B2 B3 B4
A 8 3 0 5 2 50 50 0
В 7 4 40 9 8 40 -1
С 6 3 3 30 1 10 40 1
D 2 50 4 1 20 5 70 3
Потребности
50
40
50
60 200 200
vj 5 3 4 2
Аналогично с первым планом определим оценки для всех клеток матрицы перевозок:
Поскольку отрицательных оценок нет, то план перевозок является оптимальным. Суммарные затраты на перевозки, при оптимальном плане составляют: F(x) = 2*50 + 4*40 + 3*30 + 1*10 + 2*50 + 1*20 = 480 Наличие нулевых оценок свободных клеток в оптимальном плане перевозок свидетельствует о неединственности оптимального плана. Решаем в MS Excel 1.Создаем форму: Для этого необходимо выполнить резервирование изменяемых ячеек: в блок ячеек В3:Е6 вводится «1». Таким образом, резервируется место, где после решения задачи будет находиться распределение поставок, обеспечивающее минимальные затраты на перевозку груза. 2.Вводим граничные условия. Введение условия реализации мощностей поставщиков, т.е. аi=?хij где аi – мощность i-го поставщика xij – объем поставки груза от i-го поставщика к j-му потребителю n – количество потребителей. Для этого необходимо выполнить следующие операции: - курсор в ячейку А3 - щелкнуть знак «?» - выделить необходимые для суммирования ячейки В3:Е3 - нажать ENTER – подтверждение ввода формулы для суммирования. Аналогичные действия выполняем для ячеек А4, А5, А6. Введение условия удовлетворения запросов потребителей, т.е. bj=?xij где b – мощность j-го потребителя m – количество поставщиков. Для этого необходимо выполнить следующие операции: - курсор в В7 - щелкнуть знак «?». При этом автоматически выделяется весь столбец В3:В6 - ENTER – подтверждение суммирования показателей выделенного столбца. Последовательность этих действий выполнить для ячеек С7 – Е7. 3.Вводим исходные данные. 4.Назначаем целевую функцию. Для вычисления значения целевой функции необходимо зарезервировать ячейку и ввести формулу для ее вычисления: F=??CijXij где Сij – стоимость доставки единицы груза от i-го поставщика к j-му потребителю Хij – объем поставки груза от i-го поставщика к j-му потребителю. Для этого: - курсор в ячейку В15. В данную ячейку будет помещаться значение целевой функции после решения задачи - щелкнуть Мастер функций - в окне Категория выбрать Математические - в окне Функция выбрать СУММПРОИЗВ - ОК - в окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией. - в поле Массив 1 указать адреса В11:Е14 - в поле Массив 2 указать адреса В3:Е6 - ОК
Получаем:
5.Вводим зависимости из математической модели. - щелкнуть Сервис – Поиск решения - курсор подвести в поле Установить целевую (ячейку) - ввести адрес $B$15 - установить направление изменения целевой функции, равное минимальному значению - ввести адреса изменяемых ячеек В3:Е6.
6.Вводим ограничения: - щелкнуть Параметры - установить Линейная модель - установить Неотрицательные значения - ОК. После этого осуществляется выход в поле Поиска решений - нажать Выполнить.
После выполнения всех вышеуказанных действий на экран выводится окно Результаты поиска решения. В матрице перевозок содержатся оптимальные объемы поставок грузов от поставщика потребителям, дающие минимум затрат на доставку. Значение целевой функции содержится в ячейке В15 и равно 480.
Ответ: Суммарные затраты на перевозки, при оптимальном плане составляют: F(x) = 480
