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

ЗАВДАННЯ НА курсову РОБОТУ

1.             Зміст курсової роботи:

Вступ

РОЗДІЛ 1. Оптимізаційна задача лінійного програмування

1.1 Математична постановка задачі лінійного програмування

1.2 Рішення задачі лінійного програмування в MS Excel

РОЗДІЛ 2. Транспортна задача лінійного програмування

2.1 Математична постановка транспортної задачі

2.2 Рішення транспортної задачі в MS Excel

РЕФЕРАТ

Курсовая работа содержит 31 страницы, 17 рисунков, 3 таблицы, 7 источников.

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

Целью данной работы является найти максимальную прибыль и минимальные транспортные затраты.

В процессе решения оптимизационной и транспортной задачи найдены оптимальные варианты решения поставленной цели.

СОДЕРЖАНИЕ

Введение              5

РАЗДЕЛ 1. Оптимизационная задача линейного программирования.              6

1.Математическая постановка задачи линейного программирования.              6

1.2 Решение задачи линейного программирования в MS Excel              8

РАЗДЕЛ 2. Транспортна задача линейного программирования.              19

2.1 Математическая постановка транспортной задачи.              19

2.2 Решение транспортной задачи в MS Excel              21

Вывод              30

ВВЕДЕНИЕ

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

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

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

Задачей курсовой работы является создание оптимального плана транспортной задачи и задачи линейного программирования.

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

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

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

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

Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта. Использование математического моделирования в экономике позволяет углубить количественный экономический анализ, расширить область экономической информации, интенсифицировать экономические расчеты.

Можно выделить три основные этапа проведения экономического моделирования.

1 этап. Постановка цели и задачи исследования. Качественное описание объекта в виде экономической модели.

2 этап. Формирование  математической модели изучаемого объекта, выбор (или разработка) методов исследования, программирование модели на ЭВМ, подготовка исходной информации. Проверяются пригодность машинной модели на основании правильности получаемых с её помощью результатов и оценка их устойчивости.

3 этап. Основной этап экономико-математического моделирования, анализ математической модели, проведение машинных расчетов, обработка и анализ полученных результатов.

При использовании экономико-математических методов на ПК  позволяет достаточно дешево и быстро производить сравнение многочисленных вариантов планов и управленческих решений. В результате отбираются наиболее оптимальные варианты.

Для конкретного предприятия можно сформировать различные варианты плана производства. При этом необходимые для его выполнения ресурсы и полученные от его реализации результаты будут различны. Один вариант плана с точки зрения достижения величины какого-либо из показателей или соблюдения выполнения определенных условий будет лучше, другой – хуже. Когда вариант плана производства является наилучшим с позиции достижения определенного уровня конкретного показателя, например, получения максимальной прибыли, максимальной производительности труда и т.д., то говорят об оптимальном плане, а процесс его составления называют оптимальным планированием.  Оптимальный план может, например, обеспечить производство максимального объема продукции при определенном уровне наличных ресурсов или минимальную себестоимость продукции и т.п.

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

Показатель, по которому оценивается мера эффективности плана, его оптимальность, называется критерием оптимальности. Критерий оптимальности должен удовлетворять следующим требованиям: 1) быть единственным, т.е. одним для данной задачи; 2) количественно измеряться.

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

В общем, виде задача линейного программирования имеет вид:

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

1.2 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ  В MS EXCEL

Ткань трех видов производится на станках двух типов с различной производительностью. Для изготовления ткани используется пряжа и красители. В таблице указаны мощности станков  (в тысячах станко-часов), ресурсы пряжи и красителей (в тыс. кг), производительности станков по каждому виду пряжи (м/ч), норма расхода пряжи и краски (в кг на 1000 м) и цена 1 метра ткани. Необходимо определить оптимальный ассортимент, максимизирующий прибыль фабрики.

Решение

Этап 1. Определение переменных.

Пусть изготавливается:

              х1 –метров ткани №1;

              х2 –метров ткани №2;

              х3 –метров ткани №3;

