Рефетека.ру / Информатика и програм-ие

Курсовая работа: Решение задач линейного программирования

Введение


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

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

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

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

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

Задачи работы обусловлены ее целью:

Во-первых, раскрыть теоретическое содержание данной темы.

Во-вторых, сформулировать и найти оптимальное решение задач с помощью средств MS Excel.


Задачи линейного программирования


1. С помощью средств Excel найти решение задачи линейного программирования


L(Х) = 14хРешение задач линейного программирования -9х2 -х4 +6,4х5 —> min;

Решение задач линейного программирования0,9 хРешение задач линейного программирования + 10х2 -28х4 +5х5 Решение задач линейного программирования 245,

0,8 хРешение задач линейного программирования+ 1,7х2 -0,2х3 -0,5х4 =9,

6 хРешение задач линейного программирования + 4х3 - 7х4 + 6,3х5 Решение задач линейного программирования 54,

8 хРешение задач линейного программирования+6,2х2 -4,8х4 +2,9х5 Решение задач линейного программирования17,

xРешение задач линейного программированияРешение задач линейного программирования 0, (j =Решение задач линейного программированияРешение задач линейного программирования).


2. Мебельный комбинат выпускает книжные полки А из натурального дерева со стеклом, полки В1 из полированной ДСП (древесно-стружечной плиты) без стекла и полки В2 из полированной ДСП со стеклом. Габариты полок А, В1 и В2 следующие: длина 1100 (d) мм, ширина 250 (w) мм, высота 300 (h) мм/ Размер листа ДСП 2x3 м.

Решение задач линейного программированияРешение задач линейного программированияРешение задач линейного программированияРешение задач линейного программированияРешение задач линейного программированияРешение задач линейного программированияРешение задач линейного программированияРешение задач линейного программированияРешение задач линейного программирования


h

w

d

Габариты полок, выпускаемых мебельным комбинатом


При изготовлении полок А выполняются следующие работы: столярные, покрытие лаком, сушка, резка стекла, упаковка. Все операции, производимые в ходе столярных работ и упаковки, выполняются вручную. Полки В1 и В2 поставляются в торговую сеть в разобранном виде. За исключением операции упаковки, все остальные операции (производство комплектующих полки, резка стекла) при изготовлении полок В1 и В2, выполняются на специализированных автоматах.

Трудоемкость столярных работ по выпуску одной полки А составляет 3,2 (Тр1) ч. Производительность автомата, покрывающего полки А лаком - 2 (Пр1) полок в час, автомата, режущего стекло - 180 (Пр2) стекол в час. Сменный фонд времени автомата для покрытия лаком – 7,4 (ФВ1) ч, автомата для резки стекла - 7,1 (ФВ2) ч. Сушка полок, покрытых лаком, происходит в течение суток в специальных сушилках, вмещающих 55 (VI) полок. На упаковку полки А требуется 6 (Тр2) минуты. В производстве полок заняты 27 (Р1) столяров и 7 (Р2) упаковщиков.

Производительность автомата, производящего комплектующие полок В, и В2, равна 7 (Прз) полки в час, а его сменный фонд времени равен 7,8 (ФВ3) ч, трудоемкость упаковочных работ составляет 9 (Тр3) мин для полки В1 и 10 (Тр4) мин для полки В2.

От поставщиков комбинат получает в месяц 415 (Z1) листов полированной ДСП, 215 (Z2) листов ДВП (древесно-волокнистой плиты), а также 240 (Z3) листов стекла. Из каждого листа ДВП можно выкроить 6 (К1) задних стенок полок В1 и В2, а из каждого листа стекла - 13 (К2) стекол для полок А и В2.

Склад готовой продукции может разместить не более 370 (V2) полок и комплектов полок, причем ежедневно в торговую сеть вывозится в среднем 72(N) полок и комплектов. На начало текущего месяца на складе осталось 80 (Ост) полок, произведенных ранее. Себестоимость полки А равна 150 (С1) руб., полки В без стекла - 120 (С2) руб., со стеклом - 134 (Сз) руб.

Маркетинговые исследования показали, что доля продаж полок обоих видов со стеклом составляет не менее 43% (Д) в общем объеме продаж, а емкость рынка полок производимого типа составляет около 1100 (Vз) штук в месяц. Мебельный комбинат заключил договор на поставку заказчику 50 (З) полок типа В2 в текущем месяце.

Составьте план производства полок на текущий месяц. Известны цены реализации полок: полка А - 192 (Ц1) руб., полка В без стекла - 154 (Ц2) руб., полка В со стеклом - 147 (Ц3) руб.


D W H Тр1 Тр2 Тр3 Тр4 Р1 Р2 Пр1 Пр2 Пр3 ФВ1 ФВ2 ФВ3 Z1 Z2 Z3
1180 270 260 3,2 6 9 10 27 7 2 180 7 7,4 7,1 7,8 415 215 240


















K1 K2 V1 V2 V3 N ост Д З С1 С2 С3 Ц1 Ц2 Ц3


6 13 55 370 1100 72 80 43(A,B1) 5A,12B2 150 120 134 192 154 147



3 варианта раскроя ДСП, 8 ч в смене; работа в 1 смену; 22 рабочих дня в месяц.

3. На складах хранится мука, которую необходимо завезти в хлебопекарни. Номера складов и номера хлебопекарен даны в таблице 1. Текущие тарифы перевозки муки [руб./т], ежемесячные запасы муки [т/мес] на складах и потребности хлебопекарен в муке [т/мес] указаны в табл. 2.

При этом необходимо учитывать, что из-за ремонтных работ временно нет возможности перевозить муку с некоторых складов в некоторые хлебопекарни. В табл. 1это показано в графе "Запрет перевозки" в формате № склада х № хлебопекарни. Например, «2x3» обозначает, что нельзя перевозить муку со склада № 2 в хлебопекарню № 3.

Кроме того, необходимо учесть, что некоторые хлебопекарни имеют договоры на гарантированную поставку муки с определенных складов. В табл. 1 это показано в графе "Гарантированная поставка" в формате № склада х № хлебопекарни = объем поставки. Например, «1x4=40» обозначает, что между складом № 1 и магазином № 4 заключен договор на обязательную поставку 40 т муки.

Необходимо организовать поставки наилучшим образом, учитывая, что мука хранится и транспортируется в мешках весом по 50 кг.

Таблица 1

Номер склада, хлебопекарни, запрещенные или гарантированные поставки

№ Варианта № Складов № Хлебопекарен Запрет перевозки Гарантированная поставка, т/мес.
4 1,2, 3,4 3, 4, 5 3x3, 4x5 3x5=40

Таблица 2

Запасы, потребности и тарифы перевозок

Склады Хлебопекарни

1 2 3 4 5 Запас, т/мес.
1 400 600 800 200 200 80
2 300 100 500 600 500 70
3 500 200 100 600 300 60
4 300 700 200 400 900 55
5 200 500 800 200 400 65
Спрос, т/мес. 77,86 56,78 58.88 62,44 73,92


2. Теоретическая основа линейного программирования

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


Постановка практической задачи ЛП включает следующие основные этапы:

определение показателя эффективности, переменных задачи,

задание линейной целевой функции S(x), подлежащей минимизации или максимизации,

задание ограничений.

Приведем сейчас общую математическую формулировку основной задачи линейного программирования.

Дана система линейных уравнений с n неизвестными:

a11 x1 + a11 x2 + …… + a11 xn Решение задач линейного программирования=Решение задач линейного программирования b1 ,

a21 x1 + a22 x2 + …… + a2n xn Решение задач линейного программирования =Решение задач линейного программирования b2 ,

am1 x1 + am2 x2 + …… + amn xn Решение задач линейного программирования=Решение задач линейного программирования bm ,

и линейная функция

f = c1 x1 + c2 x2 +………+ cn xn (1.2)

Требуется найти такое неотрицательное решение системы

x1 ≥0, x2 ≥0, … … , xn ≥0 (1.3)

при котором функция f принимает наименьшее значение.

Уравнения (1.1) называют системой ограничений данной задачи; функцию f — целевой функцией (или линейной формой).


2.2.Методы решения задач линейного программирования


2.2.1. Симплекс – метод


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

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

X0 + A0,m+1*Xm+1 + ... + A0,n*Xn = A0,0


X1 + A1,m+1*Xm+1 + ... + A1,n*Xn = A1,0

.

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

.

Xi + Ai,m+1*Xm+1 + ... + Ai,n*Xn = Ai,0

.

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

.

Xm + Am,m+1*Xm+1 + ... + Am,n*Xn = Am,0

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

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


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 - свободные переменные задачи.

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

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


2.2.2. Геометрический метод


Применяется дя задач с двумя переменными. Метод решения состоит в следующем:

Решение задач линейного программированияНа плоскости Ох1х2 строятся прямые, которые задают соответствующие ограничения:

a11 x1 + a11 x2 + …… + a11 xn = b1 ,

a21 x1 + a22 x2 + …… + a2n xn = b2 ,

…………………………………………

am1 x1 + am2 x2 + …… + amn xn = bm .


Находим множество всех точек х1,х2, удовлетворяющим всем неравенствам. Такое множество называется областью допустимых решений. Строим вектор Решение задач линейного программирования и перемещаем линию уровня, который задается уравнением: с1х1+с2х2 = const в направлении вектора Решение задач линейного программированиядо последней точки пересечения с ОДР. Эта точка и дает решение задачи Lmax = значению L в этой точки


2.3. Двойственная задача.


Общая схема построения двойственной задачи.

Если задана общая задача ЛП:

Решение задач линейного программирования

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

Решение задач линейного программирования

то двойственной по отношению к ней называется общая задача ЛП:

Решение задач линейного программирования

где D* определяется системой уравнений и неравенств:

Решение задач линейного программирования

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

1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3. Матрица ограничений задачи А транспонируется.

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

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

Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей.

((D*)*, (f*)*)≡(D, f),

Основные теоремы:

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

Теорема 2 ( о дополняющей нежесткости). Для того чтобы план х* и у* являлись оптимальными решениями соответственно задач линейного программирования и двойственной к ним необходимо и достаточно, чтобы выполнялись следующие соотношения:

Решение задач линейного программирования

Решение задач линейного программирования

Теорема 3 (об оценках). Значение переменных Решение задач линейного программирования в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*)

Решение задач линейного программирования

2.4. Транспортная задача.


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

Имеется ряд пунктов производстваРешение задач линейного программированияс объемами производства в единицу времени (месяц, квартал), равными соответственноРешение задач линейного программированияи пункты потребленияРешение задач линейного программирования потребляющие за тот же промежуток времени соответственноРешение задач линейного программированияРешение задач линейного программирования продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех пунктах-поставщиках равна сумме объемов потребления на всех пунктах-получателях:

Решение задач линейного программирования

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

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

Решение задач линейного программирования

При этом каждый потребитель получает нужное количество продукта:

Решение задач линейного программирования

и каждый поставщик отгружает весь произведенный им продукт:

Решение задач линейного программирования

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

Рассмотрим таблицу.

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0), называют свободными, а ненулевые — занятыми (xi,j>0).



В1 В2 …… Вn Всего

C1,1 C1,2 …… C1,n а1
A1 C2,1 C2,2 …… C2,n а2
A2 …. …. …. ….
…. …. ….
Am Cm,1 Cm,2 …… Cm,n аm

b1 b2
bn

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

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

Производственно-транспортная задача

Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).

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

3. Решение задач


3.1. Решение задачи линейного программирования


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


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

Составим целевую функцию и зададим ограничения.

Пусть Х1, Х2, Х3, Х4, Х5 – неизвестные переменные

Целевая функция: L(Х) = 14 хРешение задач линейного программирования-9 х2 - х4+6,4 х5—> min;

Ограничения: g1: 0,9 хРешение задач линейного программирования + 10 х2-28х4 +5х5Решение задач линейного программирования 245,

g2: 0,8 хРешение задач линейного программирования+ 1,7х2 -0,2х3 -0,5х4 =9,

g3: 6 хРешение задач линейного программирования + 4х3 - 7х4 + 6,3х5 Решение задач линейного программирования 54,

g4: 8 хРешение задач линейного программирования+6,2х2 -4,8х4 +2,9х5 Решение задач линейного программирования17,

Решение задач линейного программирования


3.1.2.Ввод данных


1. Введем на рабочий лист Excel необходимые данные. В ячейке В5 запишем выражение целевой функции, а в ячейках В8:В11– левые части ограничений.

2.Командой Сервис, Поиск решения откройем диалоговое окно ІПоиск решенияІ (рис. 2) и заполним его данными. В поле Установить целевую ячейку введем адрес целевой функции $В$5, в поле Изменяя ячейки - адреса $B$3:$E$3. Переведите переключатель Равной в положение минимальному значению.

Чтобы ввести ограничения в окне ІПоиск решенияІ нажмем кнопку Добавить и на экране появится диалоговое окно ІДобавление ограниченияІ .

3. Начнем с первого ограничения. Установим курсор в поле Ссылка на ячейку и, выделяя на листе (рис.1) ячейку В8, введем ее адрес $B$8 в это поле.

Кнопкой-стрелкой откроем список и выберем в нем знак <=. В поле Ограничение установите курсор и, выделяя на листе ячейку D8, введем ее адрес $ D $8 в это поле и нажмем кнопку Добавить.

4. Повторим действия п.3 и введем остальные ограничения $В$9=$D$9, $В$10<=$D$10, $В$11>=$D$11, реализующие граничные условия. После ввода последнего ограничения $F$11<=$H$11 вместо кнопки Добавить нажмем кнопку ОК.

Таким образом, в окно ІПоиск решенияІ (рис. 2) будут введены ограничения.


3.1.3. Решение задачи


1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно ІПараметры поиска решенияІ (рис.4).

В этом окне оставьте неизменными установленные по умолчанию Максимальное время: 100 сек, выделяемое на поиск решения (возможно до 9 часов), Предельное число итераций: 100, Относительная погрешность: 0,000001, Допустимое отклонение: 5%, переключатели в положении линейная, прямые, Ньютона.

Установим флажок Линейная, чтобы обеспечить применение симплекс-метода, и нажмите кнопку ОК.

2. В окне ІПоиск решенияІ нажмите кнопку Выполнить. На экране появится диалоговое окно ІРезультаты поиска решенияІ (рис.5) с информацией «Решение найдено. Все ограничения и условия оптимизации выполнены», подтверждающей успешное решение задачи оптимального распределения ресурсов и количественные результаты (значения переменных, ограничений и целевой функции), приведенные на рис.6.

x1 = А3 = 0, x2 = В3 = 14,43, x3 =С3 = 39,93, x4 =D3 =15,10, x5 =Е3=0

При этом значение целевой функции:

L= В5 = -144,99.


3.1.4. Анализ оптимального решения


Анализ оптимального решения начинается после успешного решения задачи, когда на экране появляется диалоговое окно ІРезультаты поиска решенияІ. С его помощью можно подготовить три типа отчетов: по результатам (опция Результаты), по устойчивости (опция Устойчивость), по пределам (опция Пределы).

1. Подготовим отчет по результатам (рис.7).

Отчет состоит из трех таблиц.

В первой таблице (Целевая ячейка) приводятся сведения о целевой функции: исходное значение (в графе «Исходно») и оптимальный результат (в графе «Результат»).

Во второй таблице (Изменяемые ячейки) приводятся исходные (в графе «Исходно») и полученные в результате решения задачи (в графе «Результат») значения переменных x1, x2, x3, x4, x5.

Третья таблица (Ограничения) отображает результаты оптимального решения, касающиеся ограничений и граничных условий.

2. Щелчком на ярлычке Отчет по устойчивости откроем содержимое отчета на рабочем листе (рис. 8).

Отчет по устойчивости содержит две таблицы.

В первой таблице (Изменяемые ячейки) приводятся следующие значения переменных:

результаты решения задачи (графа «Результ. значение»);

нормированная стоимость, т.е. дополнительные двойственные переменные vj, Решение задач линейного программирования, которые показывают, насколько изменяется целевая функция при принудительном включении единицы этой продукции в оптимальное решение;

коэффициенты целевой функции (графа «Целевой коэффициент»);

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

Во второй таблице приводятся значения ограничений:

значения используемых (графа «Результ. Значение») и заданных (графа «Ограничение, правая часть») ресурсов;

теневая цена, т. е. двойственные оценки zi, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;

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

3. Отчёт по переделам (рис.9) показывает, в каких пределах может меняться выпуск продукции, вошедшей в оптимальное решение, при сохранении его структуры:

