Xreferat.com » Рефераты по информатике и программированию » Решение задач линейного программирования

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

VALIGN=TOP BGCOLOR="#ffffff">
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;

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

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