Методы решения задач линейного программирования с n-переменными (стр. 1 из 4)

Министерство образования Республики Башкортостан

Стерлитамакский колледж строительства, экономики и права

КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ

«МАТЕМАТИЧЕСКИЕ МЕТОДЫ»

На тему: «Методы решения задач линейного программирования с n-переменными»

Выполнила: студентка гр. ПО-32

Талант Людмила Владимировна

Руководитель: Шалаева И.И.

г. Стерлитамак 2011

Содержание

Введение

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

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

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

Математическая модель

Решение задачи в MS Excel

Решение задачи графическим методом

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

Аналитическая часть

Заключение

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

Введение

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

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

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

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Называется программированием условно, не имея ничего общего с написанием машинного кода.

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

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

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

В линейном программировании изучаются свойства решений линейныхсистем уравнений и неравенств с n-переменными следующего вида:

(1.1)

В системах (1.1) коэффициенты a_ij и правые части b_i являются числами.

Системы (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

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

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

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

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

Прибыль обозначим F, тогда F=c₁x₁+c₂x₂+...+c_nx_ng max

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

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

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

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

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

а₁₁x₁+a₁₂x₂+...+a_1nx_n - объём первого ресурса, который требуется на изготовление продукции, следовательно, мы имеем следующее ограничение:

а₁₁x₁+а₁₂+...+а_1nx_n<=b₁

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

а₂₁x1+а₂₂+...+а_2nx_n<=b₂

а₃₁x1+а₃₂+...+а_3nx_n<=b₃

...

а_m1x₁+а_m2+...+a_mnx_n<=b_m

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

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

(2.1)

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

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

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

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

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

Z = c₁х₁+c₂х₂+... +c_Nx_N

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

a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

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

a_М1x₁ + a_М2x₂ + ... + a_МNХ_N = b_М

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

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

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

x₁ + a_1,М+1x_М+1 + a_1NХ_N = b₁

x₂ + a_2,М+1x_М+1 + a_2NХ_N = b₂