Размещено на http://www.allbest.ru/

сОДЕРЖАНИЕ

Введение

1.Общая задача линейного программирования (ЛП)

1.1 Постановка задачи

1.2 Графический метод решения задач ЛП

1.3 Симплекс-метод решения задач ЛП

2. Примеры решения задач ЛП

Заключение

Список использованных источников

Введение

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

В данном курсовом проекте будет рассмотрено два метода решения задач линейного программирования: графический и симплекс-метод.

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно. Поэтому для решения, в том числе этой проблемы, в конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач - симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

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

Для достижения поставленной цели решаются задачи: постановки задачи линейного программирования, графического метода решения задач ЛП, симплекс-метода решения задач ЛП.

1. Общая задача линейного программирования

1.1 Постановка задачи

Задача линейного программирования (ЛП) ассоциируется с задачей распределительного типа, в которой требуется распределить ограниченные ресурсы по нескольким видам деятельности. Интерпретация задачи ЛП в этом случае состоит в следующем. Моделируемая ЭИС характеризуется наличием нескольких видов деятельности j (j = 1, …, n), для осуществления которых требуются имеющиеся в ограниченном количестве различные ресурсы bi, (i = 1, …, m). Интенсивность расходования каждого из ресурсов на каждый из видов деятельности ЭИС известна и равна aij. Результативность или ценность каждого j-го вида деятельности ЭИС характеризуется величиной cj. Цель построения модели заключается в определении уровней каждого вида деятельности ЭИС xj, при которых оптимизируется общий результат деятельности ЭИС в целом при выполнении ограничений, накладываемых на использование ресурсов, т. е. cj xj ? bi, i = 1, …, m. Структура целевой функции y(u) отражает вклад каждого вида деятельности ЭИС в общий результат. При максимизации сj представляет собой “полезность” j-го вида деятельности (ущерб, наносимый конкуренту по бизнесу, предотвращенный ущерб), а в случае минимизации характеризует затраты (потери собственные, расход материальных средств). Линейность модели выявляется или принимается в качестве допущения на этапе формализации задачи. Линейность предполагает наличие двух свойств -- пропорциональности и аддитивности, присущих как целевой функции, так и ограничениям. Пропорциональность целевой функции означает, что вклад каждой управляемой переменной в целевую функцию пропорционален величине этой переменной. Аддитивность же целевой функции заключается в том, что целевая функция представляет собой сумму вкладов от различных управляемых переменных. Пропорциональность ограничений проявляется в том, что общий объем потребляемых ресурсов прямо пропорционален величинам управляемых переменных. Аддитивность ограничений состоит в том, что величина ресурса должна представлять собой сумму расходов по видам деятельности, каждое слагаемое которой пропорционально величине соответствующей управляемой переменной. В формализованном виде задачу ЛП можно представить следующим образом:

Определить

где , (1.1)

Условие неотрицательности, накладываемое на переменные xj, означает, что ни одному виду деятельности ЭИС не может быть приписан отрицательный уровень. Ограничение типа ? нельзя рассматривать как ограничение в буквальном смысле этого слова. Наличие такого неравенства предполагает необходимость обязательного выполнения каких-либо планов, заданий, нормативов.

Математическая формулировка задачи ЛП выглядит следующим образом: необходимо определить значения управляемых переменных xj, доставляющих экстремум целевой функции y(u) на всем множестве стратегий U = {u} и удовлетворяющих всем имеющимся в задаче ограничениям. Этой формулировкой задача ЛП считается поставленной математически, что позволяет осуществлять поиск ее оптимального решения известными математическими методами.

Формальную постановку задачи ЛП (1.1) для удобства можно представить в упрощенном виде:

определить max (или min) W(x) = при ограничениях:

cj xj (?, = или ?) bi, i = 1, …, m; xj ? 0,

где W(x) -- новое обозначение ЦФ, т. е. W(x) = y(u) = f(x).

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

1.2 Графический метод решения задач ЛП

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

(c, x) > max

Ax ? b,

где x = (x1, x2), c = (c1, c2), b = (b1, b2, ..., bm), A - матрица размера (m Ч 2).

