Алгоритм решения ТЗ

Шаг 1 Построить начальный базисный план перевозок методом минимальной стоимости, методом северо-западного угла или методом двойного предпочтения. Вычислить значение целевой функции при начальном плане перевозок z(X ⁰).

Шаг 2 Вычислить потенциалы строк и столбцов u_i и v_j. по формуле (2.11).

Шаг 3 Для незагруженных клеток вычислить величины превышения стоимости по формуле (2.12).

Шаг 4 Проверить, есть ли незагруженные клетки, для которых величина D_ij > 0 , среди всех таких клеток выбрать одну с наибольшим значением D_ij > 0 и перейти к шагу 5. Если все D_ij £ 0 , то построенный план перевозок является оптимальным.

Шаг 5 От выбранной клетки построить замкнутый контур (см. рисунок 2.1). Разметить вершины контура знаками «+», «–». Вычислить величину изменения объема перевозок по контуру qпо формуле (2.13). По формуле (2.14) сформировать новый улучшенный план перевозок. Вычислить значение целевой функции при улучшенном плане перевозок z(X). Перейти к шагу 2.

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

Постановка задачи. Строящаяся линия разбита на четыре различных по протяженности участка, на которых производятся балластировочные работы. Имеются три балластных карьера, мощность которых достаточна для покрытия общей потребности участков в балласте и составляет соответственно 35, 60, 85 тыс. м³ балласта. Потребность каждого участка в балласте равна соответственно 75, 20, 55, 30 тыс. м³. Карьеры и участки линии связаны между собой транспортной сетью. На основании этой сети установлены расстояния от каждого карьера до любого участка сети, условия перевозки, и соответственно затраты на перевозку тыс. м³ балласта c_ij ( , ).

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

Исходные данные приведены в таблице 2.2.

Таблица 2.2 – Исходные данные задачи

Суммарная мощность поставщиков равна суммарному спросу потребителей, что составляет 180 тыс. м³ (т. е. выполняется условие общего баланса ). Следовательно, данная задача является задачей закрытого типа.

Математическую модель транспортной задачи сформулируем следующим образом. Требуется найти план перевозок

при ограничениях:

на мощности балластных карьеров:

x₁₁ + x₁₂ + x₁₃ + x₁₄ = 35;

x₂₁ + x₂₂ + x₂₃ + x₂₄ = 60;

x₃₁ + x₃₂ + x₃₃ + x₃₄ = 85;

на потребности участков строящейся линии в балласте, которые должны быть полностью удовлетворены:

x₁₁ + x₂₁ + x₃₁ = 75; x₁₂ + x₂₂ + x₃₂ = 20;

x₁₃ + x₂₃ + x₃₃ = 55; x₁₄ + x₂₄ + x₃₄ = 30;

условия неотрицательности, исключающие обратные перевозки

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

z = 9 x₁₁ + 6 x₁₂ + 5x₁₃ + 2 x₁₄ + 11 x₂₁ + 8 x₂₂ + 6x₂₃ +

+ 7 x₂₄ + 7x₃₁ + 10x₃₂ + 4x₃₃ + 8 x₃₄ ®min.

Построим начальный базисный план методом северо-западного угла, методом минимальной стоимости и сравним значения целевой функции для полученных планов.

Метод северо-западного угла. Построение начального базисного плана методом северо-западного угла (таблица 2.3). Назначение перевозок начинаем с верхней левой клетки (северо-западного угла). В клетку (1; 1) записываем наименьшее из значений a₁ и b₁ х₁₁ = min (35, 75) = 35. Так как запасы первого поставщика полностью исчерпаны, из дальнейшего рассмотрения исключаем первую строку. Вычеркнув строку, корректируем потребности первого потребителя на величину x₁₁ = 35, b₁ = 75 – 35 = 40.

Следующая поставка осуществляется от второго поставщика первому потребителю. В клетку (2; 1) назначаем перевозку х₂₁ = min (60; 40) = 40 и исключаем из дальнейшего рассмотрения первого потребителя. Вычеркнув первый столбец, корректируем запасы второго поставщика a₂ = 60 – 40 = 20.

Следующая поставка осуществляется от второго поставщика второму потребителю. В клетку (2; 2) назначаем перевозку х₂₂ = min (40; 40) = 40. Исключаем из дальнейшего рассмотрения второго поставщика и второго потребителя. C оставшейся матрицей поступаем аналогично предыдущему:

