Решение задачи линейного программирования - Курсовая работа

Экономические проблемы, возникающие перед специалистами, в большинстве своем сложные. Они зависят от множества различных, иногда противоречащих друг другу факторов, изменяются с течением времени и влияют на другие проблемы и процессы. Математическая модель отражает проблему в абстрактной форме и позволяет учесть большое число разнообразных характеристик, от которых эта проблема зависит. Анализ и расчет математической модели позволяют выбрать оптимальные решения поставленной задачи и обосновать этот выбор. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что ее переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства.Была предложена следующая простая модель сельскохозяйственного производства на Нарвских островах для внешнего рынка. Имеются три основные культуры, растущие в этом климате, и выращиваться они могут на одном из двух типов пахотных земель. Разные типы культур по-разному растут на разных землях, и подсчитано, что чистый урожай культуры i с земли типа j составляет Rij. Для одного акра культуры i, выращенной на земле типа j, требуется Wij м3 воды в год. Чтобы получить урожаи 1,2,3 с каждых 10 акров земли, для выполнения различных работ по выращиванию культур в течение 1 года требуется, соответственно, 2, 1 и 3 человека.Процесс построения математической модели для решения поставленной задачи можно начать с ответов на три следующие вопроса: 1. Отвечая на поставленные вопросы сформулируем суть проблемы - необходимо определить, какие культуры, в каком количестве и на каких землях необходимо выращивать, чтобы получить максимальный урожай. Введем обозначение переменных: х1 - количество планируемого выращивания 1-й культуры на землях типа I; Учитывая, что чистый урожай культуры i с земли типа j составляет Rij, то можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х1, х2, х3, х4, х5, х6, которые обеспечат максимальный урожай: Величины х1, х2, х3, х4, х5 и х6 нельзя выбирать произвольно, так как необходимо учесть ограничения на количество акров пригодных в настоящее время земель типа I и типа II. Ограничения на количество акров пригодных в настоящее время земель типа I и типа II можно записать следующим образом: При решении рассматриваемой задачи должны быть учтены ограничения на дополнительное орошение.Общей задачей линейного программирования (ОЗЛП) называют задачу: Максимизировать (минимизировать) функцию Моделируемая система характеризуется наличием нескольких видов «производственной деятельности» , для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы Расход i-го ресурса на единицу продукта j-го вида производственной деятельности равен aij. Цель построения модели состоит в определении уровней (объемов производства) каждого вида производственной деятельности xj, при которых оптимизируется (максимизируется или минимизируется) общий результат производственной деятельности системы в целом без нарушения ограничений, накладываемых на использование ресурсов. Оптимальным решением (или оптимальным планом) задачи ЛП называется решение системы ограничений (2.2), при котором линейная функция (2.1) принимает оптимальное значение. Пусть некоторая производственная единица (цех, завод, фирма и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров) Пj, Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.).Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Линейный характер построенной модели определяет с формальных позиций то, что все входящие в нее функции (ограничения и целевая функция) линейны. Для привидения системы ограничений неравенств к каноническому виду, необходимо в системе ограничений выделить единичный базис. При таких ограничения вводят дополнительные переменные с коэффициентом « 1», образующие единичный базис.Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица 3.1). Индексная строка позволяет нам судить об оптимальности плана: При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки. Для перехода ко второй итерации отыскиваем ключевой (главный) столбец и ключевую (главную) строку. Ключевым столбцом является тот, в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax. Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца [1, с.Вычислим значения Di по строкам как частное от

Содержание

Введение

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

2. Построение математической модели

3. Выбор, обоснование и описание метода решений рассматриваемой задачи

3.1 Общая задача линейного программирования

3.2 Выбор метода реализации модели

3.3 Алгоритм симплекс-метода

4. Решение задачи симплекс-методом

4.1 Решение прямой задачи линейного программирования симплексным методом

4.2 Составление и решение двойственной задачи

5. Анализ модели на чувствительность

Заключение

Список библиографических источников

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

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

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

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

- выбрать и описать метод реализации модели;

- решить прямую и двойственную задачи выбранным методом;

- произвести анализ модели на чувствительность.

Объектом исследования является сельскохозяйственное производство на Нарвских островах для внешнего рынка.

Предметом исследования являются данные о землях и культурах, которые выращиваются в этом климате.