Очевидно, что при данной постановке задачи допустимое множество X в плоскости (x1, x2) представляет собой многоугольник (не обязательно замкнутый), образованный пересечением полуплоскостей H+aibi (где ai - i-я строка матрицы A, i = 1, ..., m), соответствующих ограничениям вида ai1x1 + ai2x2 ? bi в исходной задаче. Линии уровня функции f(x) = (c, x) (линией уровня называется множество {xR: f(x)= б, б R}) образуют семейство параллельных прямых Hcб. При этом grad f(x) = c, т.е. градиент целевой функции всюду одинаков и является нормалью каждой из данных полуплоскостей. В соответствии с предыдущим, поиск решения задачи сводится к нахождению максимального числа б* среди всех таких б, что полуплоскость Hcб имеет непустое пересечение с X. При этом X - множество решений задачи. При неограниченном решений может и не быть, т.е. HcбX Ш при всех б> .

Из графического представления ясна характерная особенность задачи ЛП (при c ? 0): если ее решение существует, то оно достигается обязательно на границе. Отметим, что в рассмотренной задаче ЛП на максимум при поиске б* происходит как бы перемещение прямой Hcб в направлении вектора c. Если же решается задача ЛП на минимум, и, следовательно, ищется минимальное б*, удовлетворяющее указанным требованиям, то Hcб перемещается в направлении, противоположном вектору c.

Пример 1.2.1 Пусть дана задача ЛП

2x + y > max

-x + y ? 2,

x + 2y ? 7,

4x - 3y ? 6,

x ? 0, y ? 0.

Геометрическая интерпретация задачи приведена на рисунке 1.



Рисунок 1

Ясно, что решением является точка пересечения прямых

x + 2y = 7 и 4x - 3y = 6, т.е. (x*, y*) = (3, 2).

Очевидно, что графический метод решения задач ЛП применим лишь в случае малой размерности пространства. В общем случае для решения задач линейного программирования в пространстве произвольной размерности широко используется симплекс-метод.

задача линейный программирование симплекс

1.3 Симплекс-метод решения задач ЛП

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

Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (x1, ..., xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (x1, ..., xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1.

Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:

Симплекс-таблица

	1	x1	x2	...	xm	xm+1	...	xn
x0	A0,0	0	0	...	0	A0,m+1	...	A0,n
x1	A1,0	1	0	...	0	A1,m+1	...	A1,n
x2	A2,0	0	1	...	0	A2,m+1	...	A2,n
...	...	...	...	...	...	...	...	...
xm	Am,0	0	0	...	1	Am,m+1	...	Am,n

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (x1, ..., xm). Сверху от таблицы приведен набор всех переменных задачи, где xm+1, ..., xn - свободные переменные задачи.

На начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (x1, ..., xm) ?0 при xj = 0 (j = m+1, ..., n), следовательно, все свободные члены ограничений Ai,0 ?0 (i = 1, ..., m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные Ai,0, определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A0,j? 0 (j = 1, ..., m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования.

Если симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все Ai,0 ? 0 и A0,j ? 0, то решение оптимально.

Действительно, поскольку допустимыми являются лишь неотрицательные значения управляемых параметров, то изменение целевой функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A0,j < 0, то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменной xj с отрицательным коэффициентом A0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи. Теоретически можно использовать любую свободную переменную xj с A0,j < 0, но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A0,p < 0 из всех отрицательных A0,j <0:

A0,p = min A0,j < 0.

Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A0,p < 0, называется разрешающим столбцом. Свободная переменная разрешающего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную xq, которая раньше других обращается в нуль при увеличении переменной xp ведущего столбца.

Её индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, минимизирующий отношение (Ai,0 / Ai,p):

Aq,0 Ai,0

------ = min ------ , i = 1,...,m.

Aq,p i Ai,p

Элемент Aq,p называется разрешающим элементом, cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, разрешающей строкой. Переменная ведущей строки xq заменяется в базисе переменной разрешающего столбца xp и становится свободной переменной с значением 0, в то время как новая базисная переменная xp достигнет максимально возможного значения, равного: max xp = ( Aq,0 / Aq,p).

После указанного взаимообразного обмена переменными xp и xq между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств):

· умножение уравнения E1(x) = 0 на константу K1 и замена уравнения E1(x) = 0 уравнением K1*E1(x) = 0;

· сложение уравнений E1(x) = 0 и E2(x) = 0 c последующей заменой уравнения E2(x) = 0 уравнением E1(x) + E2(x) = 0.

Исключения Гаусса позволяют привести систему уравнений к диагональной форме относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента Aq,p, стали нулевыми, а ведущий элемент стал равным единице:

Ai,p = 0, если i не равно q

и

Ai,p = 1, если i = q.

Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение.

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

Алгоритм решения задач симплекс - методом

1) Поставленная описательная задача переводится в математическую форму (целевая функция и ограничения).

2) Полученное математическое описание приводят к канонической форме.

3) Каноническую форму приводят к матричному виду.

4) Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m - число строк в матрице. Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного равного единице.

5) Если матрица не является правильной, то ее нужно сделать таковой с помощью искусственного базиса. Для этого в матрицу нужно дописать столько базисных столбцов, чтобы их общее количество вместе с уже имеющимися базисными столбцами составляло m. После этого переходят к пункту 6. Если искусственный столбец выходит из базиса, то его удаляют из матрицы. Если удалены все искусственные столбцы, то получено первое допустимое решение. Если искусственные элементы не удается вывести из базиса, то система не имеет решений.

6) Строят последовательность матриц. Нужно определить разрешающий столбец, разрешающую строку и разрешающий элемент. Элемент, соответствующий разрешающей строке, удаляется из базиса, а на его место ставят элемент, соответствующий разрешающему столбцу. Составляют уравнение пересчета матрицы, выполняют пересчет, а затем проверяют его результаты на оптимальность. Если решение не оптимально, то заново ограничивают ведущий элемент, ведущую строку и ведущий столбец.

Признаком оптимальности решения является наличие в векторе решений только отрицательных или нулевых коэффициентов при всех ограничениях.

Ответ записывается следующим образом:

- Каждому отрицательному коэффициенту в векторе решения ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе.

- Для каждого нулевого коэффициента в векторе решения ставится в соответствие значение свободного члена из строки, содержащей единицу в столбце данной переменной.

- Фиктивные переменные в ответе не учитываются.

Разрешающим может быть назначен любой столбец, удовлетворяющий одному из условий:

1) Первый столбец, содержащий положительный элемент в векторе решений.

2) Столбец, содержащий наибольший положительный элемент в строке решения.

3) Если столбец удовлетворяет условию max(Cj min bj/aij) при решении на max, и min(Cj min bj/aij) при решении задач на min.

Cj - коэффициент целевой функции в столбце j, aij - коэффициент в столбце j и строке i.

2. Примеры решения задач различными методами ЛП

Задача 1

Предприятие выпускает пиломатериалы и фанеру, используя при этом еловые и пихтовые лесоматериалы. Для изготовления 2,5 м3 пиломатериалов необходимо израсходовать 2,5 м3 еловых и 7,5 м3 пихтовых лесоматериалов. Для приготовления 100 м3 фанеры требуется 5 м3 еловых, 10 м3 пихтовых. Запасы предприятия составляют 80 м3 еловых и 180 м3 лесоматериалы. Найти оптимальный план производства предприятия, если по условиям поставки необходимо произвести не менее 10 м3 лесоматериалов и 1200 м3 фанеры. Доход с 1 м3 пиломатериалов составляет 16 у.е., со 100 м2 - 60 у.е.

Решение

Введем следующие обозначения:x1- площадь фанеры(100 м2); x2- площадь пиломатериалов (м3).

Доход от реализации фанеры составляет 16x1, а от реализации пиломатериалов 60x2, т.е. необходимо максимизировать целевую функцию:

F(x1,x2)=16x1+60x2>max

Ограничения задачи имеют вид:

5x1+x2?80, (1)

10x1+7,5x2?180, (2)

x2?10, (3)

x1?12. (4)

Первое ограничение по еловым пиломатериалам 5x1+x2?80. Прямая 5x1+x2=80 проходит через точки (0,80) и (16,0).

Второе ограничение по пихтовым пиломатериалам 10x1+7,5x2?180. Прямая 10x1+7,5x2=180 проходит через точки (0,18) и (60,0). Третье ограничение попиломатериалам и четвертое по фанере x2?12. Решением этой системы является полуплоскость выше (3) прямой и левее (1). На рисунке 2 заштрихована область допустимых значений.

Рисунок 2 - Область допустимых значений-

Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.

=(16,60)

Что бы построить этот вектор, нужно соединить точку (16;60) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента.

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

5x1+x2=80,

x2=10

Отсюда легко записать решение исходной ЗЛП: max f(x) = 800 и достигается при x1=14 и x2=10.

Рисунок 3. Максимум целевой функции достигается в точке (14,10).

Таким образом, для оптимального плана производства предприятию необходимо изготовить 10 м3 пиломатериалов и 14 м2 фанеры.

Задача 2

