Решение задач о планировании перевозок (стр. 1 из 3)
Федеральное агентство по образованию
ФГОУ СПО «Донской техникум информатики и вычислительной техники»
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОЙ РАБОТЕ
По дисциплине: Математические методы
Тема проекта: «Решение задач о планировании перевозок»
Аннотация
Данная курсовая работа предусматривает разработку экономико-математической модели задачи и решение задачи линейного программирования с использованием математических методов. Машинная реализация решаемой задачи осуществляется на ПЭВМ Pentium 4 под управлением OCWindows с использованием табличного процессора MicrosoftExcel.
Курсовая работа выполнена на листах.
Введение
Человек всегда моделировал: мысленно, физически, знаками, в том числе математически.
Развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования и хозяйственного руководства. В этих условиях только научный подход к руководству экономической жизнью общества позволит обеспечить высокие темпы развития народного хозяйства.
Успешная реализация достижений Научно-технического прогресса в нашей стране тесным образом связана с использованием математических методов и средств вычислительной техники при решении задач из различных областей человеческой деятельности. Исключительно важное значение приобретает использование указанных методов и средств и при решении экономических задач. Одним из необходимых условий дальнейшего развития экономической науки является применение точных методов количественного анализа, широкое использование математики. В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение в экономических исследовании и планировании. Особенно успешно развиваются методы оптимального планирования, которые и составляют сущность математического программирования. Проникновение математики в экономику, планирование и управление является определяющей особенностью современного этапа научно-технической революции. Составными частями математического программирования являются линейное, нелинейное и динамическое программирование. Впервые постановка задачи линейного программирования в виде предложения по составлению оптимального плана перевозок, позволяющего минимизировать суммарный километраж, дана в работе А.Н. Толстого (1930 г.).
Этот процесс в последнее время шел интенсивно во всем мире. Появились целые школы математических методов в США, Франции, ФРГ, Англии и некоторых других странах, что вызвано объективными причинами. Расширение масштабов производства, развитие, кооперации, усложнение межхозяйственных связей и другие, качественные Количественные изменения в экономике привели к резкому увеличению числа управленческих решений, из которых надо выбрать лучшее. Методам линейного программирования посвящено много работ зарубежных и прежде всего американских ученых. Основной метод решения задач линейного программирования симплексный метод был опубликован в 1949 г. Данцигом. Дальнейшее развитие метода линейного и нелинейного программирования получили в работах Форда, Фалкерсона, Куна, Лемке, Госса, Чарнеса и др. В настоящее время методы линейного программирования развиваются главным образом в направлении выявления конкретных экономических задач, к решению которых оно может быть применено, а также по пути создания более удобных алгоритмов для решения задач на ЭВМ.
В ряде задач линейного и нелинейного программирования экономический процесс зависит от времени , от нескольких периодов (этапов). При решении таких задач (они называются многоэтапными) необходимо учитывать поэтапное развитие процесса. Это, например, задача распределения ресурсов между предприятиями по годам планируемого периода. Такие многоэтапные задачи относятся к задачам динамического программирования.
Чрезвычайно велико значение экономико-математических методов при принятии плановых заданий. Увеличение «Цены ошибки» в планировании потребовало решения планово-экономических задач на более высоком уровне их научного обоснования, т.е. прежде всего такими методами, которые давали бы наилучший (оптимальный) или рациональный результат.
Постановка задачи
Изготовленный на 5 кирпичных заводах кирпич поступает на место строящихся объектов.
Ежедневное производство кирпича и потребность в нем указаны в таблице. В нем уже указана цена перевозки 1000 шт. кирпича с каждого из заводов каждого из объектов.
Составить план перевозок, согласно которому обеспечиваются потребности в кирпиче на каждом из строящихся объектов при минимальной общей стоимости перевозок.
Характеристика вида программирования
Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.
Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:
математические модели очень большого числа экономических задач линейны относительно искомых переменных;
· эти типы задач в настоящее время наиболее изучены;
· для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;
· многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;
· некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Итак, Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы. Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений
· переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи. Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).В общей постановке задача линейного программирования выглядит следующим образом:
Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных f(x) = f (х1 , х2 , … хn ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:
В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х1 , х2 , … хn
б) область G определяется системой линейных равенств или неравенств.
Математическая модель любой задачи линейного программирования включает в себя:
· максимум или минимум целевой функции (критерий оптимальности);
· систему ограничений в форме линейных уравнений и неравенств;
· требование неотрицательности переменных.
Пример
В других ситуациях могут возникать задачи с большим количеством переменных, в систему ограничений которых, кроме неравенств, могут входить и равенства. Потому в наиболее общей форме задачу линейного программирования формулируют следующим образом:
(2.4) 
(2.5) 
(2.6)Коэффициенты ai,j, bi, cj, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0).
Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными.
Выше описанная задача линейного программирования (ЗЛП) представлена в общей форме, но одна и та же (ЗЛП) может быть сформулирована в различных эквивалентных формах. Наиболее важными формами задачи линейного программирования являются каноническая и стандартная.
В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, ..., хn являются неотрицательными: