Транспортна задача линейного программирования

Отчет по устойчивости

Отчет по устойчивости (рис. 10) состоит из двух таблиц.

Таблица 1 содержит информацию, относящуюся к переменным.

1. Результат решения задачи.

2. Нормированная (редуцированная) стоимость, которая показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение.

3. Коэффициенты ЦФ.

4. Предельные значения приращения целевых коэффициентов ∆cj, при которых сохраняется первоначальное оптимальное решение. Например, допустимое увеличение цены на ткань №3 х3 равно 4 грн./м. (строка 11 на рис.9). Это означает, что если цена на ткань №3 возрастет более чем на 4 грн./м., например, станет равной 24 грн./м., то оптимальное решение изменится.

Рис. 9. - Отчёт по устойчивости

Примечание. При выходе за указанные в отчете по устойчивости пределы изменения цен оптимальное решение может меняться как по номенклатуре выпускаемой продукции, так и по объемам выпуска (без изменения номенклатуры).

Таблица 2 (см. рис. 9) содержит информацию, относящуюся к ограничениям.

1. Величина использованных ресурсов в колонке "Результ. значение".

2. Предельные значения приращения ресурсов ∆bi. В графе "Допустимое Уменьшение" показывают, на сколько можно уменьшить (устранить излишек) или увеличить (повысить минимально необходимое требование) ресурс, сохранив при этом оптимальное решение.

3. Ценность дополнительной единицы i-го ресурса (теневая цена) рассчитывается только для дефицитных ресурсов.

Столбец «Теневая цена» показывает увеличение целевого значения в ответ на увеличение ограничения на одну единицу.

Столбец «Ограничение». Правая часть просто выводит используемые в задаче значения ограничений. Столбцы «Допустимое увеличение» и «Допустимое уменьшение» показывают изменение значения ограничения (показанного в столбце «Ограничение Правая часть») до момента увеличения или уменьшения оптимальных значений в изменяемых ячейках.

Отчет по пределам

Этот отчет приведен на рис.10. В нем показано, в каких пределах значения изменяемых ячеек могут быть увеличены или уменьшены без нарушения ограничений задачи. Для каждой переменной ячейки отчет представляет оптимальное значение, а также наименьшее и наибольшее значения, которые может принимать ячейка без нарушения ограничений.

Рис. 10. - Отчёт по пределам

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

При данных объёмах изготовления трех видов ткани максимальная прибыль от её реализации при соблюдении указанных производственных издержек будет составлять 2692 грн. Фирма будет получать максимальную прибыль в размере 2692 грн. в случае производства 77 метров ткани №2 и 77 метров ткани №3. Ткань №1 в оптимальный план выпуска не включена, значит, ее изготовление будет приносить вместо прибыли только убытки.

Из четырех видов ресурсов, которые представлены станком 1 типа, станком 2 типа, пряжей и красителем, дефицитными являются пряжа и красители, а работа двух станков не используются в полной мере. Излишек работы станка 1-го типа составляет 27308 станко-часов, а излишек работы станка 2-го типа – 42692 станко-часов. Таким образом, эти два ресурса в совокупности не используются на 66%, что составляет практически 2/3 общего запаса. Можно сказать, что фирма могла бы работать эффективнее при рациональном распределении ресурсов и, соответственно, получать большую прибыль. Денежные средства, сбережённые после работы станков, предположим, для других целей в количестве, необходимом для данного оптимального плана выпуска, которое является меньше исходного, можно направить на повышение границы дефицитного ресурса, то есть на увеличение пряжи и красителей.

Однако в условиях нестабильности современной экономической системы невозможно точно спланировать оптимальный план на будущее, поэтому в него могут вноситься разнообразные корректировки. Если производитель ткани всё-таки включит в оптимальный план изготовление ткани №1, то производство каждой единицы этого вида ткани будет уменьшать прибыль на 3 грн. Аналогично, при выпуске каждой дополнительной единицы ткани №2 фирма будет терять прибыль в размере 0,92 грн., а при выпуске одной дополнительной единицы ткани №3  – в размере 4 грн.

