Курсовая работа: Методы решения задач линейного программирования с 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

aij - объём i-того ресурса, который расходуется на производство одной единицы j-того вида продукции i=1..m, j=1..n.

xj - объем (количество единиц) j-того вида продукции в производственном плане предприятия (j от 1 до n).

Необходимо определить нормы выпуска каждого вида продукции, чтобы прибыль от её реализации была максимальной.

Построение экономико-математической модели

Прибыль обозначим F, тогда F=c1x1+c2x2+...+cnxng max

Составим ограничения для первого ресурса:

а11 - объем первого ресурса, который расходуется на производство одной единицы первого вида продукции;

а11x1 - объём первого ресурса, который требуется на изготовление x1 единиц первого вида продукции;

а12x2 - объём первого ресурса, который требуется на изготовление x2 единиц второго вида продукции;

а1nxn - объём первого ресурса, который требуется на изготовление xn единиц n-ого вида продукции;

а11x1+a12x2+...+a1nxn - объём первого ресурса, который требуется на изготовление продукции, следовательно, мы имеем следующее ограничение:

а11x1+а12+...+а1nxn<=b1

Аналогично для остальных ресурсов:

а21x1+а22+...+а2nxn<=b2

а31x1+а32+...+а3nxn<=b3

...

аm1x1+аm2+...+amnxn<=bm

Кроме того, количество выпущенной продукции не может быть отрицательной, следовательно, x1>= 0, x2>=0, ...,xn>=0.

Таким образом, получаем следующую экономико-математическую модель задачи линейного программирования:

(2.1)

Задачу линейного программирования для N (любое целое число) переменных можно представить в следующем виде:

Решения, удовлетворяющие системе ограничений условий задачи и требованиям неотрицательности, называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) целевой функции, — оптимальными .

С помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если N и M связаны соотношением N – M = 2.

Действительно, пусть поставлена задача линейного программирования.

Найти максимальное значение линейной функции

Z = c1х1+c2х2+... +cNxN

при ограничениях

a11x1 + a22x2 + ... + a1NХN = b1

a21x1 + a22x2 + ... + a2NХN = b2

. . . . . . . . . . . . . . .

aМ1x1 + aМ2x2 + ... + aМNХN = bМ

xj ≥ 0 (j = 1, 2, ..., N)

где все уравнения линейно независимы и выполняется соотношение N - M = 2.

Используя метод Жордана-Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х1, х2, ..., хM, а свободными — два последних: хМ+1, и хN, т. е. система ограничений приняла вид:

x1 + a1,М+1xМ+1 + a1NХN = b1

x2 + a2,М+1xМ+1 + a2NХN = b2

. . . . . . . . . . . .

xМ + aМ, М+1x2 + aМNХN = bМ

xj ≥ 0 (j = 1, 2, ..., N)

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные — неотрицательные: хj ≥ 0 (j = 1, 2, ..., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств.

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

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Страницы: 1, 2