Решение задач линейного программирования
Введение
Линейное программирование — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.
Программирование в управлении можно представить как процесс распределения ресурсов. Существует ряд различных методов, основанных на идеях математического программирования, однако, наиболее широкое применение нашел метод линейного программирования.
Применение методов линейного программирования актуально в сегодняшнее время, так как использование математических моделей является важным направлением совершенствования планирования и анализа деятельности компании. Представление данных в виде математической модели позволяет конкретизировать информацию, создавать и моделировать варианты, выбирать оптимальные решения.
Актуальность линейного программирования и обусловила выбор темы данной курсовой работы. Значимость выбранного вопроса определяется также тем, что использование метода линейного программирования представляет собой важность и ценность – оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями
Цель курсовой работы – на практическом примере продемонстрировать использование методов линейного программирования.
Задачи работы обусловлены ее целью:
Во-первых, раскрыть теоретическое содержание данной темы.
Во-вторых, сформулировать и найти оптимальное решение задач с помощью средств 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 |
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |