Материал: 5462

71

Здесь Eн – нормативный коэффициент эффективности капитальных вложений, ki – удельные капитальные вложения, Ci – затраты на производство единицы продукции в i-м пункте производства, Cij – затраты

на доставку единицы продукции из i-го пункта производства в j-й пункт потребления.

Эта модель представляет собой открытую транспортную задачу, которая приводится к закрытой введением фиктивного потребителя. Варианты поставщиков, которые в оптимальном плане «прикрепились» к фиктивному потребителю, в оптимальный план не включают.

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

реконструкции первого предприятия (пристройки к нему нового цеха) и строительства нового предприятия А4. Себестоимость производства

Нормативный коэффициент эффективности капитальных вложений, связанный со строительством и реконструкцией Ен 0,15 .

Известна матрица транспортных затрат на доставку единицы продукции:

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

Решение. Каждому проектируемому варианту прироста мощности выделяем отдельную строку и даем недостающую мощность 150. Вычисляем затраты на производство и доставку продукции (Сi Cij ) для

введением фиктивного потребителя со спросом равным 150. Решаем задачу методом потенциалов. Получаем оптимальный план Хопт

потребителю, поэтому оптимальным вариантом прироста мощностей является реконструкция предприятия А1. После реконструкции мощность предприятия А1 составит 150+150=300 (ед). Полученное решение является целочисленным. При этом Zmin 4725.

Вопросы для самопроверки

1.В чем смысл задачи оптимального размещения производства?

2.Как формируются приведенные затраты на производство продукции на действующих предприятиях и на планируемых вариантах реконструкции и строительства предприятий.

3.Какие решения называются цело- и нецелочисленными?

4.Как выбрать оптимальный вариант прироста мощности?

73

Задачи для самостоятельного решения

Мощности трех действующих предприятий в пунктах А1, А2, А3 составляют ai (280; 420; 500) единиц однородной продукции.

Перспективная потребность в этой продукции четырех потребителей в пунктах В1, В2, В3, В4 равна b j (440; 360; 350; 300).

Увеличение выпуска продукции возможно за счет строительства предприятий в пунктах А4 и А5 и реконструкции действующих. Известны: Сi – затраты на производство единицы продукции;

C рек затраты на производство после реконструкции;

ki капитальные затраты на единицу готовой продукции, связанные с

реконструкцией и строительством;

Cij затраты на доставку единицы продукции от i-го предприятия до j-го

потребителя;

Eн 0,15 нормативный коэффициент эффективности, связанный со

строительством и реконструкцией.

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

Предлагаются варианты прироста мощностей

1.Реконструкция А1 и строительство А4.

2.Реконструкция А1 и строительство А5.

3.Реконструкция А2 и строительство А4.

4.Реконструкция А2 и строительство А5.

5.Реконструкция А3 и строительство А4.

6.Реконструкция А3 и строительство А5.

7.Реконструкция А1 и реконструкция А2.

8.Реконструкция А1 и реконструкция А3.

9.Реконструкция А2 и реконструкция А3.

10.Строительство А4 и строительство А5.

74

Глава 10. Транспортная задача в сетевой постановке

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

Метод решения транспортной задачи на сети требует меньше подготовительной работы. Для решения задачи требуется составить один макет сети с указанием расстояния каждого участка между узлами или стоимости перевозки по нему. Макет, на котором решается транспортная задача в сетевой постановке линейного программирования, может иметь форму обычной железнодорожной или автодорожной сети, на каждом участке которой обозначена его длина или стоимость перевозки.

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

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

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

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

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

На сети с n вершинами и m дугами расположено множество поставщиков Ai и потребителей B j , известны ресурсы каждого

75

поставщика ai и потребности каждого потребителя b j . Задана Cij

стоимость перевозки груза по каждой дуге и ее пропускная способность

dij .

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

В этом случае экономико-математическая модель задачи имеет вид

ij

iA, j B ;

xij dij ; xij 0,

где xij – грузопоток по дуге i, j ;

Cij – стоимость перевозки груза по дуге i, j или ее длина; dij – пропускная способность дуги i, j .

Пример Рассмотрим алгоритм решения транспортной задачи на сети без

ограничения по пропускной способности.

На рис.1 представлена симметричная транспортная сеть с 11 вершинами (станциями отправления и назначения) и 17 звеньями (участками, соединяющими пункты отправления и назначения). В каждом звене проставлено число, характеризующее расстояние (длину звена Сij ) между

соседними вершинами, соединенными данным звеном.

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