Завод производит два вида продукции: велосипеды и мотоциклы. При этом цех по сборке велосипедов имеет мощность 100 тыс. штук в год, цех по сборке мотоциклов 30 тыс. Одна группа механических цехов завода может производить детали либо для 120 тыс. велосипедов, либо для 40 тыс. мотоциклов, либо другую комбинацию деталей, ограниченную этими данными.Другая группа механических цехов может выпускать детали либо для 80 тыс. велосипедов, либо для 60 тыс. мотоциклов, либо любую допустимую их комбинацию. В результате реализации каждой тысячи велосипедов завод получает прибыль в 2 тыс. рублей, а с каждой тыс. мотоциклов- 3 тыс. рублей.

Найти такое сочетание выпусков продукции, которое дает наибольшую сумму прибыли.

Решение

В качестве переменных задачи возьмем количество велосипедов и мотоциклов, выпускаемых заводом в год (в тыс. штук): x1 и x2.

Учитывая возможности сборочных цехов, необходимо потребовать, чтобы

x1?100, (1)

x2?30 (2)

Проанализируем возможности цехов. При этом необходимо учитывать, что при выпуске обоих видов продукции должно выполняться условие пропорциональности количества продукции данного вида доле производственной мощности , занятой ее выпуском. Если предусматривается производство 1000 велосипедов, то доля занятых производственных мощностей механических цехов первой группы составит 1/120 суммы всех мощностей, принимаемых в данном случае за единицу; на выпуск же x1 тыс. велосипедов потребуется занять (1/120) x1 всей мощности. Аналогично для производства x2 тыс. мотоциклов необходимо выделить (1/40) x2 всей мощности. Так что для реализации плана (x1,x2) потребуется предусмотреть

((1/120)x1+(1/40)x2) мощности механических цехов первой группы. Но в производственном процессе может быть использована не более чем вся наличная производственная мощность рассматриваемых цехов, следовательно

(1/120)x1+(1/40)x2?1, (3)

Точно также получаем ограничения по производственной мощности механических цехов второй группы:

(1/80)x1+(1/60)x2?1. (4)

По смыслу задачи:

x1?0, (5)

x2?0 (6)

Любой план (x1,x2), удовлетворяющий ограничениям (1)-(6), будет допустимым и дает предприятию прибыль (в тыс. руб): f(x1,x2)=2x1+3x2

Соотношения образуют математическую модель задачи:

f(x1,x2)=2x1+3x2>max

x1?100, (1)

x2?30, (2)

(1/120)x1+(1/40)x2?1, (3)

(1/80)x1+(1/60)x2?1. (4)

x1?0, x2?0

Решим данную задачу графическим методом. Для этого на графике отметим координаты прямой (1/120)x1+(1/40)x2=1, она проходит через точки (0,120) и (40,0) и координаты прямой (1/80)x1+(1/60)x2=1, которая проходит через точки (0,80) и (60,0).Также отметим на графике x1=100 и x2=30 (рисунок 3).



Рисунок 3

Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е. =(2;3)

Что бы построить этот вектор, нужно соединить точку (2;3) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента.

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

(1/120)x1+(1/40)x2=1

(1/80)x1+(1/60)x2=1.

Из первого уравнения выразим x1 и подставим его во второе уравнение:

x1+3 x2=120,

x1=120-3 x2.



Таким образом, при выпуске 24 тыс. мотоциклов и 48 тыс. велосипе -дов будет получена наибольшая сумма прибыли.

Задача 3

Решить задачу линейного программирования симплекс-методом.

Дано:

F(x)=-2x1+x2>max,

x1+x2?4,

-x1+2x2?2,

x1+2x2?10

Приведем задачу к каноническому виду путем добавления искусственных переменных:

F(x)=-2x1+x2>max,

x1+x2-x3=4,

-x1+2x2+x4= 2,

x1+2x2+x5= 10

1)Построим симплекс-таблицу:

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	-1	0	0	4
0	-1	2	0	1	0	2
0	1	2	0	0	1	10
F	2	-1	0	0	0	0

2)По F-строке выбираем наибольший по величине отрицательный элемент у нас он равен -1, соответствующий этому элементу столбец является разрешающим.

3)Находим отношения членов к соответствующим элементам разрешающего столбца.

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	-1	0	0	4	4
0	-1	2	0	1	0	2	1
0	1	2	0	0	1	10	5
F	2	-1	0	0	0	0	0

4)Среди отношений выбираем минимальное т.е. в данном случае оно равно 1. Строка, которая соответствует минимальному отношению является разрешающей.

Следовательно, элемент находящийся на пересечении разрешающей строки и разрешающего столбца является разрешающим т.е. равен 2.

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	-1	0	0	4	4
0	-1	2	0	1	0	2	1
0	1	2	0	0	1	10	5
F	2	-1	0	0	0	0	0

