Лабораторная работа №5. Применение надстройки Solver (Поиск решения) для решения транспортной задачи.

Цель работы.

Научиться использовать возможности MS Excel для решения задач оптимизации в нефтегазовом деле.

Постановка задачи.

Имеются три пункта поставки однородного груза А₁,А₂ и А₃ и пять пунктов В₁, В₂, В₃, В₄, В₅ потребления этого груза. В пунктахА₁, А₂ и А₃ находится груз, соответственно, в количестве а₁, а₂ и а₃ тонн. Впункты В₁, В₂, В₃, В₄, В₅ требуется доставить, соответственно, b₁, b₂, b₃, b₄, b₅тонн груза. Стоимость перевозки единицы груза от пункта поставки до пунктапотребления приведена в следующей матрице – таблице 1:

Таблица 1 – Транспортная задача

Найти план закрепления потребителей за поставщиками однородногогруза, чтобы общие затраты по перевозкам были минимальными. Составить математическую модель задачи и решить её, используя Поиск решения таблицExcel.

а₁ = 400; а₂ = 250; а₃ = 350.

b₁ = 200; b₂ = 170; b₃ = 230; b₄ = 225; b₅ = 175.

Решение.

Найдём сумму запасов и сумму потребностей:

a₁ + a₂ + a₃ = 400 + 250 + 350 = 1 000;

b₁ + b₂ + b₃ + b₄ + b₅ = 200 + 170 + 230 + 225 + 175 = 1 000.

Если сумма запасов равна сумме потребностей, то модель транспортной задачи называется закрытой, в противном случае модель будет открытой. Открытую модель можнопривести к закрытой по правилу: если сумма запасов больше суммы потребностей, то добавляется фиктивный потребитель, потребности которого равны разности между суммой запасов и суммой потребностей, а тарифы перевозок к немуравны нулям, задача превращается в закрытую форму. Если сумма потребностейбольше суммы запасов, то добавляется фиктивный поставщик, запасы которогоравны разности между суммой потребностей и суммой запасов, а тарифы перевозок от него равны нулям, задача превращается в закрытую форму.

Рассмотрим сначала закрытую модель. Сумма запасов равна сумме потребностей, то есть все запасы должны быть вывезены, и все потребности удовлетворены.

Обозначим x_i,j – количество груза, перевозимого от A_i к B_j, и составим математическую модель задачи.

Целевая функция – общие затраты на перевозки:

Ограничения:

Найти неотрицательные значения x_ij, удовлетворяющие системе ограничений и минимизирующие функцию Z – затраты на перевозки.

Рассмотрим последовательность действий для решения этой задачи, используя модуль Поиск решения.

1. Подготовка исходных данных на листе Excel. В ячейку A1 ввеститекст «Транспортная задача ». В ячейку B2 текст «Потребители ». В ячейки cB3по F3 названия потребителей. В ячейку A4 ввести текст «Поставщики ». В ячейку B4 ввести текст «Стоимость перевозки единицы груза ».Вячейку G4 текст «Запасы ». В ячейки A5 по A7 названия поставщиков. В ячейкуA8 текст «Потребности ». Значения запасов ввести в блок ячеек G5:G7. Значения потребностей ввести в блок ячеек B8:F8. Стоимости перевозки единицыгруза от A_i к B_j ввести в блок ячеек B5: F7. Для плана перевозок отведём блокячеек B12:F14. В ячейку A9 ввести текст «Доставлено ». В ячейку H4 ввеститекст «Вывезено ». В ячейку B10 ввести текст «План перевозок ». В ячейки с B11по F11 названия потребителей. В ячейки с A12 по A14 названия поставщиков. ВB15 ввести текст «Затраты на перевозки » (рис. 1).

2. Ввод формул и функций. В ячейку B16 вставим функцию Суммпроизв. В окне этой функции указать первый массив B5:F7, второй массив B12:F14. В ячейки H5, H6, H7 ввести функции: в H5 – функцию СУММ(B12:F12), в H6 – функцию СУММ(B13:F13), в H7 – функцию СУММ(B14:F14). В ячейки B9, C9, D9, E9, F9 ввести функции: в B9 – функцию СУММ(B12:B14), в C9 – функцию СУММ(C12:C14), в D9 – функцию СУММ(D12:D14), в E9 – функцию СУММ(E12:E14), в F9 – функцию СУММ(F12:F14).

Рисунок 1 – Исходные данные

3. Войти в меню Данные, Поиск решения. В окне Поиска решения установим целевую ячейку В16, переключатель установим на min, в поле Изменяя ячейки укажем мышкойблок B12:F14. Далее ввести ограничения. Щёлкнуть по кнопке Добавить.

4. В окне ограничений ввести одно за другим 9 ограничений:

– первое ограничение: H5 = G5;

– второе ограничение: H6 = G6;

– третье ограничение: H7 = G7;

– четвёртое ограничение: B9 = B8;

– пятое ограничение: C9 = C8;

– шестое ограничение: D9 = D8;

– седьмое ограничение: E9 = E8;

– восьмое ограничение: F9 = F8;

– девятое ограничение: B12: F14 ≥ 0 (рис. 2).

Рисунок 2 – Поиск решения

5. После ввода ограничений снова войти в окно Поиск решения и проверить правильность ввода ограничений. Если есть ошибки, использовать кнопки Изменить или Удалить. Затем войти в окно Параметры и поставить флажок вполе напротив надписи Линейная модель. Далее в окне Поиск решениящёлкнуть по кнопке Выполнить.

6. В результате получим оптимальный план перевозок и значение функции минимальных затрат: Z_min = 12 055 единиц (рис. 3).

x₁₁ = 0 x₁₂ = 0 x₁₃ =230 x₁₄=170 x₁₅=0;

x₂₁= 80 x₂₂=170 x₂₃=0 x₂₄=0 x₂₅ =0;

x₃₁=120 x₃₂=0 x₃₃=0 x₃₄ =55 x₃₅ =175.

Рисунок 3 – Результат работы

Задание для самостоятельного решения.

В регионе расположено несколько НГДУ, обеспечивающих определённыеобъёмы добычи нефти, которая поступает на НПЗ, расположенные в различныхрегионах страны и имеющие различные производственные мощности. В силуразноудалённости потребителей от НГДУ затраты на транспортировку нефтиразличаются.

В задаче необходимо составить план закрепления поставщиков за потребителями, который учитывает, по возможности, наиболее полное удовлетворение потребителей НПЗ и при этом обеспечивает минимальные затраты натранспортировку нефти.

Введём условные обозначения:

i – индексНГДУ, i = 1, m;

m – общее число НГДУ в регионе;

j – Индекс НПЗ, j = 1,n;

n – общее число НПЗ.

Известно:

a_i – объёмы добычи нефти в i-ом НГДУ, тыс. т;

b_j – потребность j-го НПЗ в нефти, тыс. т;

c_ij – издержки на транспортировку 1 000 т нефти, тыс. руб.

Таблица 2 – Варианты задания

Указания.

Модель задачи.

1. В качестве неизвестных задачи принимаются переменные x_ij, означающие объём перевозок нефти от i-го НГДУ к j-му НПЗ.

2. В качестве коэффициентов целевой функции выступают издержки наперевозку 1 000 т нефти. Целевая функция минимизируется.