приводятся значения хi в оптимальном решении (графа «Значение»);

даются нижние и верхние пределы изменения хi и соответствующие значения целевой функции (в графах «Целевой результат»).


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


3.2.1. Построение модели


В данной задаче искомыми неизвестными являются количество полок каждого вида, которые будут произведены в текущем месяце. Таким образом, Х1 – количество полок А(шт./мес.); Х2 – количество полок В1(шт./мес.); Х3 – количество полок В2(шт./мес.).

Целевая функция: Прибыль определяется разностью между ценой и себестоимостью, тогда:

Решение задач линейного программирования L(х) = (192-150)х1+(154-120)х2+(147-134)х3 мах

Руб./шт.* шт./мес. =руб./мес.

Ограничения:

Ограничения по фонду времени ( с использованием трудоемкости работ)

3,2 х1Решение задач линейного программирования 27*8*1*22

ч/шт.* шт./мес. Решение задач линейного программированиячел.* ч/(чел.см.)*см./дн. * дн./мес.

ч/мес. Решение задач линейного программированияч/мес.

3,2 ч/шт. (Тр1) – это время, затрачиваемое на столярные работы при производстве одной полки типа А;

27 чел. (Р1) – это количество столяров;

8ч/(чел.*см) – количество часов работы 1 человека в течении смены;

1см./дн. – количество смен в одном рабочем дне;

22 дн./мес. – количество рабочих дней в месяце

Необходимо произвести проверку единиц измерения!

Аналогично – упаковочные работы:

6/60х1+9/60х2+10/60х3Решение задач линейного программирования 7,4*8*1*22

ч/мес. Решение задач линейного программирования ч/мес

7 чел. (Р2) – это количество упаковщиков

Ограничение по фонду времени на покрытие лаком полок типа А:

1/2*х1Решение задач линейного программирования 7,4*1*22

ч/шт.*шт./мес. Решение задач линейного программированияч/см.*см./дн.*дн./мес.

ч/мес. Решение задач линейного программирования ч/мес.

1/2 – коэффициент, показывающий количество часов, приходящихся на покрытие лаком одной полки типа А.

Автомат работает в смену 7,4 ч в смену (ФВ1).

Ограничение по фонду времени на резку стекла для полок типа А и В2:

2/180х1+2/180х3Решение задач линейного программирования 7,1*1*22

ч/шт.*шт./мес. Решение задач линейного программированияч/см.*см./дн.*дн./мес.

ч/мес. Решение задач линейного программирования ч/мес.


Ограничения по фонду времени на производство комплектующих полок типа В1 и В2:

1/7х2+1/7х3Решение задач линейного программирования7,8*1*22

ч/шт.*шт./мес. Решение задач линейного программированияч/см.*см./дн.*дн./мес.

ч/мес. Решение задач линейного программирования ч/мес.


Ограничения по запасу расходуемых в производстве материалов (по запасу используемых для производства полок деталей)..

Целесообразно ориентироваться не на количество листов ДСП, а на количество комплектов для полок, которые можно получить из имеющегося запаса ДСП. Поскольку листы ДСП можно раскраивает различными способами и получать при этом различное количество деталей и комплектов, то обозначим месячный запас комплектов в правой части как Yкомпл и рассмотрим способ его численного определения позже.

1х2+1х3Решение задач линейного программирования Yкомпл

Компл./шт.*шт./мес. Решение задач линейного программирования Компл./мес.

Компл./мес.Решение задач линейного программирования Компл./мес.

Аналогично составляем ограничения по запасу задних стенок из ДВП для полок В1, В2:

1х2+1х3Решение задач линейного программирования215*6

Задняя стенка/шт.*шт./мес. Решение задач линейного программированиялист ДВП/мес.*задняя стенка/лист ДВП

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

Где 215 – ежемесячный запас листов ДВП

6 – количество задних стенок полок из каждого листа ДВП.

Ограничения по запасу стекол для полок А и В2:

2х1+2х3Решение задач линейного программирования240*13

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

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

Где 240 – ежемесячный запас стекол

13 – количество стекол из каждого листа стекла.

Ограничения по емкости вспомогательных помещений и рынка.

Ограничение по количеству полок А, которые может вместить сушилка:

х1Решение задач линейного программирования 55*22

