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

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

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