Построение математической модели

Лабораторная работа №3

Решение транспортных задач с использованием MICROSOFT EXCEL

Целью работы является приобретение навыков по­строения математических моделей транспортных задач линейного программи­рования и их решения в среде Microsoft Excel.

Порядок выполнения лабораторной работы

Для выполнения лабораторной работы необходимо:

1) повторить теоретический материал, относящийся к данному занятию;

2) по номеру своего варианта выбрать условие задачи и постро­ить математическую модель транспортной задачи;

3) решить транспортную задачу с помощью надстройки Поиск решений в среде Excel (см. п.2);

4) после выполнения всех пунктов задания необходимо защитить отчет по работе.

Отчет по лабораторной работе должен занимать 5-7 страниц и содержать:

• титульный лист;

• постановку экономической задачи (исходные данные вари­анта);

• экономико-математическую модель с необходимыми коммен­тариями по ее элементам с указанием всех единиц измерения;

• протокол решения задачи, куда должны входить:

а) фрагмент исходного рабочего листа Excel;

б) диалоговое окно Поиск решения;

в) отчет Результаты и его анализ.

Отчет оформляется в установленные преподавателем сроки.

2. Инструкция по использованию
MICROSOFT EXCEL при решении транспортных задач линейного программирования

Рассмотрим в качестве примера решение средствами Microsoft Excel следующей транспортной задачи:

Четыре предприятия экономического района для производства продукции получают сырье от трех поставщиков. Потребности в сырье каждого из предприятий соответственно равны 900, 600, 800 и 600 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 600, 800 и 1000 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей:

.

Составить такой план перевозок, при котором общая стоимость перевозок будет минимальной.

Построение математической модели

Обозначим через x_ij количество единиц сырья, перевозимого из i-го пункта его получения на j-е предприятие. Задача является открытой, так как сумма запасов грузов 600 + 800 + 1000 = 2400 в местах отправления, не равна сумме потребностей грузов в местах назначения 900 + 600 + 800 + 600 = 2900. Так как потребности в грузах превышают их запасы, то вводим фиктивного поставщика с номером 4, у которого запас груза равен 2900 – 2400 = 500. В этом случае общий запас станет равным 2900, и мы получим закрытую транспортную задачу. При этом все тарифы от фиктивного поставщика ко всем потребителям груза полагаются равными нулю. В матрице тарифов появится четвертая строка, в которой стоят все нули:

.

Условия доставки необходимого и вывоза имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

x₁₁ + x₁₂ + x₁₃+ x₁₄= 600, (1)

x₂₁ + x₂₂ + x₂₃+ x₂₄= 800, (2)

x₃₁ + x₃₂ + x₃₃+ x₃₄= 1000, (3)

x₄₁ + x₄₂ + x₄₃+ x₄₄= 500, (4)

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 900, (5)

x₁₂ + x₂₂ + x₃₂+ x₄₂ = 600, (6)

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 800, (7)

x₁₄ + x₂₄ + x₃₄ + x₄₄= 600, (8)

x_ij ≥ 0, i=1,2,3,4, j=1,2,3,4.

При данном плане перевозок их общая стоимость составит:

F = 4x₁₁ + 3x₁₂ + 2₁₃+ 1x₁₄ + 2x₂₁ + 1x₂₂+ 7x₂₃ +

+ 9x₂₄ + 3x₃₁ + 6x₃₂+ + 8x₃₃ + 4x₃₄ → min. (9)

Таким образом, математическая постановка задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (1)–(8), при котором целевая функция (9) принимает минимальное значение.