шт./мес. Решение задач линейного программированияшт./дн.*дн./мес.

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

где 55 – количество полок, которые могут быть просушены в течение месяца.

Ограничение на количество полок всех видов, которые может вместить склад готовой продукции:

х1+х2+х3Решение задач линейного программирования370-80+72*22

шт./мес. Решение задач линейного программированияшт./мес.-шт./мес.+шт./дн.*дн./мес.

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

Здесь учитывается, что общая емкость склада уменьшается на остаток полок, которые остались невывезенными с прошлого месяца. Кроме того, в течение месяца каждый день будет освобождаться по N мест для полок.

Ограничение по примерной емкости рынка:

х1+х2+х3Решение задач линейного программирования1100

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

1100 – емкость рынка по всем видам полок.

Ограничение по гарантированному заказу.

х1Решение задач линейного программирования5,

х3Решение задач линейного программирования12

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

Необходимо произвести как минимум 5 полок А и 12 полок В3.

Ограничения по соотношению объемов продаж различных товаров.

Процентное отношение количество полок А и В1 ко всему объему продаж:

(х1-5)+х2Решение задач линейного программирования0,43[(х1-5)+х2+(х3-12)]

0,57х1+0,57х2-0,43х3 - 2,31

Шт./мес. Решение задач линейного программированияшт./мес.

Определение количества комплектов для полок В1 и В2


3.2.2. Первый этап решения задачи


В зависимости от размеров листов ДСП и габаритов полок детали В1 и В2 можно выкроить различными способами. Рассмотрим 3 возможных варианта такого раскроя (рис.10).

Решение задач линейного программированияL(Y)=Yкомпл мах комппл./мес.

Согласно 1 варианту из одного листа ДСП для полок В1 и В2 можно выкроить 19 деталей верхней и нижней стенок, а также 9 деталей боковых стенок. По 2 варианту раскроя получаем 12 деталей верхней и нижней стенок и 36 деталей боковых стенок. По 3 варианту раскроя получаем 16 деталей верхней или нижней стенок и 18 деталей боковых стенок.

Обозначим количество листов ДСП, раскроенных в течение месяца : по 1-му варранту через у1(лист./мес.); по 2 варианту – у2(лист./мес.); по 3 варианту – у3(лист./мес.). Таким образом, наша цель – укомплектовка максимального количества полок – описывается целевой функцией:

Решение задач линейного программирования L(Y)=Yкомпл мах

Количество всех раскроенных листов ДСП не должно превышать 415, то есть ежемесячный запас их на складе:

у1+у2+у3Решение задач линейного программирования 415

лист./мес.

Количество верхних и нижних стенок, получаемых при раскрои:

19у1+12у2+16у3Решение задач линейного программирования 2Yкомпл

дет,мес. Решение задач линейного программированиядет./мес.

Ограничение, задающие нижнюю границу количества боковых стенок полок:

9у1+36у2+18у3Решение задач линейного программирования 2Yкомпл

дет,мес. Решение задач линейного программированиядет./мес.

Получаем модель задачи, позволяющую раскроить максимальное количество комплектов:

Решение задач линейного программирования L(Y)=Yкомпл мах

Решение задач линейного программирования у1+у2+у3Решение задач линейного программирования 415

19у1+12у2+16у3Решение задач линейного программирования 2Yкомпл

9у1+36у2+18у3Решение задач линейного программирования 2Yкомпл

у1,у2,у3,YкомплРешение задач линейного программирования0


Решим данную задачу с помощью функции Поиск решения в MS Excel. Для этого повторим все пункты выполнения работы 3.1.2 – 3.1.3 (рис.11).


3.2.3. Решение исходной одноиндексной задачи

Решив задачу для варианта 0 мы получил значение правой части ограничения Y = 3515 комплектов, после чего решаем исходную задачу, модель которой имеет следующий вид:

Решение задач линейного программирования L(х) = 42х1+34х2+13х3 мах

Решение задач линейного программирования 3,2х1Решение задач линейного программирования4752;

0,1х1+0,15х2+0,167х3Решение задач линейного программирования1232;

0,5х1Решение задач линейного программирования162,8;

0,011х1+0,011х3Решение задач линейного программирования156,2;

0,143х2+0,143х3Решение задач линейного программирования171,6;