х₃₃ = min (85; 55) = 55;

х₃₄ = min (30; 30) = 30.

Таблица 2.3 – План перевозок, построенный методом северо-западного угла.

Построенный начальный план перевозок является вырожденным, так как число ненулевых перевозок x_ij не равно m + n – 1 = 6. Для построения базисного плана в клетку (3; 2) введем нулевую перевозку х₃₂ = 0 так, чтобы не образовывался замкнутый контур из назначенных перевозок.

Значение целевой функции при начальном плане перевозок

z(X ⁰) = 9 × 35 + 11 × 40 + 8 × 20 + 10 × 0 + 4 × 55 + 8 × 30 = 1375 д.е.

Метод минимальной стоимости. Построение начального базисного плана методом минимальной стоимости (таблица 2.4). Назначение перевозок начинаем с клетки (1; 4), имеющей минимальную стоимость перевозки. В клетку (1; 4) записываем наименьшее из значений a₁ и b₄ х₁₄ = min (35, 30) = 30 и исключаем из дальнейшего рассмотрения четвертый столбец. Вычеркнув четвертый столбец, корректируем запасы первого поставщика на величину x₁₄ = 30, a₁ = 35 – 30 = 5.

Следующая поставка осуществляется от третьего поставщика третьему потребителю. В клетку (3; 3) назначаем перевозку х₃₃ = min (85; 55) = 55, исключаем из дальнейшего рассмотрения третьего потребителя. Корректируем запасы третьего поставщика a₃ = 85 – 55 = 30. C оставшейся матрицей поступаем аналогично предыдущему:

х₁₂ = min (5; 20) = 5;

х₃₁ = min (30; 75) = 30;

х₂₂ = min (60; 15) = 15;

х₂₁ = min (45; 45) = 45.

Таблица 2.4 – План перевозок, построенный методом минимальной стоимости.

Построенный начальный план перевозок является базисным, так как число назначенных перевозок x_ij равно m + n – 1 = 6.

Значение целевой функции при начальном плане перевозок:

z(X ⁰) = 6 × 5 + 2 × 30 + 11 × 45 + 8 × 15 + 7 × 30 + 4 × 55 = 1135 д.е.

Построение оптимального плана методом потенциалов.С помощью метода потенциалов доведем до оптимального начальный план, построенный методом минимальной стоимости (см. таблицу 2.4).

Вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках.

Если известен u_i, то v_j = c_ij + u_i, если известен v_j, то u_i = v_j – c_ij. Положим, например, u₁ = 0. Тогда будут вычислены и остальные потенциалы строк и столбцов (таблица 2.6).

Таблица 2.6 – Начальный план перевозок

Для незагруженных клеток вычислим величины превышения стоимости D_ij = v_j – u_i – c_ij :

Полученный план неоптимален. Среди оценок D_ij имеются положительные. Наиболее потенциальной является клетка (2; 3). От клетки (2, 3) строим замкнутый контур: (2; 3), (2; 1), (3; 1), (3; 3). Начиная с клетки (2, 3), разметим вершины контура попеременно знаками плюс «+», минус «–», обходя замкнутый контур в любом направлении.

Из клеток, помеченных знаком «–», выбираем наименьшее значение объема перевозки q = min (45, 55) = 45. Сформируем новый улучшенный план перевозок: на 45 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком « – ».

Новый улучшенный план перевозок представлен в таблице 2.7.

Таблица 2.7 – Улучшенный методом потенциалов план перевозок

Значение целевой функции при улучшенном плане перевозок:

z(X ¹) = 6 × 5 + 2 × 30 + 8 × 15 + 6 × 45 + 7 × 75 + 4 × 10 = 1045 д.е.

Вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках.

Для незагруженных клеток вычислим величины превышения стоимости:

Среди оценок свободных клеток нет положительных, следовательно, построенный план перевозок является оптимальным:

Значение целевой функции при оптимальном плане z(X^*) = 1045 д.е.

Вывод.Для того чтобы общие затраты на перевозки были минимальными, рекомендуется придерживаться полученного оптимального плана X^* (см. таблицу 2.7). В этом случае суммарные затраты будут минимальны и составят 1045 д.е.

Дата добавления: 2014-12-09; просмотров: 408; Нарушение авторских прав

Мы поможем в написании ваших работ!