86282 (612710)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Негосударственное среднее профессиональное образовательное учреждение «ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»

курсовая РАБОТА

по дисциплине Математические методы

Тема: Линейное программирование

Выполнил(а) студент(ка) курса, группы ПО-27 ЗС

Якушева Ольга Сергеевна

фамилия имя отчество

Руководитель работы Груздева Елена Юрьевна

ученая степень, звание, фамилия и инициалы

Содержание

Введение

Теоретическая часть

Математическое решение задачи

Заключение

Список использованной литературы

Приложение №1 (Excel)

Приложение №2 (Pascal)

Введение

Математическое программирование – область прикладной математики, объединяющая различные мат.методы и дисциплины.

Методы:

1. Математическое программирование.

2. Дифференциальные и разностные уравнения.

3. Теория игр.

4. Теория решений и т.д.

Классические задачи исследования операций:

• Задачи диеты (задача о рационе).

• Задача замены (динамическое программирование).

• Задача коммивояжера (динамическое программирование).

• Распределительные задачи.

• Задача о назначениях.

• Задача о размещении складов.

• Задача о раскрое (линейное программирование).

• Задача поиска.

• Теория расписаний (метод дискретного программирования).

• Управление запасами (линейное программирование).

• Задачи массового обслуживания.

Методы математического программирования:

1. Линейного программирование.

2. Не линейное программирование.

3. Динамическое программирование.

4. Алгоритмы на графах.

5. Система массового обслуживания (СМО).

6. Методы прогнозирования.

7. Имитационное прогнозирование.

8. Теория игр.

9. Теория принятия решений.

Теоретическая часть

Рассмотрим один из основных методов – линейное программирование.

Линейное программирование (далее ЛП) – задачи, в которых критерий оптимальности задается в виде линейной формы от входящих в него переменных, на эти переменные накладываются ограничения в виде линейных уравнений или линейных неравенств.

Основные задачи ЛП:

• Задача оптимизации межотраслевых потоков.

• Транспортные задачи.

• Подробнее поговорим про задачу об оптимальном выпуске продукции.

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

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

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

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

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

Для решения задач ЛП используют графический метод и симплекс-метод.

Математическое решение задачи

В общем виде задачу линейного программирования можно представить следующим образом:

Алгоритмы симплекса-метода позволяют также установить, является ли задача ЛП разрешимой.

Рассмотрим задачу линейного программирования симплекс методом. Предприятие располагает ресурсами сырья, рабочей силой и оборудованием, необходимым для производства любого из трех видов производимых товаров 1, 2, 3. Затраты ресурсов на изготовление единицы данного вида товаров; прибыль, получаемая от реализации единицы товара, а также запасы ресурсов указаны в таблице.

Определить какой ассортимент товара надо выпускать, чтобы прибыль была максимальной.

Обозначим Товар 1 как х₁, Товар 2 – х₂, Товар 3 – х₃.

Z=10х1+8х2+6х3

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

Математическая модель должна быть в канонической форме, т.е. все ограничения в виде неравенств.

4 x₁ + 8x₂ + 4x₃ ≤ 120

6x₁ + 2x₂ + 3x₃ ≤ 160

2x₁ + 2x₂ + 4x₃ ≤ 400

Введем новые переменные x₄, x₅, x₆.

4 x₁ + 8x₂ + 4x₃ + x₄ ≤ 120

6x₁ + 2x₂ + 3x₃ + x₅ ≤ 160

2x₁ + 2x₂ + 4x₃ +x₆ ≤ 400

Находим исходные опорные решения и проверяем на оптимальность, для этого заполняем симплексную таблицу.

Ключевой элемент

I опорное решение.

x₁=0, x₂=0, x₃=0, x₄=120, x₅=160, x₆=400, Z=0.

Если решение не оптимально, строим вторую симплекс-таблицу.

Находим ключевой элемент: выбираем столбец с наибольшей по модулю отрицательной оценкой, для этого столбца находим b_i/x_ij и выбираем минимальное значение, т.е. выбираем строку, на пересечении выбранного столбца и строки определяется ключевой элемент;

Ключевой элемент находится на пересечении столбца х₁ и строки х₅, т.е. меняем их местами. Свободные переменные x₅, x₂, x₃; базисные переменные x₁, x₄, x₆.

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

Получаем новое опорное решение и проверяем его на оптимальность,

Ключевой

элемент

II опорное решение.

x₁=26,67, x₂=0, x₃=0, x₄=13,33, x₅=0, x₆=346,67, Z=266,67.

Данное решение не является оптимальным, т.к. в последней строке симплекс-таблицы находится отрицательное число – строим третью симплекс-таблицу.

Ключевой элемент находится на пересечении столбца х₂ и строки х₄, т.е. меняем их местами. Свободные переменные x₄, x₃, x₅; базисные переменные x₂, x₁, x₆.

III опорное решение.

x1=26, x2=2, x3=0, x4=0, x5=0, x6=344, Z=276.

Третье опорное решение является оптимальным, так как последняя строка симплекс таблицы содержит только положительные элементы.

Подставляем в линейную функцию Z = 10*26 + 8*2 + 6*0 = 276.

Оптимально производить Товар 1 – в количестве 26, Товар 2 – в количестве 2 и Товар 3 – в количестве 0.

Запрограммируем в MS Office Excel (Приложение№1) и в Pascal (Приложение№2). Данные и условия сформированы ранее.

Заключение

Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 г. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 60-х гг. Фиако (Fiacco) и МакКормиком (McCormick). Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 г. советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным.

Список использованной литературы

• А.И.Ларионов, Т.И.Юрченко “Экономико-математические методы в планировании: Учебник – М.: Высш.школа, 1984

• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006.

• В.И. Бодров, Т.Я. Лазарева, Ю.Ф. Мартемьянов «Математические методы принятия решений», Издательство ТГТУ, 2004

• Вершик А. М. «O Л. В. Канторовиче и линейном программировании»

• Большакова И. В., Кураленко М. В. «Линейное программирование. Учебно-методическое пособие к контрольной работе».

Приложение №2

PROGRAM SIMPLEX_METOD;

USES CRT;

LABEL ZN,ST,ELL,_END;

TYPE MAS=ARRAY[1..30] OF REAL;

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов курсовой работы