Решение ТЗ с верхними и нижними границами

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

 

19. последовательность действий при постановке и решении ТЗ. 1. Определяется набор поставщиков, их ресурсы и размещение.

2. Анализируются рынки сбыта (регионы спроса на продукцию). Исследуется концентрация потребления. Находятся условные центры спроса, и, в соответствии с определившейся схемой привязки потребления к условным центрам выполняется агрегирование..

3. Выбирается период планирования (год, квартал, месяц) и для него составляется баланс ресурсов и потребностей. Исходными данными здесь выступают планы (прогнозы) производства и спроса (например, по статистическим отчетам). 4. Анализируется и формируется транспортная сеть. каждому узлу присваивается свой уникальный номер. Задаются в качестве поставщиков и потребителей соответствующие узлы, и формируются соответствующие наборы.5. Принимается решение о математической модели, используемой при решении задачи: открытая, закрытая, дополнительные ограничения.6. Выбирается показатель критерия оптимальности решения задачи.7. Подбирается программа расчетов оптимального плана на компьютере.8. Выполняется серия экспериментальных расчетов оптимальных планов с различными ограничениями.

9. Производится анализ полученных решений, обсуждение результатов с заказчиком. Если необходимо, выполняется корректировка модели в экономическом и математическом отношении.

10. Разрабатывается методика регулярных расчетов и формируются основные спецификации по инфорационному обеспечению расчетов.

 

Постановка и решение ТЗ по критерию времени.

Шаг1. Построение первоначального плана. В каждом столбце отыскивается минимальное значение времени заносится величина спроса соответствующего столбца. без ограниченийШаг2. Расчитываются небалансы по каждой строке

 

 

Производится метка строк в соответствии со знаками небалансов.

Если небаланс строка называется недостаточной если

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

Шаг3. Проверка получен ли оптимальный и допустимый план: Да, если все небалансы одного знака или равны нулю. Если - нет, переход к шагу 4. Шаг4. В каждом столбце содержащем поставку, относящуюся к недостаточной строке отыскивается минимальное значение показателя данного столбца, принадлежащего к избыточной строке и показателем сij базисной клетки: (разрешающее слагаемое) Шаг 5. Построение контура перераспределения базисного плана. В клетку относительно которой найдено минимальное значение вводится поставка, ограниченная значением небалансов строк, а также клеток помеченных знаком - входящих в состав данного контура перераспределения поставок. Переход к шагу 3. Получен ли оптимальный план. Все перевозки выполняются за суток - максимальное значение критерия оптимальности в клетке.

 

Постановка ТЗ на сети

А-поставщики В-потр-ли Т-промеж станции

 

аi-мощ-ть пост-каi вj-спрос j

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

Шаг 1. Отыскивается допустимый план, удовлетворяющий условиям: Соблюдаются все балансы по потокам с учетом ресурсов и потребностей узлов. Поскольку обычно решаются задачи закрытого типа, предполагается равенство суммы ресурсов и потребностей. Каждый поток больше или равен нулю. Количество звеньев с потоками (допустимый базисный план) в точности равен N-1, где N количество звеньев Шаг 2. Расставляется система потенциалов. Если исходный узел звена i, aj - конечный, и поток следует в направлении от / к у, то потенциал Pj=Pi+cij. Наоборот, если поток в обратном направлении, то Pj=Pi-cij. Шаг 3. Проверка на оптимальность плана. Все небазисные звенья, не содержащие потоков, должны удовлетворять условию: Pj-Pi=<Cij. Если все небазисные звенья удовлетворяют условию,то план оптимален, если есть нарушения условия оптимальности, то переход к шагу 4. Шаг 4. Отыскивается улучшенный базисный план. Для этого рассматривается звено с наибольшим нарушением условия оптимальности. На это звено назначается поток. Его величина определяется наименьшим значением перевозки, которое находится в специально составленном контуре. Последний состоит из базисных звеньев и звена с нарушением. выбирается порядок обхода звеньев от меньшего потенциала к большему. В соответствии с принятым порядком обхода находится наименьшее значение потока из звеньев с направлением против потока. На звено с нарушением назначается величина выбранного наименьшего значения, добавляется ко всем потокам, соответствующим направлению обхода, вычитается из величины потока у звеньев с направлением против потока. Переход к шагу 2.