Моделирование задач линейного программирования. Транспортная задача и задача планирования производства

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Псковский государственный университет»

Кафедра «Теория Механизмов и Машин»

Контрольная работа

на тему: “Моделирование задач линейного программирования. Транспортная задача и задача планирования производства”

по дисциплине: “Моделирование и проектирование систем и средств управления”

Студент: Сергеев С.И.

Преподаватель: Святсков В.А.

Псков - 2012

Аннотация

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

Введение

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

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

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

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется Транспортной задачей Монжа-Канторовича. Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей ее можно решить проще (для задач малой размерности). Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из в груза, а в маленькие клетки -- соответствующие тарифы .

Задача решается методом потенциалов, если пункты не делятся на пункты отправления и пункты потребления, все пункты равноправны, но производство задается положительным числом, а потребление - отрицательным. Перевозки осуществляются по заданной сети, в которой дуги могут соединять любые пункты (включая производитель > производитель, потребитель > потребитель).

Транспортная задача с ограничениями пропускной способности

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

Многопродуктовая транспортная задача

Вариант транспортной задачи, в которой присутствует несколько продуктов (пункты могут производить/потреблять несколько продуктов). Для некоторых дуг задается ограничение на пропускную способность (без этого ограничения задача распадается на отдельные задачи по продуктам). Задача решается симплекс-методом (используется разложение Данцига-Вулфа, в качестве подзадач используются однопродуктовые транспортные задачи).

Задача планирования производства

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

В 1938-1939 гг. ленинградский математик (впоследствии академик, лауреат Ленинской, Государственных и Нобелевской премий) Л.В. Канторович в результате анализа ряда проблем организации и планирования производства сформулировал новый класс условно-экстремальных задач и предложил методы их решения. Так было положено начало новой отрасли прикладной математики линейному программированию. В более поздних работах Л. В. Канторович расширил область применения линейного программирования в социалистической экономике, сформулировав задачи отраслевого и народнохозяйственного оптимального планирования. А через два десятилетия после своего возникновения линейное программирование стало основным инструментом планово-экономических решений на всех уровнях социалистического народного хозяйства.

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

Далее методы планирования продолжали совершенствоваться, но только развитие вычислительной техники в конце 50-х гг. позволило сделать плановые многовариантные расчеты достаточно распространенными. Важную роль в организации и пропаганде экономико-математических исследований в этот период сыграл академик В. С. Немчинов. Именно в эти годы получают развитие некоторые разделы прикладной математики, связанные с решением оптимизационных задач: линейное и нелинейное программирование, теория оптимального управления и др. В 60-е гг. основное внимание исследователей сосредоточивается на разработке оптимизационных моделей различных типов и их практическом применении к решению задач планирования. Было построено большое количество экономико-математических моделей, на основе которых проведены расчеты по составлению реальных оптимальных планов (оптимальные планы перевозок, эксплуатации подвижного состава транспорта, использования топлива, загрузки оборудования предприятий; оптимальное размещение отдельных отраслей промышленности и предприятий отрасли; оптимальное планирование и распределение капиталовложений и т. д.), что дало большой народнохозяйственный эффект. Наряду с расширением сферы применения математических моделей в экономике и планировании осуществляется процесс усовершенствования моделей и использования более адекватного математического аппарата: переход от статических моделей к динамическим, от жестко детерминированных к стохастическим моделям, учитывающим случайность и неопределенность экономических процессов, применение дискретного программирования, методов статистического моделирования, создание новых алгоритмов, позволяющих решать задачи большой размерности.

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

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

линейный программирование транспортный математический

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

1. Концептуальное моделирование.

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

1.2 Концептуальное модулирование транспортной задачи.

1. n-количество пунктов потребления (магазины);

2. m-количество пунктов отправления (склады);

3. - запасы сырья в каждом пункте отправления (i=1,2,..m) (1)

4. - количество сырья или продукта (j=1,2…n) необходимое каждому пункту потребления. (2)

5. Дана матрица стоимости (тарифов)

-стоимость перевозки или сырья с i-го пункта отправления в j-ый пункт потребления. (3)

6. найти матрицу перевозок или план перевозок Х

(4)

В (4) означает количество сырья (продукта) перевозимое с i-го пункта отправления в j-ый пункт потребления

План перевозок Х формулы (4) удовлетворяет следующими ограничениями.

7. Все перевозки не отрицательны ?0;

i=1,2…m; j=1,2…n (5)

8. С каждого склада весь груз должен быть вывезен.

(6)

9. Потребности каждого пункта потребления (магазина) должны быть удовлетворены.

(7)

10. Матрица Х минимизирует значению следующей целевой функции

- min (8)

11. В начале проверить, что задача закрытая, т. е. выполняются условия баланса, производства и потребления.

= (9)

2. Постановка задачи на уровне структурно-функционального моделирования

Пусть дана транспортная задача в постановке п.1

Даны 2 таблицы

· Табл. 1 -транспортная

· Табл. 2-матрица тарифов

C=

Примечание: при реализации компьютерного моделирования значение формальных параметров элементов матрицы Х приобретают значения фактических.

3. Раздел структурно-функционального моделирования

Математическое моделирование транспортной задачи.

1. Фундаментом компьютерного моделирования является математическое моделирование, постановка задачи. Формулы (1)-(8).

Таблица тарифов стоимости

Рис1. Отображение рабочего листа.

А1-А3 - отправители;

В1-В3- получатели.

Рис.2 Отображение результатов имитационного моделирования.

2. Анализ математического решения:

Целевая функция:

35•2+5•1+60•2+45•1+5•2=250

250=250!

Проверка на закрытость:

35+45+70=40+60+50

150=150

С каждого склада всё вывезено:

35+0+0=35

0+0+45=45

5+60+5=70

4. Задача планирования производства

Анализ компьютерного решения:

Имитационное моделирование математической задачи

К=1; 140,8421

К=2; 184,2147

Анализ математического решения:

Ограничения: 36х₁+96х₂ ? 596

46х₁+76х₂ = 446

326х₁+426х₂ ? 5626

226х₁+126х₂ ? 3426

Функции цели:

Z(x)=19х₁+24х₂ => max

Вывод

По транспортной задаче

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

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

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

Благодаря программному продукту Excel, который входит в пакет MS Office, решение наших задач ускоряется в несколько десятков раз. А благодаря точным математическим расчетам данного ПО, мы можем без сомнения найти самые точные результаты исследований.

Список используемой литературы

1. Лекционный материал. (Преподаватель - Святсков В.А.)

2. Исследование операций в экономике. По ред. Н.Ш. Кремера.

3. Конюховский П.В. Математические методы исследования операций в экономике.

4. www. wikipedia.org/wiki/

Размещено на Allbest.ru