Постановка и решение транспортной задачи

Варианты задач для самостоятельного решения

Составить экономико-математические модели задач, найти оптимальные решения.

Задача 31.

Найти оптимальное целочисленное решение для условия задачи 18 (см.п.1.8).

(Ответ: )

Задача 32.

Найти оптимальное целочисленное решение для условия задачи 19 (см.п.1.8).

(Ответ: )

Задача 33.

Для изготовления трех видов продукции (П1, П2, П3) используется три вида ресурсов (Р1, Р2, Р3). Все условия представлены в таблице 22. Количество продукции каждого вида должно быть целым. Определить план выпуска продукции, при котором прибыль от реализации будет максимальной.

Таблица 22. Исходные данные

Ресурсы	Запас ресурсов, ед.	Норма расхода ресурса на единицу продукции, ед.
П1	П2	П3
Р1
Р2
Р3
Прибыль от реализации единицы продукции

(Ответ: x₁ = 13, x₂ = 28, x₃ = 6, прибыль 125).

Задача 34.

В столовой готовят два вида салатов: А и Б, смешивая три основных ингредиента: помидоры, огурцы и сладкий перец. В таблице 23 приведены нормы расхода ингредиентов, объём запасов каждого ингредиента и прибыль от реализации 1 порции салата видов А и Б. Требуется составить план производства салатов А и Б с целью максимизации суммарной прибыли.

Таблица 23. Исходные данные

Ингредиенты	Расход на 1 порцию (г)	Объем запасов (кг)
А	Б
помидоры			1,2
огурцы			2,1
сладкий перец			0,8
прибыль от 1 порции (р.)

(Ответ: 20 порции салата А, 20 порций салата Б, прибыль 140 р.)

Задача 35.

Из бруса длиной 6 м нарезаются заготовки длиной 2м, 2,5м и 3м. Из одного бруса можно нарезать заготовки различными вариантами. При каждом варианте могут оставаться концевые остатки. За смену требуется нарезать 25 заготовок длиной 2м, 30 заготовок длиной 2,5м, 40 заготовок длиной 3м. Определить, какое количество бруса необходимо нарезать по различным вариантам, чтобы выполнить план по нарезке заготовок, и чтобы при этом общая длина концевых остатков была минимальной.

Указание: Определите возможных 6 вариантов нарезки.

(Ответ: общая длина концевых остатков 19 м, оптимальное решение неединственное, возможны разные варианты записи оптимального решения, общее количество разрезанного бруса 44.)

3. Транспортная задача

Среди задач линейного программирования особое место занимает транспортная задача. Общая формулировка задачи, алгоритм её решения, выбор первоначального опорного плана, критерий оптимальности и особые случаи рассмотрены в курсе лекций «Методы оптимальных решений».

Рассмотрим решение транспортной задачи на примере.

Пример 13. Пусть необходимо организовать перевозку кирпича с т=3 кирпичных заводов на m=4 стройки. Условия транспортной задачи запишем в табличной форме:

Таблица 24. Исходные данные

Поставщики и их мощности (тыс.шт.)	Потребители и их спрос
Стройка 1	Стройка 2	Стройка 3	Стройка 4
Завод 1
Завод 2
Завод 3

Мощность поставщика – это количество кирпича (тыс.шт.), которое он может отправить потребителям за некоторый период времени. Спрос потребителя – это его возможности по использованию кирпича за тот же период времени. В верхнем левом углу каждой клетки области, выделенной утолщенной линией, задана удельная стоимость c_ij поставки 1 тыс.шт. кирпича по маршруту i-j (с завода i настройку j).

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

Составим первоначальный план поставок продукции методом наименьших затрат. Количество продукции, которое можно перевезти по каждому маршруту, записываем в нижние правые углы клеток таблицы

Находим клетку (маршрут) с минимальной удельной стоимостью. Если таких клеток несколько, можно начать с любой из них. Минимальная стоимость c₂₁=3. По маршруту 2 – 1 (с завода 2 на стройку 1) можно перевезти 90 единиц продукции. Ставим в нижний правый угол клетки 90 и перечеркиваем клетку сплошной линией. Клетка заполнена. При этом спрос стройки 2 удовлетворен полностью, поэтому остальные клетки столбца перечеркиваем пунктирной диагональной линией («вычеркиваем столбец»). На заводе 2 остается 175 – 90 = 85 тыс.шт. кирпича.

Таблица 25. Шаг 1

Поставщики и их мощности (тыс.шт.)	Потребители и их спрос
Стройка 1	Стройка 2	Стройка 3	Стройка 4
Завод 1
Завод 2
Завод 3

В незачеркнутых клетках находим клетку с минимальной удельной стоимостью: c₁₃=4. По соответствующему маршруту 1 – 3 можно перевезти 100 тыс.шт. кирпича. Ставим в нижний правый угол клетки 100, перечеркиваем клетку. На заводе 2 нет остатка продукции, поэтому остальные клетки строки перечеркиваем пунктирной линией (табл.26). На стройку 3 остается привезти 120 – 100 = 20 тыс.шт. кирпича.

Таблица 26. Шаг 2

Поставщики и их мощности (тыс.шт.)	Потребители и их спрос
Стройка 1	Стройка 2	Стройка 3	Стройка 4
Завод 1
Завод 2
Завод 3

Далее находим клетку с минимальной удельной стоимостью: c₃₄=4. По соответствующему маршруту 3 – 4 можно перевезти 110 тыс.шт. кирпича, при этом запросы стройки 4 будут удовлетворены полностью. На заводе 3 остатки продукции составят 15 тыс.шт. Ставим в нижний правый угол клетки 110, перечеркиваем клетку и вычеркиваем столбец (табл.27).

Таблица 27. Шаг 3

Поставщики и их мощности (тыс.шт.)	Потребители и их спрос
Стройка 1	Стройка 2	Стройка 3	Стройка 4
Завод 1
Завод 2
Завод 3

Продолжая далее по тому же алгоритму, последовательно получаем таблицы 28 и 29.

Таблица 28. Шаг 4

Поставщики и их мощности (тыс.шт.)	Потребители и их спрос
Стройка 1	Стройка 2	Стройка 3	Стройка 4
Завод 1
Завод 2
Завод 3

Таблица 29. Первоначальный план, метод наименьших затрат

Поставщики и их мощности (тыс.шт.)	Потребители и их спрос
Стройка 1	Стройка 2	Стройка 3	Стройка 4
Завод 1
Завод 2
Завод 3

План первоначального распределения поставок определен. Вычислим суммарные затраты на перевозку по всем маршрутам:

F=4*100+3*90+7*80+6*5+5*15+4*110=1775.

Второй метод (метод «северо-западного угла») определения первоначального опорного плана основан на последовательном заполнении свободных клеток, начиная с верхней левой клетки («северо-западный угол»). При последовательном вычеркивании строк и столбцов каждый раз происходит заполнение верхней левой клетки незачеркнутой области. В результате получим первоначальный опорный план (табл.30).

Таблица 30. Первоначальный план, метод «северо-западного угла»

Поставщики и их мощности (тыс.шт.)	Потребители и их спрос
Стройка 1	Стройка 2	Стройка 3	Стройка 4
Завод 1
Завод 2
Завод 3

Суммарные затраты на поставки по всем маршрутам при таком распределении равны:

F=6*90+5*10+7*70+6*105+5*15 +4*110=2225.

Сравнивая суммарные затраты по двум вариантам первоначального заполнения таблицы поставок, можно сделать вывод, что метод наименьших затрат предпочтительнее, т.к. уже начальное базисное решение ближе к оптимальному.

Дата добавления: 2015-06-27