После выполнения симплекс преобразования переходим к новой таблице.

5)Элементы разрешающей строки предыдущей таблицы делим на разрешающий элемент и записываем на прежнее место.

Остальные элементы таблицы записываем по формуле:

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
0	1,5	0	-1	-1	0	3
x2	-0,5	1	0	0,5	0	1
0	2	0	0	-1	0	8
F	1,5	0	0	1	0	1

Таким образом, оптимальное решение найдено, следовательно, x2=1, а все остальные элементы равны 0.

Задача 4

Компания производит полки для ванных комнат двух размеров - А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В - 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В - 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В - 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

Решение

Составим математическую модель задачи. Пусть x1 - количество полок вида А, x2- количество полок вида В, которые производятся в неделю. Прибыль от продажи такого количества полок составит 3x1+4x2, прибыль требуется максимизировать. Выпишем ограничения задачи .x1+x2?550- в неделю на рынке может быть реализовано до 550 полок.

Затраты материала: 2x1+3x2?1200

Затраты машинного времени:12x1+30x2?9600

Таким образом, приходим к задаче линейного программирования.

F=3x1+4x2>max,

x1+x2?550,

2x1+3x2?1200,

12x1+30x2?9600,

x1?0,x2?0.

Решим ее симплекс-методом. Приведем задачу к каноническому виду путем добавления искусственных переменных

F=3x1+4x2>max,

x1+x2+x3=550,

2x1+3x2+x4=1200,

12x1+30x2+x5=9600,

xi?0,i=1,2,3,4,5

Составим симплекс-таблицу

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
0	1	1	1	0	0	550	550
0	2	3	0	1	0	1200	400
0	12	30	0	0	1	9600	320
F	-3	-4	0	0	0	0	0

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

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
0	0,6	0	1	0	-0,033	230	383,3
0	0,8	0	0	1	-0,1	240	300
x2	0,4	1	0	0	0,033	320	800
F	-1,4	0	0	0	0,13	1280

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
0	0	0	1	-0,75	0,042	50	1190
x1	1	0	0	1,25	-0,125	300	2400
x2	0	1	0	-0,5	0,083	200	2409
F	0	0	0	1,75	-0,042	1700

базисные переменные	коэф. переменных	свободные члены	отношения
	x1	x2	x3	x4	x5
x5	0	0	24	-18	1	1200
x1	1	0	3	-1	0	450
x2	0	1	-2	1	0	100
F	0	0	1	1	0	1750

В последнем плане строка F не содержит отрицательных значений, план x1=450,x2=100 оптимален, целевая функция принимает значение 1750.

Таким образом, чтобы получить максимальную прибыль предприятию необходимо производить 450 полок вида A и 100 полок вида В, при этом прибыль составит 1750 ден. ед., а останется неиспользованными 1200 минут машинного времени.

Заключение

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

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

Таким образом, использование симплекс-метода в задачах линейного программирования является наиболее оптимальным.

Список использованных источников

1) Солодовников, А.С. Математика в экономике. Часть 1. Линейная алгебра, аналитическая геометрия и линейное программирование / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра.-М.: Издательство «Финансы и статистика»,2011.

2) Струченков В.И. Методы оптимизации в прикладных задачах / В.И.Струченков.-М.: Издательство «Солон-Пресс»,2009.

3) Юденков, А.В. математическое программирование в экономике : Учебное пособие / А.В.Юденков, М.И.Дли, В.В. Круглов.- М.: издательство «Финансы и статистика»,2010.

4) Агишева Д.К., Зотова С.А., Матвеева Т.А., Светличная В.Б. Линейное программирование (учебное пособие) // Успехи современного естествознания. - 2010.

5) Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике(учебное пособие): Издательство «Финансы и статистика», 2012.

6) Карасёв А.Н. Математические методы в экономике/ А.Н. Карасёв, Н.Ш. Кремер, Т.Н. Савельева, 2009

7) Минько Э.В. Методы прогонозирования и исследования операций: Учебное пособие/ Э.В. Минько, А.Э. Минько.-М.:Издптнльство «Инфа-м», 2014

8) Балдин К.В. Математическое программирование/ К.В. Балдин.-М.: Издательство «Дашков и К», 2009

9) Корнев В.В. Прикладные методы оптимизации/ В.В. Корнев, В.В. Курдюмов, В.С. Рыхлов, 2004.

Размещено на Allbest.ru