На рис.1. представлены исходные данные.

Этап 2. Определение цели.

Цель состоит в максимизации общего дохода от реализации всех видов ткани.

Этап 3. Целевая функция задачи.

Пусть F – общий доход от реализации товара, тогда целевая функция

              F* = 15х1 + 15х2 + 20х3 max                                                       

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

Этап 4. Ограничения на производственный процесс.

Переведем объем ресурсов из тыс. кг и тыс. станко-часов в килограммы и станко-часы, разделив на 1000.

Станки I типа                                                        20х1 + 10х2 + 25х3 ≤ 30000

Станки II типа                                                        8х1 + 20х2 + 10х3 ≤ 45000

Пряжа                                                       120х1 + 180х2 + 5210х3 ≤ 30000

Красители                                                             10х1 + 5х2 + 8х3 ≤ 1000

условие неотрицательности                                          x1, x2, x3 ≥ 0

Максимизировать F* = 15х1 + 15х2 + 20х3 при указанных выше условиях ограничений.

Этап 5. Ввод исходных данных.

Для построения расчётной таблицы вводим исходные данные.

Введём переменные в ячейки В3 – D3, а их значения соответственно в ячейки В4 – D4.

Запишем целевую функцию в ячейку

F4 =B9*B4+C9*C4+D9*D4.

Заполним оставшуюся часть данных. Результат см. рис.2.

Рис. 2. – Ввод исходных данных в MS Excel

Далее вводим ограничения на производственный процесс (cм. рис.3).

Рис. 3. – Ограничения на производственный процесс

Этап 6. Ввод условий задачи.

Для ввода условий задачи выбираем команду «Поиск решения». Устанавливаем целевую ячейку. Вводим направление целевой функции максимальному значению. В окно ввода «Изменяя переменные» вводим адреса искомых переменных. Вводим все ограничения и параметры поиска решения (см. рис. 4, 5).

Рис. 4. - Заполнение диалогового окна «Поиск решения» исходными данными

Рис. 5. - Параметры поиска решения

Этап 7. Решение задачи.

Устанавливаем флажок Линейная модель диалогового окна Параметры поиска решения, что обеспечивает применение симплекс-метода;

Щелкаем мышью на кнопке ОК – на экране вновь появится диалоговое окно Поиск решения;

Щелкаем мышью на кнопке Выполнить – в таблице появятся результаты решения и на экран будет выведено диалоговое окно Результаты поиска решения. Выделяем типы отчетов и нажимаем кнопку ОК (см. рис. 6).

Рис. 6. - Результаты поиска решения

На рис.7 представлено полученное решение задачи.

Рис. 7.  - Диалоговое окно Результаты поиска решения

Этап 8. Анализ оптимального решения.

Анализ оптимального решения выполняется на основании успешного решения задачи, когда на экране появляется диалоговое окно Результат поиска решения. Решение найдено (рис.6).

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

Отчет по результатам

Отчет см. рис.7 состоит из трех таблиц:

                  Таблица 1 приводит сведения о целевой функции.

                  В столбце «Исходно» приведены значения целевой функции до начала вычислений. В нашем случае она равна 0 и результат равный 2692 в столбце «Результат».

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

                  Таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.

Рис. 8. - Отчёт по результатам

Для Ограничений в графе «Формула» приведены зависимости, которые были введены в диалоговое окно Поиск решения; в графе «Значение» приведены величины использованного ресурса; в графе «Разница» показано количество неиспользованного ресурса. Если ресурс используется полностью (то есть ресурс дефицитный), то в графе "Статус" соответствующее ограничение указывается как "связанное"; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается "не связан". В графе "Значение" приведены величины использованного ресурса

Для граничных условий (строки 24, 25, 26 на рис. 8) в графе "Разница" показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

Таблица 3 отчета по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Так, если на ресурс наложено ограничение типа ≥, то в графе "Разница" дается количество ресурса, на которое была превышена минимально необходимая норма.

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

Отчет по устойчивости (рис. 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 представлены результаты ввода.