|
|
БИЛЕТ 7 ВОПРОС 2 Особенность линейно – целочисленных задач и методов их решения
Задача ЦЛП – это задача математического программирования, в которой все или некоторые переменные должны принять только целочисленное значение, а целевая функция и функции, входящие в ограничение – линейное.
Т.е. это такая нелинейная задача, которая может быть линейной, если бы не требования целочисленности ряда переменных. Задачу ЦЛП можно решать например, как задачу ЛП без учета условий целочисленности переменных, а затем округлить полученное решение с избытком или недостатком. При этом будет получено некоторое целочисленное решение.
Однако использование такого подхода требует обязательной проверки допустимости решений. Таким методом часто пользуются при решении практических задач, особенно когда значения переменных настолько велики, что можно пренебречь ошибками округления.
При решении задач в которых целочисленные переменные принимают малые значения округляются не могут привести к далекому от истинного оптимума целочисленного решения.
Таким образом, эвристический метод решения задач ЦЛП основанный на округлении оптимального решения соответствующей задачи ЛП, позволяет получать в общем случае только приближенные решения. Для определения истинного значения целочисленных переменных применяется метод отсечений и метод ветвей и границ.
Первый базируется на идее деформации ОДР задачи ЛП таким образом, чтобы от нее было отсечено оптимальное нецелочисленное решение, но сохранены все допустимые целочисленные решения.
Т.е. была бы построена область, для которой оптимальное решение соответствующей задачи ЛП совпадает с оптимальным решением задачи ЦЛП.
Указанная деформация осуществляется путем введения специальных дополнительных ограничений.
Второй метод основан на идее проверочной подстановки всех допустимых целочисленных значений в целевую функцию и сравнении полученного результата. Естественно что удобной для использования это идея становится лишь тогда, когда полный перебор может быть сокращен дополнительными рассуждениями, основанными на принципе разветвления комбинаторского прог - ия.
БИЛЕТ 8 ВОПРОС 1 Методика определения длины критического пути структурного плана.
Длительность критического пути сетевой модели определяется с помощью анализа данных из таблицы событий.
Индекс события
Ранний срок свершения события, Тран
Поздний срок свершения события, Тпоз
Резерв времени свершения события, Rсоб
1
2
3
4
Когда будет вычислен ранний срок наступления завершающего события n (столбец 2 в б
таблице событий), тогда может быть определена длина критического пути структурного плана, т.к. S= Трn
а n=N завершающего события сетевой модели
БИЛЕТ 8 ВОПРОС 2 Применение булевых переменных при построении моделей задачи планирования производства.
В общем виде модель задачи ЦОП может быть представлена следующим образом Z=C*X стремится к максимуму, а X+B=0, X>=0, Xi – целые числа, J принадлежит Т, где Т – множество значений индекса J, соответствующих целочисленных переменных. Причём задача называется полностью целочисленная, если все значения J принадлежат Т и частично целочисленная в противном случае. Если целочисленная переменная может принимать значения равные только 0 или 1, то выше изложенная модель задачи ЦЛП является моделью задачи с булевыми переменными. Любая целочисленная переменная может быть выражена через булевую переменную. Допустим 0<=Х<=N – целочисленная переменная, значения которой не превышают некоторого целого положительного числа N. Тогда если Б1, Б1 БN.. булевая переменная, все допустимые значения Х представляются в виде Х = Б1+Б1+БN…Другое(более экономичное) двоичное представление в котором кол-во булевых переменных меньше N, задаётся формулой Х=Б1+2Б2+2в квадрате Б3 + и т.д. + 2(K-1)*BK, где K – наименьшее целое число удовлетворяющее условие 2 в степени К-1 >=N. Таким образом любую целочисленную задачу можно записать в булевых переменных.
БИЛЕТ 9 ВОПРОС 1 Расчет времени парам. работ структурного плана: организационный смысл работ структурного плана и методика определения значений.
В результате расчетов определяется временный параметры работы сети к числу которых относится: полная(Г i, j) и свободная(D i, j). Резервы времени выполнения работ(i j). С организационной точки зрения резервы времени работ(полная и свободная) показывают насколько можно увеличить её длительность или задержать срок её начала, причём свободная – при условии неизменности сроков выполнения других работ, а полная – при сохранении длительности критического пути. А ещё свободных резервов времени: D i, j = Tpj - Tpi - t i,j , (i,j) принадлежат Q. D i,j - свободный резерв времени работ. Q - множество работ сетевой модели. Расчет полных резервов времени Г i,j = Rj + D i,j = Тpj - Tpi - t i,j. Г i ,j - полный резерв времени работ. Для работ критического пути справедливо соотношение: Tpj = Tpi + t i,j. Все резервы времени критических работ = 0. Расчет резервов времени работ позволяет определить критический путь сетевой модели.
БИЛЕТ 10 ВОПРОС 1 Методика определения состава работ критического пути структурного плана
Для того чтобы определить состав работ критического пути структурного плана, необходимо рассчитать полные резервы времени всех работ, которые принадлежат данному структурному плану. Если полный резерв времени какой – либо работы =0, то эта работа входит в состав работ критического пути. Таким образом выясняется, как проходит критический путь, то есть какие работы в критическом пути.
БИЛЕТ 10 ВОПРОС 2 Транспортная задача ЛП
ТЗЛП заключается в определении объема перевозок от поставщиков к потребителям, если известны выпуск продукции у каждого поставщика и потребности потребителей; затраты на перемещение грузов от поставщиков к потребителям. План грузоперевозок для им.min затраты. Причем это могут быть затраты денежных средств, транспортных работ или перевозок.
Особенности транспортной задачи
1) Все ограничения имеют вид равенств
2) Каждая переменная входит всего 2 ограничения.
3) Коэффициент при переменных в ограничениях =1
Решение задач ТЗЛП включает 2 основных этапа построение опорного решения (начального плана перевозок) и построение оптимального решения.
Построение опорного решения. Оно может быть получено методами северо-западного угла, наименьших стоимостей и двойного предпочтения. Наиболее простым и легко формализуемым является метод северо-западного угла, однако он даёт обычно решение, далёкое от оптимального. При построении опорного решения методами наименьших стоимостей и двойного предпочтения анализируется матрица затрат и начальный план обычно близок к оптимальному. Метод с-з угла используется, как правило, при расчётах на ПК. При его применении данные о стоимостях не нужны.
При использовании материалов активная ссылка на источник обязательна.