Курсовая работа: Решение задач о планировании перевозок

Данная курсовая работа предусматривает разработку экономико-математической модели задачи и решение задачи линейного программирования с использованием математических методов. Машинная реализация решаемой задачи осуществляется на ПЭВМ Pentium 4 под управлением OCWindows с использованием табличного процессора MicrosoftExcel.

Курсовая работа выполнена на листах.

Введение

Человек всегда моделировал: мысленно, физически, знаками, в том числе математически.

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

Успешная реализация достижений Научно-технического прогресса в нашей стране тесным образом связана с использованием математических методов и средств вычислительной техники при решении задач из различных областей человеческой деятельности. Исключительно важное значение приобретает использование указанных методов и средств и при решении экономических задач. Одним из необходимых условий дальнейшего развития экономической науки является применение точных методов количественного анализа, широкое использование математики. В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение в экономических исследовании и планировании. Особенно успешно развиваются методы оптимального планирования, которые и составляют сущность математического программирования. Проникновение математики в экономику, планирование и управление является определяющей особенностью современного этапа научно-технической революции. Составными частями математического программирования являются линейное, нелинейное и динамическое программирование. Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок, позволяющего минимизировать суммарный километраж, дана в работе А.Н. Толстого (1930 г.).

Этот процесс в последнее время шел интенсивно во всем мире. Появились целые школы математических методов в США, Франции, ФРГ, Англии и некоторых других странах, что вызвано объективными причинами. Расширение масштабов производства, развитие, кооперации, усложнение межхозяйственных связей и другие, качественные Количественные изменения в экономике привели к резкому увеличению числа управленческих решений, из которых надо выбрать лучшее. Методам линейного программирования посвящено много работ зарубежных и прежде всего американских ученых. Основной метод решения задач линейного программирования симплексный метод был опубликован в 1949 г. Данцигом. Дальнейшее развитие метода линейного и нелинейного программирования получили в работах Форда, Фалкерсона, Куна, Лемке, Госса, Чарнеса и др. В настоящее время методы линейного программирования развиваются главным образом в направлении выявления конкретных экономических задач, к решению которых оно может быть применено, а также по пути создания более удобных алгоритмов для решения задач на ЭВМ.

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

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

Постановка задачи

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

Ежедневное производство кирпича и потребность в нем указаны в таблице. В нем уже указана цена перевозки 1000 шт. кирпича с каждого из заводов каждого из объектов.

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

Характеристика вида программирования

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

математические модели очень большого числа экономических задач линейны относительно искомых переменных;

· эти типы задач в настоящее время наиболее изучены;

· для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

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

· некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Итак, Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы. Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений , которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений

· переменных (аргументов функции F ), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F , максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F , называется оптимальным планом задачи. Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП ) является выбор из множества допустимых планов наиболее выгодного (оптимального).В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ) , которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G :

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что

а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n

б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

· максимум или минимум целевой функции (критерий оптимальности);

· систему ограничений в форме линейных уравнений и неравенств;

· требование неотрицательности переменных.

Пример

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--