Курсовая работа: Методы решения задач линейного программирования с n-переменными
Курсовая работа: Методы решения задач линейного программирования с n-переменными
Министерство образования Республики Башкортостан
Стерлитамакский колледж строительства, экономики и права
КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ
«МАТЕМАТИЧЕСКИЕ МЕТОДЫ»
На тему: «Методы решения задач линейного программирования с n-переменными»
Выполнила: студентка гр. ПО-32
Талант Людмила Владимировна
Руководитель: Шалаева И.И.
г. Стерлитамак 2011
Содержание
Введение
Постановка основной задачи линейного программирования с n-переменными
Графический метод решения задач линейного программирования с n-переменными
Симплекс-метод решения задач линейного программирования с n-переменными
Математическая модель
Решение задачи в MS Excel
Решение задачи графическим методом
Решение задачи симплекс-методом
Аналитическая часть
Заключение
Список используемой литературы
Введение
Цель курсового проектирования — закрепить, систематизировать и комплексно обобщить знания по методам решения задач линейного программирования с n-переменными и развить навыки самостоятельной творческой работы; научиться практически применять полученные теоретические знания при решении конкретных вопросов; научиться пользоваться справочной литературой, стандартами, другими нормативно-техническими документами и средствами вычислительной техники. Объектом исследования будет конкретная задача, описанная ниже. В курсовой работе рассмотрим графический и симплекс-методы линейного программирования с n-переменными и найдем оптимальный план производства товаров, обеспечивающего предприятию максимальную прибыль.
Постановка основной задачи линейного программирования с n-переменными
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Называется программированием условно, не имея ничего общего с написанием машинного кода.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.
В линейном программировании изучаются свойства решений линейных систем уравнений и неравенств с n-переменными следующего вида:
(1.1)
В системах (1.1) коэффициенты aij и правые части bi являются числами.
Системы (1.1) называются системами ограничений.
Точка в n - мерном пространстве
(1.2)
удовлетворяющая системе (1.1), называется допустимым планом.
Основной задачей линейного программирования (ОЗЛП) с n-переменными называется задача о нахождении такого допустимого плана, который доставляет максимум функции
(1.3)
Функция Z, определенная соотношением (1.3), называется функцией прибыли (целевой функцией).
Допустимый план, доставляющий максимум функции (1.3), называется оптимальным планом.
Иногда в задачах линейного программирования вместо нахождения максимума функции прибыли Z требуется найти минимум функции затрат
(1.4)
В этом случае с помощью введения функции Z = − R задача о нахождении минимума функции затрат R сводится к задаче о нахождении максимума функции прибыли Z.
Графический метод решения задач линейного программирования с n-переменными
Задача линейного программирования для n-переменных
Рассмотрим задачу формирования плана производства.
Некоторое предприятие может выпускать определённый набор продукции. Нормы затрат известны. Требуется построить производственный план, учитывающий ограниченность ресурсов.
Формализация
n - число различных видов продукции.
m - число различных ресурсов.
Таблица №1
| Вид продукции | Норма расхода ресурса на единицу продукции | Прибыль на единицу продукции | ||||||
| 1 | 2 | 3 | ... | i | … | m | ||
| 1 |
a11 |
c21 |
a31 |
… |
ai1 |
… |
am1 |
c1 |
| 2 |
a12 |
c22 |
a32 |
… |
ai2 |
… |
am2 |
c2 |
| 3 |
a13 |
c23 |
a33 |
… |
ai3 |
… |
am3 |
c3 |
| … | … | … | … | … | … | … | … | … |
| j |
a1j |
c2j |
a3j |
… |
aij |
… |
amj |
cj |
| … | … | … | … | … | … | … | … | … |
| n |
a1n |
a2n |
a3n |
… |
ain |
… |
amn |
cn |
| Ограничения на ресурсы |
b1 |
b2 |
b3 |
… |
bi |
… |
bm |
|
