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

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