Сущность и использование транспортных задач
Различные технико-экономические и экономические производственные задачи, начиная от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования.
На сегодняшний день это является важным инструментом экономического анализа: позволяет получить четкое представление о состоянии предприятия, охарактеризовать и количественно описать его внутреннюю структуру и внешние связи. Таким образом, экономико-математическое моделирование работы предприятия, фирмы, основанное на анализе его деятельности, должно обогащать этот анализ результатами и выводами, полученными после решения соответствующих задач.
Часто эксперимент с математической моделью может заменить реальный эксперимент, который либо слишком дорог, либо невозможен по тем или иным причинам. Все это и дает весомую актуальность применению задач линейного программирования в современных экономических условиях и данной курсовой работе как его частному случаю.
Целью работы стали систематизация теоретических данных по выбранной теме и их применение на конкретном предприятии. Для достижения этой цели были поставлены следующие задачи:
- рассмотреть сущность задач линейного программирования;
- выявить основные методы линейного программирования при решении экономических задач, изучить алгоритм построения экономико-математических моделей;
- применить теоретические положения построения ЭММ и транспортной задачи к статистическим данным ООО «Дубровчанка+», а также их решения в виде расчета плана максимизации прибыли и минимизации расходов на перевозку продукции потребителям.
Исходя из этого, объектом исследования в рамках курсовой работы стала область применения методов линейного программирования при решении экономических задач, а предметом – ее применение на конкретном предприятии.
Все это и дало обоснование для следующего структурирования работы. Курсовая работа содержит введение, где дается обоснование актуальности выбранной для исследования темы, формируются цели, задачи, объект и предмет исследования, отражены структура работы, а также теоретическая и информационная база, использованная при ее написании.
Основная часть данной курсовой работы, решающая поставленные цели и задачи, состоит из двух разделов. Так, первый из них «Краткое описание ООО «Дубровчанка+» включает в себя при этом подразделы «Историческая справка», «Характеристика предприятия» и «Организационная структура и статистические данные».
Второй раздел носит название «Применение методов линейного программирования при решении экономических задач» и включает в себя подразделы «Понятие линейного программирования» и «Построение и решение ЭММ на примере ООО «Дубровчанка+».
Третий «Применение теории транспортной задачи к работе ООО «Дубровчанка+» раскрывает понятие транспортной задачи, методику ее построения и решения в подразделе «Сущность транспортной задачи» и описывает механизм его применения на конкретном предприятии.
В заключении освещаются основные теоретические положения по исследуемой теме, а также обобщаются результаты проведенной работы.
Информационной базой для написания курсовой работы послужили популярные учебные пособия отечественных авторов: Алесинской Т.В. - Учебное пособие по решению задач по курсу «Экономико-математические методы и модели», А.И. Орлова – «Теория принятия решений», «Исследование операций в экономике» под редакцией Н.Ш. Кремера и другие.
1. КРАТКОЕ ОПИСАНИЕ ООО «ДУБРОВЧАНКА+»
1.1 Историческая справка
ООО «Дубровчанка+» является наследником одного из старейших предприятий Пензенской области - Городищенского деревоперерабатывающего завода, основанного в 1939 году.
История завода начиналась с работы объединения кустарей и ремесленников г. Городище в разных по своему профилю промартелях. Так, еще до Великой Отечественной войны в шорном и сапожном цехах работало лишь 18 человек. В годы войны к ним прибавились валяльный, кожевенный, жестяной и столярный цеха.
17 ноября 1971 года решением Пензенского Облисполкома предприятие было переименовано в «Городищенский деревоперерабатывающий завод» (ДОЗ), именно с этого периода начинается его интенсивное строительство, а численность занятых на производстве рабочих достигает более 700 человек.
Основной специализацией предприятия стал выпуск мебели различного назначения и мебельных деталей. Гарнитуры для кухни, выпускаемые в Городище, были востребованы как среди населения Пензенской, так и других областей. А полумягким стульям и табуретам был присвоен в свое время государственный Знак качества.
Однако помимо производства мебели, ДОЗ занимался лесоразработками, ежегодно заготавливая 18 тысяч кубометров древесины, изготовлением кирпича и резной сувенирной продукции.
С 2001 года после технического перевооружения предприятия и оснащения цехов современными деревообрабатывающими станками зарубежного и отечественного производства предприятие приступило к выпуску качественной мебели современного дизайна и высокой экологической чистоты, пиломатериалов и поганажа.
1.2 Характеристика предприятия
На сегодняшний день ООО «Дубровчанка +» располагается на территории в 19 гектаров, обладает мебельными цехами общей площадью 8500 квадратных метров, собственным лесозаготовительным, лесопильным и сушильным участками. Заготовка ежегодно арендуемого леса позволяет в полной мере обеспечивать производство мебели из отборной древесины, производить пиломатериалы хвойных и лиственных пород на продажу. За последние годы на предприятии также налажено производство погонажа (вагонки, половой рейки, блок-хауса).
Серийно изготавливаемая продукция представлена наборами мебели для кухни с фасадами из пластика и массива древесины, угловыми скамьями, табуретками, обеденными столами, кроватями и другими изделиями(1). Помимо серийных моделей, организовано производство мебели по индивидуальным проектам.
Удобное географическое расположение предприятия позволяет производить отгрузку продукции автомобильным и железнодорожным транспортом в любую точку России, ближнего и дальнего зарубежья. Кроме всего этого, для заказчиков и покупателей подмосковного и близлежащих к нему регионов недавно открыто представительство в Москве, так же полно демонстрирующее всю гамму мебельной продукции.
Основной упор в развитии предприятия сейчас делается на поддержание и развитие надежных партнерских отношений с заказчиками, внедрение новых технологий с целью постоянного совершенствования качества и снижения стоимости выпускаемой продукции, расширение ассортимента и разработку новых моделей мебельной продукции, отвечающих высоким требованиям покупателей.
Таблица 1
Основные виды продукции ООО «Дубровчанка +»
Наименование изделия | Габаритные размеры, мм | Ед.изм. |
| Кухня "Добровчанка-Н8" (угловая, без раковины, фасад - массив, постформинг) | 2400*1600 | к-т. |
| Шкаф навесной 2-х дверный (фасад - массив) | 800*320*720 | шт. |
| Шкаф-стол однодверный (фасад - массив) | 400*600*850 | шт. |
| Шкаф навесной однодверный стекло (фасад - массив) | 400*320*420 | шт. |
| Шкаф-стол с ящиком на 400 (фасад - массив) | 400*600*850 | шт. |
| Шкаф-стол на 800 (фасад - массив) | 800*600*850 | шт. |
| Шкаф-стол под мойку (без крышки, без раковины, массив) | 800*600*850 | шт. |
| Шкаф навесной однодверный (фасад - массив) | 400*320*720 | шт. |
| Шкаф-стол угловой (фасад - массив) | 800*800*850 | шт. |
| Шкаф навесной угловой (фасад - массив) | 600*600*720 | шт. |
| Шкаф навесной открытый | 200*300*720 | шт. |
| Шкаф навесной 2-х дверный, массив, стекло | 800*320*720 | шт. |
| Кухня "Дубровчанка-Н3" (без раковины, фасад - массив, постформинг) | 2000*600*2085 | к-т. |
| Стол обеденный, пластик | 800*600*750 | шт. |
| Стол обеденный "Ладога", пластик | 110*600*750 | шт. |
| Стол обеденный из массива | 1200*670*750 | шт. |
| Стол обеденный раскладной, пластик | 800*600(1200*800)*750 | шт. |
| Табурет кухонный, массив | 320*320*450 | шт. |
| Табурет кухонный, пластик | 320*320*450 | шт. |
| Табурет кухонный, мягкий | 320*320*450 | шт. |
| Скамья угловая | 1540*1130*800 | шт. |
| Кровать подростковая 2-х ярусная | 1985*750*1650 | шт. |
| Кроватка детская, массив | 1255*670*900 | шт. |
| Комод из массива | 800*560*850 | шт. |
| Прикроватная тумбочка | 505*400*555 | шт. |
| Стул мягкий (шинил) | шт. | |
| Матрац ватный (кровать подр. 2-х ярусная) | шт. | |
| Матрац ватный (кроватка детская) | шт. | |
| П/материал хвойных пород необрезной | м3 | |
| П/материал лиственных пород необрезной | м3 | |
| Евровагонка | м3 |
1.3 Организационная структура и статистические данные
Организационная структура предприятия представлена на схеме:
В настоящее время ООО «Дубровчанка+» располагается на территории в 19 га, обладает мебельными цехами общей площадью 8500 квадратных метров, лесозаготовительным, лесопильным и сушильным участками. Здесь производится более 40 видов мебельной продукции, на предприятии занято порядка 120 человек со средней заработной платой 6000-7000 рублей. Средний объем производства составляет около 1000 единиц продукции в месяц, которая реализуется как среди потребителей Пензенской области, так и других регионов: Самарской, Саратовской, Тамбовской, Московской и других областей. Объемы лесозаготовки для собственного производства и к реализации составляют примерно 10 000-13000 кубометров древесины в год.
2. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ РЕШЕНИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ
2.1 Понятие задачи линейного программирования
Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Л.В. Канторовича «Математические методы организации и планирования производства» (2). Поскольку методы, изложенные им, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти не замеченной. Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования.
Таким образом, линейное программирование - область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной (целевой) функции многих переменных при наличии линейных ограничений, т. е. равенств или неравенств, связывающих эти переменные (1).
Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
В этом случае говорят, что задача представлена в канонической форме. При этом система линейных уравнений и неравенств, определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности. В частном случае, если I = Ш, то система состоит только из линейных неравенств, а если I = M, то – из линейных уравнений.
Итак, характерные черты задач линейного программирования следующие:
1) показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x1, x2, ..., xn);
2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.
Любую задачу линейного программирования можно свести к задаче в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот.
Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
4) если некоторая переменная xk не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: 
, где 
- свободный индекс, 
.
При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональностьозначает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционаленвеличине этой переменной. Аддитивностьозначает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных (4).
Исходя из отмеченных выше особенностей задач линейного программирования, можно наметить следующую общую схему формирования экономико-математической модели:
- выбор некоторого числа переменных величин, заданием числовых значений которых однозначно определяется одно из возможных состояний исследуемого объекта или явления;
- выражение взаимосвязей, присущих исследуемому объекту (явлению), в виде математических соотношений (уравнений, неравенств); эти соотношения образуют систему ограничений задачи;
- количественное выражение выбранного критерия оптимальности в форме целевой функции;
- математическое формулирование задачи как задачи отыскания экстремума целевой функции при условии выполнения ограничений, накладываемых па переменные (1).
Говоря о математических моделях задач линейного программирования, выделяют, как правило, несколько основных видов задач:
- задачи по определению оптимального ассортимента продукции (в качестве критериев оптимальности в них могут быть использованы прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени);
- задачи по использованию мощностей оборудования (обычно поставлены так, чтобы израсходовать все отведенное время работы машины, т.е. обеспечить полную загрузку машины, при этом количество выпускаемой продукции каждого вида должно быть, по крайней мере, не менее Nj;
- задачи по минимизации дисбаланса на линии сборки (что по существу эквивалентно максимизации выпуска изделий);
- задачи составления кормовой смеси (задача о диете);
- задачи составления жидких смесей (класс моделей, аналогичных рассмотренным выше, возникает при решении экономической проблемы, связанной с изготовлением смесей различных жидкостей с целью получения пользующихся спросом готовых продуктов);
- задачи о раскрое или о минимизации обрезков (состоят в разработке таких технологических планов раскроя, при которых получается необходимый комплекс заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму);
- транспортные задачи (по распределению ресурсов, находящихся у m производителей (поставщиков), n потребителям этих ресурсов) (3).
Обобщая их, можно сделать следующие выводы.
1. Ограничения в задачах линейного программирования могут быть выражены как равенствами, так и неравенствами.
2. Линейная функция может стремиться как к максимуму, так и к минимуму.
3. Переменные в задачах всегда неотрицательны.
Для решения задач линейного программирования в настоящее время используются несколько основных методов. Среди них:
- графический метод (используемый обычно для решения задач линейного программирования, представленных в стандартном виде, если число переменных в целевой функции и системе ограничений не более двух);
- симплексный метод (стандартный метод решения задач линейного программирования с любым числом переменных, основанный на переходе от одного опорного плана к другому, при котором значение целевой функции улучшается (по крайней мере, не ухудшается);
- решение задач линейного программирования с использованием приложения MS Excel (1).
2.2 Построение и решение ЭММ на примере ООО «Дубровчанка+»
Пользуясь статистическими данными деятельности предприятия, составим экономико-математическую модель задачи по определению оптимального ассортимента продукции.
Наименование изделия | Габаритные размеры, мм | Ед.изм. | Цена, руб. | Усл. обознач. |
| Кухня "Добровчанка-Н8" (угловая, без раковины, фасад - массив, постформинг) | 2400*1600 | к-т. | 13000-00 | A |
| Шкаф навесной 2-х дверный (фасад - массив) | 800*320*720 | шт. | 1300-00 | B |
| Стол обеденный "Ладога", пластик | 110*600*750 | шт. | 1200-00 | C |
| Кровать подростковая 2-х ярусная | 1985*750*1650 | шт. | 4300-00 | F |
| Комод из массива | 800*560*850 | шт. | 4450-00 | G |
Для производства пяти видов продукции (в таблице) ООО «Дубровчанка +» использует древесину двух видов. Нормы затрат ресурсов на одно изделие каждого вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в следующей таблице:
| Ресурсы | Нормы затрат ресурсов | Общее кол-во ресурсов | ||||
| А | B | C | F | G | ||
Древесина, м3 I Вид | 1,5 | 0,08 | 0,06 | 0,2 | 0,2 | 350 |
| II Вид | 0,2 | 0,05 | 0,04 | 0,2 | 0,1 | 130 |
| Трудоемкость, чел. - часы | 3,3 | 0,4 | 0,3 | 1 | 1,2 | 1100 |
| Прибыль от реализации, тыс. руб. | 13000 | 1300 | 1200 | 4300 | 4450 | |
Определим, сколько единиц каждого изделия следует изготавливать предприятию, чтобы прибыль от их реализации была максимальной.
Решение:
Обозначим изделие каждого вида соответственно a, b, c, f, g. Тогда на изготовление всей продукции уйдет (1,5a+0,08b+0,06c+0,2f+0,2g) м3 древесины I вида и (0,2a+0,05b+0,04c+0,2f+0,1g) м3 древесины II вида. Так как запасы этих ресурсов не превышают 350 и 130 м3 соответственно, то
1,5a+0,08b+0,06c+0,2f+0,2g ≤ 350
0,2a+0,05b+0,04c+0,2f+0,1g ≤ 130
Трудоемкость производства этих изделий равна
(3,3a+0,4b+0,3c+1f+1,2g). Значит,
3,3a+0,4b+0,3c+1f+1,2g ≤ 1100
Итак, система ограничений имеет вид:
А прибыль будет выражена функцией
F=13000a+1300b+1200c+4300f+4450g
Чтобы найти решение задачи, воспользуемся MS Excel.
Целевую функцию зададим выражением:
=13000*A2+1300*B2+1200*C2+4300*F2+4450*G2
А систему ограничений так:
=1,5*A2+0,08*B2+0,065*C2+0,2*F2+0,2*G2
=0,2*A2+0,05*B2+0,04*C2+0,2*F2+0,1*G2
=3,3*A2+0,4*B2+0,3*C2+1*F2+1,2*G2
Открыв в меню «Сервис» команду «Поиск решения», заполним открывшееся окно: установим целевую ячейку, равную максимальному значению, определим ячейки-переменные, значения которых искомы, установим систему ограничений по имеющимся запасам сырья и располагаемой трудоемкости.
После этого в окне «Параметры» установим флажок в ячейку «Линейная модель» и выберем кнопку «Выполнить».
В результате решения получаем данные об оптимальном ассортименте продукции:
| Переменные | ||||||
| 160 | 0 | 20 | 429 | 114 | ||
|
| ||||||