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