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

Введение

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

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

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

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

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

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

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

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

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

 

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 + a11x2 +  ……  + a11 xn  />=/>  b1 ,

a21 x1 + a22x2 +  ……  + a2n xn /> =/> b2 ,

am1 x1 + am2x2 +  …… + 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

...

A0,m+1

...

A0,n

X1

A1,0

1 ...

A1,m+1

...

A1,n

X2

A2,0

1 ...

A2,m+1

...

A2,n

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

Xm

Am,0

... 1

Am,m+1

...

Am,n

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

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

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

 

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

 

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

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

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

a21 x1 + a22x2 +  ……  + a2n xn  = b2 ,

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

am1 x1 + am2x2 +  …… + 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<sub/> и соответствующие значения целевой функции (в графах«Целевой результат»).

 


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 таблиц:

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

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

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 MinimizationProblems. SIAM Journal on Scientific Computing, Vol. 21, Number 1, pp. 1-23,1999.

еще рефераты
Еще работы по информатике, программированию