Реферат на тему Метод «квадратов» при улучшении опорного плана транспортной задачи.

Содержание:

Введение 3
Классификация задач математического программирования. 5
Линейное программирование 8
Транспортная задача (Т-задача) 10
Постановка задачи 10
Транспортная таблица 13
Составление первого опорного плана 14
Метод северо-западного угла 14
Метод минимального элемента 14
Аппроксимация Фогеля 15
Метод двойного предпочтения 15
Проверка опорного плана на вырожденность 16
Метод квадратов 16
Заключение 22
Список использованных источников 24
Приложение. Методы выбора опорного плана 25

Введение:

Задачи, решение которых необходимо отыскать в повседневной жизни, в большинстве своем являются многовариантными. Среди огромного количества возможных вариантов необходимо отыскать наилучшие в каком-либо смысле с учетом ограничения природных, экономических и технологических возможностей. В связи с этим возникла необходимость применения для анализа и синтеза экономических ситуаций и систем математических методов и современной вычислительной техники. Эти методы объединяются под общим названием – математическое программирование.
Суть математического программирования составляют теория и методы решения задач нахождения экстремумов функций на множествах при наличии линейных и нелинейных ограничений (равенства и неравенства).
В реальной жизни задачи, с которыми сталкивается человек, настолько сложны, что при их анализе просто необходимо отказаться от ряда несущественных, второстепенных признаков и работать с новым «образом», в котором учитываются только существенные стороны явлений. Этот образ называют моделью.
В управлении экономическими процессами наибольшее значение имеют математические, прежде всего экономико-математические, модели. Математическая модель – это записанная математическими символами абстракция реального явления. Она устанавливает соотношения между совокупностью переменных и параметрами управления явлением [1].
Модель в общем случае объединяет в себе управляемые компоненты (их обычно обозначают через вектор Х), неуправляемые компоненты (это обычно помехи или условия, в которых работает система – Y) и параметры системы (некоторые постоянные величины, заданные, например, технологическим процессом – С). Эти компоненты связываются между собой одним или несколькими критериями качества и функциями ограничений.
Задачи математического программирования классифицируются по различным признакам. Соотнесение поставленной задачи какому-нибудь классу помогает определиться с методами ее решения.
Таким образом, актуальность исследования обуславливается стремлением разработчиков или лиц, принимающих решения, получить наилучший (оптимальный) вариант решения задачи.
Объектом исследования являются модели и методы математического программирования.
Предметом исследования является разновидность задачи линейного программирования – транспортная задача.
Задачами исследования являются:
• Анализ задач линейного программирования;
• Анализ постановки транспортной задачи;
• Анализ методов получения начального опорного плана транспортной задачи;
• Использование метода квадратов для улучшения решения транспортной задачи.

Заключение:

Математическое программирование, являясь кибернетической наукой, играет важную роль в управлении широкого спектра объектов. Использование моделей и методов математического программирования можно проследить практически во всех областях жизни и деятельности человека (и не только!). Например, доказано, что пчелы ежедневно решают сложнейшую задачу математического программирования – «опылить» максимальное количество растений при минимальном пути. Что уж говорить о человеке, который всегда мечтает получить максимальную выгоду при минимизации вложений! Вот, вопросами оптимизации и занимается математическое программирование.
В практической деятельности существует бесконечное множество задач, которые нужно решать оптимальным образом. Однако, кибернетика, как наука об общих закономерностях, позволяет соотнести каждую конкретную задачу некоторому классу задач оптимизации. Это позволило разработать ограниченное количество подходов и методов оптимизации для практически бесконечного множества запросов пользователей, что и было рассмотрено в данной работе.
Большая часть задач управления сводится к задачам линейного программирования. Одной из разновидностей задач линейного программирования является транспортная задача. Эта задача, несмотря на такое «конкретное» название (транспортная!), является по сути распределительной задачей. А к этому классу можно отнести не только перевозки грузов, но и много чего еще…
Целью данной работы было рассмотрение метода квадратов для улучшения планов транспортной задачи. Однако, без знания теоретических предпосылок, модели транспортной задачи и методов получения опорного плана обойтись было нельзя. Поэтому в первой части работы были рассмотрены теоретические вопросы, связанные с задачами математического программирования и постановкой задачи линейного программирования.
Далее более детально были рассмотрены вопросы моделирования транспортной задачи и получения первого опорного плана.
В заключение, был рассмотрен один из методов решения транспортной задачи – метод квадратов.
Таким образом, можно сказать, что задачи, поставленные перед исследованием, решены и цель достигнута.

Фрагмент текста работы:

Классификация задач математического программирования.

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

1б). задачи отыскания условного экстремума. Постановка задачи такова

2. Неклассические задачи математического программирования. В этих задачах обычно присутствует требование неотрицательности всех или части компонент вектора Х:

Неклассические задачи делятся на два подкласса: специальные и неспециальные. К первым относятся такие, для которых разработаны специальные (непрямые) методы решения в зависимости от свойств функций.
Перечислим основные типы специальных неклассических задач математического программирования.
3. Задачи линейного программирования (ЗЛП). Общую постановку ЗЛП можно представить в следующем виде

где сj, bi, aij — заданные постоянные величины.
Все задачи, которые можно привести к такому виду,) являются задачами линейного программирования.
4. Задачи квадратичного программирования (ЗКП). Общая постановка ЗКП имеет вид

где сj, dkj, bi, aij — заданные постоянные величины.
5. Задачи выпуклого программирования. В этих задачах целевая функция и функции ограничений выпуклы.
6. Задачи сепарабельного программирования. Постановка задачи имеет вид

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

,
,

где сk, cik, — некоторые константы.
8. Задачи дискретного программирования. К ним можно отнести такие задачи математического программирования, в которых переменных принимают значения некоторого дискретного, предварительно определенного численного множества.
9. Задачи стохастического программирования. В них, как правило, можно определить только некоторое распределение соответствующих значений целевой функции или сам оптимальный план подчиняется статистическому распределению.