х2+х3Решение задач линейного программирования3515;

х2+х3Решение задач линейного программирования1290;

2х1+2х3Решение задач линейного программирования3120;

х1Решение задач линейного программирования1210;

х1+х2+х3Решение задач линейного программирования1874;

х1+х2+х3Решение задач линейного программирования1100;

х1Решение задач линейного программирования5;

х3Решение задач линейного программирования12;

0,57х1+0.57х2+0,43х3Решение задач линейного программирования-2,31;

х1,х2,х3Решение задач линейного программирования0


Решим задачу с использованием функции Поиск решения в MS Excel аналогично пунктам 3.1.2-3.1.3.

В ячейку Е5 введем целевую функцию, в ячейки В6:В19 – ограничения, переменные будем изменять в ячейках В3:В5 (рис.12).

Решив задачу, получаем:

х1=326шт./мес., х2=762 шт./мес., х3 = 12 шт./мес.,

L(X) = 39753 руб./мес.,

т.е. в текущем месяце необходимо произвести 326 полок А, 762 полки В1, 12 полок В2. После реализации всех произведенных полок комбинат получит прибыль в размере 39753 рублей. Оформим отчеты аналогично п.3.1.4.

Отчет по результатам, состоящий из 3 таблиц:

Информация о целевой функции.

Информация о значениях переменных, полученных в результате решения задачи.

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

Анализ отчета показывает, что мы можем уменьшить фонд времени фонд времени по производству полок В на 60,86 ч и это никак не повлияет на оптимальное решение. Таким образом, мы снизим время работы автомата, производящего комплектующие полки В1 и В2.

Емкость сушилки может быть снижена до 326 полок.

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

Отчет по устойчивости

Проанализировав 2 таблицу, мы увидим, что целесообразно увеличить емкость рынка самое большое на 425,6 = 426 полок. Это приведет к новым оптимальным решениям, увеличивающим прибыль по сравнению с найденной. Дальнейшее увеличение емкости рынка сверх указанных пределов не будет больше улучшать решение. Из колонки «Теневая цена» видно, что каждая полка, которая будет размещена на рынке, принесет прибыль равную 34 руб..

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


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


3.3.1. Определение переменных


Обозначим через хij [меш.] количество мешков с мукой, которые будут перевезены с i-го склада в j-ю хлебопекарню.


3.3.2. Проверка сбалансированности задачи


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

из запаса третьего склада = 60-40= 20т/мес.;

из потребности в муке пятой хлебопекарни

b2 = 73,92-40 = 33,92 т/мес.

Согласно условию задачи мука хранится и перевозится в мешках по 50 кг, то есть единицами измерения переменных хij являются мешки муки. Но

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

первом складе равен 80 т-мес., или 80т/мес. / 0,050т./меш.= 1600 меш/мес, а потребность третьей хлебопекарни составляет 58,88т/мес, или 58,88т/мес / 0,050 т./меш.= 1178меш./мес. Округление при расчете потребностей надо проводить в большую сторону, иначе потребность в муке не будет удовлетворена полностью.

Для данной ТЗ имеет место соотношение

склады хлебопекарни

1600+1400+400+1100 < 1178+1249+679

4500меш./мес. 3106 меш./мес.

Ежемесячный суммарный запас муки на складах больше суммарной потребности хлебопекарен на 1394 мешков муки, откуда следует вывод: ТЗ не сбалансирована.


3.3.3. Построение сбалансированной транспортной матрицы


Сбалансированная транспортная матрица представлена в таблице 3. Стоимость перевозки муки должна быть отнесена к единице продукции, то есть к 1 мешку муки. Так, например, тариф перевозки из первого склада в третий магазин равен 800 руб./т • 0,050 т/меш. = 40 руб./меш.

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

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

Транспортная матрица задачи


Хлебопекарни Запас, мешки
Склады X3 Х4 Х5 Х6
С! 40 10 10

 50

1600
С2 25 30 25

 50

1400
С3

100

30 15

 50

400
С4 10 20

 100

 50

1100
Спрос, мешки 1178 1249 679 1394

Решение задач линейного программирования= 4500


3.3.4. Задание целевой функции


Формальная ЦФ, то есть суммарные затраты на все возможные перевозки муки, учитываемые в модели, задается следующим выражением:

L(X) = 40 х11+10х12 + 10х13 +50 х14 +

+25х21+30х22 +25х23+50 х24+

+ 100х31 + 30х32 +15х33 +50 х34+

Решение задач линейного программирования +10 х41+20 х42 +100 х43+50 х44 min (руб./мес)..


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

Задание ограничений:

х11+х12 + х13 + х14 =1600,

Решение задач линейного программирования х21+х22 +х23+ х24 =1400,

х31 + х32 +х33 + х34=400,

х41+ х42 + х43+ х44 =1100,

х11+ х21+ х31 + х41=1178,

х12+х22+ х32+ х42=1249,

х13+х23+х33+ х43=679,

х14+ х24+ х34+ х44 =1394,

хijРешение задач линейного программирования 0(Решение задач линейного программирования.

Решим задачу с помощью средств MS Excel. Аналогично пунктам 3.1.2-3.1.3-введем данные, целевую функцию в ячейку F3, ограничения - в ячейки С8:С15 (рис.16).

Стоимость фиктивных перевозок составит: 127410 руб.. Найдем стоимость необходимых перевозок: 127410-1400(сумма фиктивных расходов)= 126010 руб.

Из рис.13 мы также видим какое количество мешков муки из какого склада поступит на каждую хлебопекарню:

2х3 = 1178 мешка;

1х4 = 1027 мешка;

2х4 = 222 мешка;

1х5 = 573 мешка + гарантированная поставка 800 мешков;

4х5 = 106 мешков (перевозка запрещена).

Заключение


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

x1 = А3 = 0, x2 = В3 = 14,43, x3 =С3 = 39,93, x4 =D3 =15,10, x5 =Е3=0

Во втором решении, одноиндексной задачи линейного программирования, получаем итоговый ответ:

х1 = 326шт./мес., х2 = 762 шт./мес., х3 = 12 шт./мес.,

L(X) = 39753 руб./мес.,

В транспортной задаче, номер 3, стоимость необходимых перевозок составила 126010 руб.

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

Библиографический список


1. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева [текст]: «Математические методы в экономике», 1996. – 354 с.

2. Общий курс высшей математики для экономистов [Текст]: Учебник / под ред В.И. Ермакова.- М.: ИНФА - М. - 656 с. - (серия «высшее образование»).

3. Т.Л. Партыкина, И.И. Попов Математические методы [Текст]: учебник. - М.: ФОРУМ: ИНФА-М, 2005. - 464 с.: ил - (профессиональное образование).

4. Федосеев В.В. и др. Экономико-математические методы и прикладные модели: учебное пособие для ВУЗов. - М.: Юнити, 2002.

5. Лященко И.Н. Линейное и нелинейное программирования [Текст]: И.Н.Лященко, Е.А.Карагодова, Н.В.Черникова. - К.: «Высшая школа», 1992, 372 с.

6. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. - M.: Наука, 1989. - 382с.

7. Балашевич В.А. [Текст]: Основы математического программирования. Мн.: Выш. шк. 2002. - 173с.

8. Branch M.A., T.F. Coleman, Y. Li. [Текст]: A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems. SIAM Journal on Scientific Computing, Vol. 21, Number 1, pp. 1-23, 1999.

Похожие работы:

  1. Решение задачи линейного программирования ...
  2. • Решение задачи линейного программирования симплекс-методом
  3. • Решения задач линейного программирования ...
  4. • Решение транспортной задачи линейного ...
  5. • Использование линейного программирования для решения ...
  6. • Линейное программирование: постановка задач и графическое ...
  7. • Решение задач линейного программирования
  8. • Линейное программирование: решение задач графическим способом
  9. • Решение задач линейного программирования симплекс ...
  10. • Применение линейного программирования для решения ...
  11. • Решение задач линейного программирования симплекс ...
  12. • Линейное программирование как метод оптимизации
  13. • Линейное программирование
  14. • Решение оптимизационной задачи линейного программирования
  15. • Решение задач линейного программирования
  16. • Задача линейного программирования
  17. • Графическое решение задачи линейного ...
  18. • Решения задачи планирования производства симплекс ...
  19. • Симплекс метод в форме презентации
Рефетека ру refoteka@gmail.com