Исходя из всего выше сказанного, можно сказать, что с помощью полученных отчетов руководитель предприятия может выбирать воспользоваться оптимальным решением задачи, увеличить объемы производства или наоборот уменьшить их. Главное при принятии решения соблюдать ограничения, которые получены в отчетах, не нарушая их, иначе выбранная стратегия перестанет быть оптимальной.

Проанализировав полученные результаты, можно сделать вывод о том, что оптимальный план производства следующий:

1.                      Ткань №1 – 0;

2.                      Ткань №2 – 77;

3.                      Ткань №3 – 77;

Максимальный доход будет составлять 2692 грн.

РАЗДЕЛ 2. ТРАНСПОРТНА ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

2.1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ.

Транспортная задача – один из наиболее важных частных случаев общей задачи линейного программирования. Содержательно транспортная задача формулируется следующим образом.

Пусть в пунктах производится некоторый однородный продукт, причем объем производства этого продукта в пункте составляет единиц, ( – количество пунктов производства). Произведенный в пунктах производства продукт должен быть доставлен в пункты потребления , причем объем потребления в пункте составляет единиц продукта, ( – количество пунктов потребления). Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта в пункт , составляет денежных единиц. Задача состоит в организации такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.

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

Пусть

– множество пунктов производства;

– множество пунктов потребления;

– множество запасов пунктов производства,

где – запас -го пункта производства;

– множество заказов пунктов потребления,

где – заказы -го пункта потребления;

– матрица стоимости перевозок,

где – стоимость перевозки единицы продукции от -го поставщика к -му потребителю;

– решение задачи (требуется найти),

где – количество единиц продукции перевезенной от -го поставщика к -му потребителю;

– целевая функция, которая обеспечивает минимальную стоимость перевозок.

Получаем общую постановку транспортной задачи:

;              (1)

.                                      (2)

Группа ограничений (2) связана с тем обстоятельством, что объем вывезенного продукта из каждого пункта производства соответствует объемам производства, а объем ввезенного в пункт потребления продукта в точности соответствует его потребности. При этих ограничениях необходимым и достаточным условием для разрешимости транспортной задачи является условие баланса

                                             (3)

2.2 РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ В MS EXCEL

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

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

Данную задачу решаем, используя инструмент Поиска решений MS Excel.

Решение

1. Проверка условий закрытости задачи

Закрытая  (или классическая) транспортная задача – это транспортная задача, в которой выполняется условия баланса (3), что означает равенство между объемом производства и объемом потребления.

Открытая транспортная задача – это транспортная задача с нарушением условия баланса (3), что означает либо превышения объема поставок над объемом потребления, либо наоборот. Такая задача сводится к классической транспортной задачи путем введения фиктивного пункта поставок (или потребления) с запасом (или заказом) равным разности объемов поставок и потребления.

В данном случае Σai=125 >Σbj=127 => имеем дело с открытой моделью транспортной задачи.

Сведем ее к закрытой введением фиктивного магазина B5 с потребностью b5=127-125=2 и стоимостью перевозок сi5=0.

2. Строим математическую модель закрытой транспортной задачи

Пустьxij – количество товара, перевозимого из Аi в Bj.

Тогда

целевая функция

Z= (7x11+x12+13x13+2x14+8x21+4x22+5x23+8x24+5x31+2x32+3x33+ 7x34+5x41+5x42+8x43+4x44+x51+9x52+7x53+5x54) → min

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

3. Решение задачи в MS Excel

Для решения задачи в MS Excel введем данные как показано на рисунке 1.

В ячейку В15 введем формулу =СУММ(B10:B14) и пробуксируем эту формулу для ячеек С15, D15, E15, F15.

В ячейку G10 введем формулу = СУММ(B10:F10) и пробуксируем эту формулу для ячеек G11, G12, G13, G14.

Рис.1 - Исходные данные транспортной задачи

В ячейку F18 введем формулу для определения целевой функции {=СУММПРОИЗВ($B$2:$F$6;B10:F14)}.

В результате выполнения ввода формул в MS Excel на рисунках 2 и 3 представлены результаты ввода.