Найти оптимальное решение прилагаемой задачи симплекс методом

ID работы - 608834
математика (контрольная работа)
количество страниц - 17
год сдачи - 2012

---

СОДЕРЖАНИЕ:

---

План:
1. Теоретическая часть 3
А) Задача линейного программирования на оптимизацию производственных процессов 3
Б) Методы решения задач линейного программирования 5
В) Транспортные задачи линейного программирования 6
2. Практическая часть 8
Оптимизация производственной программы предприятия или фирмы 8
А) Построить экономико-математическую модель планирования производства 8
Б) Найти оптимальное решение прилагаемой задачи симплекс методом 8
В) Составить и решить любым методом двойственную задачу 11
Г) Выполнить полный анализ чувствительности и устойчивости оптимального решения 11
Д) Рассчитать альтернативные варианты плана 13
Модель выбора 13
А) Составить дескриптивную (описательную) задачу о назначениях 14
Б) Построение экономико-математической модели 14
В) Записать постановку задачи 15
Г) Решить задачу 16
Д) Провести анализ полученного решения 16
Список литературы 17

---

ВВЕДЕНИЕ:

---

1. Теоретическая часть
А) Задача линейного программирования на оптимизацию производственных процессов
Принцип оптимальности и задача оптимального программирования в общей постановке звучит следующим образом:
Пусть предприятие из m видов ресурсов производит n видов продукции. Предположим, что для производства одной единицы j-го вида продукции расходуется aij единиц i-го вида ресурса, т.е. аij – норма расхода j-го ресурса на производство j-й продукции. Матрица А = (аij), составленная из норм расхода, так и называется матрицей норм расхода или технологической.
J-й столбец Аj полностью описывает расход ресурсов на производство одной единицы j-й продукции, а i-я строка описывает расход i-го ресурса на производство единицы каждой продукции или при единичной интенсивности каждой технологии.
Пусть сj есть величина удельной прибыли от реализации одной единицы j-й продукции. Эти удельные прибыли образуют вектор-строку С = (с1,…,сn). Тогда произведение С • Х = с1x1 + … + сnхn представляет собой величину прибыли, полученной при реализации Х = (х1,…,хn) единиц произведенной продукции (X – вектор-столбец, но по типографским соображениям иногда будем его записывать в виде вектора-строки). Обозначим эту прибыль Р(Х).
Пусть bi обозначает количество единиц i-го ресурса, запасенного на складе. Запишем эти величины запасов в виде В = (b1,…,bm) (В – также вектор-столбец). Тогда матрично-векторное неравенство АХ В означает необходимость учитывать ограниченность запасов ресурсов при рассмотрении планов производства. Если это неравенство выполняется, значит, для плана Х хватит имеющихся запасов ресурсов В и такой план является реальным или, как говорят, допустимым.
Рассмотрим следующую задачу оптимального планирования: найти такой план производства Х = (х1,…,хn), который бы был допустимым и обеспечивал наибольшую прибыль из всех допустимых планов. Эту задачу записывают так:
c1x1 + … + cnxn max,
a11x1 + … + a1nxn b1,
…
am1x1 + … + amnxn bm,
x1, …, xn 0,
или в матрично-векторной форме:
P(X) = C • X max,
AX B,
X 0.
(Ограничение X 0 учитывает содержательный смысл задачи, 0 – это нулевой вектор-столбец такой же размерности, что и X.) Обозначим множество всех планов, удовлетворяющих условиям:
a11x1 + … + a1nxn b1,
…
am1x1 + … + amnxn bm,
x1, …, xn 0,
или в матрично-векторной форме:
AX B,
X 0.
через D и назовем это множество допустимым (множеством допустимых планов), тогда указанную выше задачу линейного программирования (ЛП) можно сформулировать так: найти максимум функции Р(Х) = С • Х на множестве D допустимых планов. В матрично-векторной форме:
P(X) max,
X D.
Б) Методы решения задач линейного программирования
На практике приходится решать такие задачи линейного программирования, в которых много видов ресурсов (иногда сотни и тысячи) и много видов продукции (тоже такого порядка). Для решения подобных задач линейного программирования разработаны мощные математические методы и такие задачи сегодня решают только на компьютере. Самый известный алгоритм решения задач линейного программирования – это так называемый симплекс-ме¬тод, придуманный американским математиком Дж. Данцигом
Теоретической основой линейного программирования и симплекс-метода являются две теоремы:
1-я основная теорема линейного программирования. Задача линейного программирования имеет оптимальное решение тогда и только тогда, когда целевая функция ограничена на допустимом множестве в направлении экстремума.
Эта теорема не имеет места в более общих ситуациях. Например, функция у = 1/х ограничена снизу 0 на множестве (0, +?), но точки минимума на этом множестве у нее нет.
2-я основная теорема линейного программирования. Если экстремум целевой функции в задаче линейного программирования достигается, то он достигается в некоторой угловой точке допустимого множества.
Точное определение угловой точки не просто, но нам оно не нужно. Нужно только понять, что допустимое множество – то, на котором ищется экстремум, – это многранное тело, и вершины этого многогранного тела и есть угловые точки. Таких угловых точек – конечное число.
Сам симплекс-метод представляет собой направленный перебор угловых точек допустимого множества в сторону приближения к искомой точке экстремума. При анализе очередной угловой точки симплекс-метод указывает:
1) что эта точка – искомая точка экстремума;
2) что целевая функция задачи не ограничена в направлении экстремума и, значит, точки экстремума нет, тем самым задача не имеет решения;
3) какую угловую точку далее надо исследовать (при этом значение целевой функции в следующей угловой точке будет ближе к экстремуму).
Решение задачи линейного программирования с помощью симплекс-метода оформляется в виде специальных таблиц, называемых симплексными таблицами.
В определенных случая когда одно или несколько ограничений задается разностью переменных для решения практической задачи необходимо использовать метод искусственного базиса (М-метод) применяется в тех случаях, когда затруднительно найти первоначальный опорный план канонической формы задачи линейного программирования.
М-метод заключается в применении правила симплекс-метода к так называемой М-задаче. Она получается из исходной добавлением к левой части векторного уравнения таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных, линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М – достат

---

СПИСОК ЛИТЕРТУРЫ:

---

Список литературы
1. Абчук В.А. Экономико-математические методы – СПб., Союз, 1999
2. Замков О.О., Толстопятенко А.В., Черемых Ю.Н. Математические методы в экономике – М., ДиС, 1998
3. Малыхин В.И. Математика в экономике – М., ИНФРА-М, 2001
4. Эдоусс М., Стенсфилд Р. Методы принятия решений – М., Аудит, ЮНИТИ, 1997
Цена: 1000.00руб.