Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Урок'
участники ролевых игр (заранее подготовленные ученики): судьи, адвокаты, прокуроры, наблюдатель, образованные господа, журналисты, железнодорожный ра...полностью>>
'Урок'
Познакомить с особенностями национального и религиозного состава населения России. Сформировать представление о культуре народов (религии, жилье, пищ...полностью>>
'Документ'
Copyright—the idea that an author of a work has rights on the uses and the reproduction of the work—originated in the field of literature. With the in...полностью>>
'Документ'
Для кінцевого користувача мережа - це не комп'ютери, кабелі і концентратори і навіть не інформаційні потоки, для нього мережа - це, перш за все, набір...полностью>>

Тема : Оптимизация потокового процесса встроенными средствами вычислительного пакета Mathcad (реализация сбалансированной транспортной задачи с использованием компьютерных технологий)

Главная > Документ
Сохрани ссылку в одной из сетей:

Задание по курсу «Datortehnoloģijas transportā»

Тема : Оптимизация потокового процесса встроенными средствами вычислительного пакета Mathcad (реализация сбалансированной транспортной задачи с использованием компьютерных технологий)

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

Краткие сведения из теории

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

Несмотря на различные области приложения задачи линейного программирования имеют единую постановку. Формально общая задача линейного программирования понимается как задача поиска экстремума скалярной линейной целевой функции F(X) - вектора управляемых (искомых) переменных X=(x1,..., xn) и сводится к определению значений переменных X=(x1,x2, , xn), приводящих к экстремуму линейную целевую функцию

F(X) = C1*X1 + ... + Cj*Xj + ... + Cn*Xn -> extr;

при линейных функциональных ограничениях:

Ai1*X1 + ... + Aij*Xj + ... + Ain*Xn (Ri) = Bi, i = 1,.2., , m

и прямых ограничениях по управляемым параметрам:

Xj  0, j = 1,...,n,

где Ri - любые из отношений < ; > ; = или их комбинации.

Классическая транспортная задача в общем виде формулируются следующим образом:

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

  • ресурс от любого производителя может быть доставлен к любому потребителю;

  • размеры отправлений и размеры приема по каждому из пунктов, выражаемые в тоннах, киловаттах или других единицах

  • стоимость доставки продукта от каждого пункта производства в каждый пункт приема .

Требуется найти оптимальный план доставки продукта (т.е. план, который обеспечит минимальные расходы на с транспортировку). При заданной стоимости доставки продукта между каждой парой пунктов поставки и потребления оптимальный план должен удовлетворять следующим условиям :

  • минимизировать транспортные расходы,

  • обеспечить вывоз всего продукта от каждого пункта производства ,

  • полностью покрыть установленные размеры потребления подукта в каждом пункте приема.

Исходные данные транспортной задачи удобно задавать таблицей вида:

Aj

Bi

A1

A2

A3

B1

с1,1

с1,2

с1,3

B2

с2,1

с2,2

с2,3

где

Bi – возможности производителей или поставщиков ( установленные объемы продукта, которые требуется вывезти c пунктов поставки )

Aj – возможности потребителей ( установленные размеры потребления в пунктах приема продукта Aj

Сij – стоимость доставки единицы груза доставки продукта от i-того пункта производства в j-тый пункт приема

Пример постановки задачи:

Дано: n=2 - число пунктов отправления однородного продукта (дизельного топливо, бензина, каменного угля, электрической энергии и др)

m=3 -число пунктов приема ресурса (дизельного топлива, бензина каменного угля, потребителей электроэнергии и др);

Известны возможности поставщиков (Bi). – объемы отправляемого продукта (число цистерн , число бензовозов, число вагонов и др

Известны возможности потребителя (Aj); (например мощности станций по по приему и обработке вагонов на пунктах приема (Aj);

Заданы потребности (например, число вагонов, которое могут обработать принимающие станции )

Задача сбалансирована, т. е. общий объем произведенной продукции в точности покрывает суммарные потребности пунктов приема. В нашем случае

B1 + B2 = A1 + A2 + A3)

Известна стоимость доставки единицы груза Ci,j из каждого пункта отправления в каждый пункт приема в виде таблицы

Пункты отправления

Пункты приема

 

A1

A2

A3

B1

С 1,1

С1,2

С1,3

B2

С 21

С2,2

С2,3

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

Обозначим через xij искомый объем перевозки -

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

B1+ B2 = A1 + A2 + A3 ,

оптимальный план доставки соответствует минимуму линейной целевой функции:

при n=2 линейных ограничениях по отправлениям

x11+x12+x13 = B1

x21+x22+x23 = B2

и m=3 линейных ограничениях пo потреблению

x11+x21+x31 =A1

x12+x22+x32 = A2

x13+x23+x33 = A3

и при очевидном условии неотрицательности управляемых переменных:

x i,j 0, i = 1,2, и j = 1,.2,3

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

Пример решения транспортной задами средствами Mathcad

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

Имеется n электростанций и m потребителей электроэнергии. Пусть Xi,j – искомый объем передачи энергии от i-той электростанции (i=1,..., N) к j-тому потребителю (j =1,..., M). Управляемые (искомые) параметры Xi,j характеризуют объем передачи энергии между каждой электростанцией i=1,..., N и каждым потребителем j=1,..., M

Для каждой электростанции i=1,..., n задан объем выработанной энергии Bi, для каждого потребителя j= 1,..., m задан объем потребления Aj ;

Известна также стоимость потерь энергии при передаче каждого киловатта энергии Ci,j от i-той электростанции в j.-ый пункт потребления.

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

B1 + ... + BN = A1 + ... + AM ,

оптимальный план доставки соответствует минимизации линейной целевой функции:

при n линейных ограничениях по отправлениям:

Xi,1 + ... + Xi,j + ... + Xi,n = Ai, где i = 1,..., N

и m линейных ограничениях пo потреблению:

X1,j + ... + Xi,j + ... + Xm,j = Bj, j = 1,..., M,

а также при очевидном условии неотрицательности управляемых переменных:

Xi,j 0, i = 1,...,N и j = 1,..., M

Известна также стоимость потерь энергии Ci,j при передаче ее от каждой станции в каждый пункт приема в виде следующей таблицы:

Электростанции

Потребители

A1=145

A2=210

A3=160

B1=237

с1,1=11,5

с1,2=7

с1,3=12

B2=278

с2,1=6,2

с2,2=10

с2,3=9

Найти оптимальный план доставки энергии потребителям

Л

истинг решения задачи

,

Пример реализация транспортной задачи в Excel (программа Solver)

Solver ‑ это отдельная программа, которую необходимо предварительно загрузить, выбрав команду Tools‑Add Insв спискеAdd-Ins Available выбрать Solver Add-InsOK‑Excel добавит Solver в меню Tools. Чтобы принимать оптимальное решение с использованием Solver, достаточно иметь математическую модель, на основе которой это решение принимается. Алгоритм определения решения в программе Solver таков: в окне программы в целевую ячейку заносится формула, определяющая желаемый результат, искомые переменные заносятся в изменяемые ячейки, сообщается программе требуемый конечный результат и указываются переменные, которыми нужно управлять. Выполняя последовательность итераций, Solver находит оптимальное решение. При этом значения параметров в изменяемых ячейках варьируются так, чтобы значение в целевой ячейке стало равно заданному (желаемому) значению.

Постановка задачи: составить оптимальный план перевозок для фирмы-перевозчика, получившей долгосрочный заказ от фирмы-поставщика на транспортировку бензина из трех портов (m=3) в пять (n=5) заправочных станций.. При этом должен быть обеспечен минимум общих затрат фирмы-перевозчика на транспортировку и удовлетворены поставленные ограничения:

    с каждого порта должен быть вывезен весь бензин

    нельзя превысить возможности емкостей каждой заправочной станци

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

Накладывая условие линейности, будем считать, что при перевозке Xij единиц продукта из пункта Si в пунктQj транспортные расходы будут равны Сij * Xij.

Чтобы найти решение поставленной задачи с помощью программы Solver, необходимо выполнить следующие процедуры:

Ввести данные так, как это показано на вкладке, размещенной на столе преподавателя:

После ввода данных необходимо выполнить следующие процедуры:

a. задание цели: выбрать команду Tools-Solver,откроется окно Solver Parameters;

  • в поле Set Target ввести ссылку на целевую ячейку-ту, в которой находится формула для оптимизации;

  • в разделе Equal To включить соответствующую кнопку-max, min, value;

b. задание переменных:

  • в поле By Changing Cells ввести адреса ячеек, значения которых Solver будет изменяться в процессе поиска решения;

c. задание ограничений на условия:

  • в разделе Subject to the Constraints окнаSolver выбрать команду Add-

  • в окне Add Constraint в поле Cell Referens ввести адрес ячейки, для которой будет введено ограничение-;

  • в ниспадающем списке выбрать подходящий оператор для ограничения;

  • в поле Constraint ввести предельное значение ограничения;

  • выбрать Add-чтобы ввести новое ограничениу; ввести OK -для возврата в окно Solver Parameter;

  • нажать Solve. Откроется окно Solve Result с результатом;

  • если решение удовлетворяет- включить Keep solver Solution-OK,если нет -включить Cancel

B

C

D

E

F

G

H

Ввод первичных данных

 

Количество товара, перевозимое из каждого порта в каждую заправочную станцию

 

 

Порт

Заправочная станция 1

Заправочная станция 2

Заправочная станция 3

Заправочная станция 4

Заправочная станция 5

Общее количество бензина из одного порта на все заправочные станции

Предложение порта

primarie dati iteracijai

 

 

Порт1

1

1

1

1

1

=SUM(B6:F6)

310

Порт 2

1

1

1

1

1

=SUM(B7:F7)

260

Порт 3

1

1

1

1

1

=SUM(B8:F8)

280

Общее количество бензина из всех портов на конкретную заправочную станцию не должно превышать возможности станции

=SUM(B6:B8)

=SUM(C6:C8)

=SUM(D6:D8)

=SUM(E6:E8)

=SUM(F6:F8)

 

=SUM(H6:H8)

Возможности станций

140

100

200

160

220

Ограничения

 

Таб. 2. Цена транспортировки

Порт

станция 1

станция 2

станция 3

станция 4

станция 5

 

 

Порт1

10

8

6

5

4

 

 

Порт1

6

5

4

3

6

 

 

Порт1

3

4

5

5

9

=B6:F8

 

Транспортные расходы

=B13*B6+B14*B7+B15*B8

=C13*C6+C14*C7+C15*C8

=D13*D6+D14*D7+D15*D8

=E13*E6+E14*E7+E15*E8

=F13*F6+F14*F7+F15*F8

=SUM(B16:F16)

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

Общее количество бензина, перевозимое из одного порта на все заправочные станции должно быть меньше или равным предложению порта

=G6:G8<=H6:H8

 

Ограничения

Общее количество бензина, перевозимое из всех портов на конлретную заправочную станцию не должно превышать возможности станции

=B9:F9>=B10:F10

 

 

Количество бензина, перевозимое с каждого порта на каждую заправку должно быть положительным числом

=B6:F8>=0

 



Скачать документ

Похожие документы:

  1. Тема: Основные организационные формы в крупномасштабном бизнесе

    Решение
    Развитие современного научно-технического прогресса в странах с развитой экономикой обусловлено размерами организации и эффективностью их инновационной деятельности.
  2. Основная образовательная программа высшего профессионального образования Направление подготовки (1)

    Основная образовательная программа
    Результаты освоения ООП ВПО определяются приобретаемыми выпускником компетенциями, т.е. его способностью применять знания, умения и личные качества в соответствии с задачами профессиональной деятельности.
  3. 1 История развития компьютерной техники, поколения ЭВМ и их классификация Развитие электронной базы, влияющее на усовершенствование ЭВМ. Поколения ЭВМ эвм

    Документ
    Развитие радиоэлектроники и новейшей технологии произ­водства радиоаппаратуры обусловило смену поколений ЭВМ. Строго говоря, характеристикой поколения ЭВМ является конструктивно-технологическая составляющая элементной базы – вакуумные
  4. 1. Основные понятия информатики. Определение понятия информатика. Предмет и задачи

    Документ
    Информатика – это основанная на использовании компьютерной техники дисциплина, изучающая структуру и общие свойства инф-ции, а также закономерности и методы ее создания, хранения, поиска, преобразования, передачи и применения в различных
  5. Министерство образования Российской Федерации Московский государственный технический университет имени Н. Э. Баумана

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

Другие похожие документы..