БИЛЕТ 18 ВОПРОС 2 Свойства множества решений в задаче ЛП.

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

- система Ур-й несовместна, те не имеет ниодного решения

- имеет единств решение, но хотяб одна перем имеет отриц знач

- система имеет единств неотриц решение

- беск множ-во неотриц решений

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

БИЛЕТ 19 ВОПРОС 2 Структура сетевой модели

Сетевая модель или сеть - это график , составленный из вершин - событий и напвленных дуг - работ или операций.

i -> j -> k , i -> k

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

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

Каждая работа в модели однозначно определяется начальным и конечным событием (i,j) - работа с начальным событием i и конечным событием j.

В сети не должно быть:

1) петель , т.е. одно и тоже событие не может быть начальным и конечным событием работы.

2) 2 работы , имеющих общее начало и общее конечное событие.

Работа в сети и модели может означать:

1) действит работа - реальный процесс , требующий затрат времени и ресурсов

2) ожидание - процесс , имеющий длительность , но не требующий ресурсов

3) фиктивные работы. Если событие i и j сведены фиктивной работой , то событие j наступит только после свершения события i. Фиктивные работы имеют нулевые длительность и расход ресурсов.

БИЛЕТ 20 ВОПРОС 1Модель транспортной задачи ЛП.

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

Формулировка задачи:

Имеется n поставщиков одного груза, i-тый поставщик имеет запас груза ai (i=1,2 n) и m потребителей, j-тый потребитель имеет потребность в грузе bj (j=1,2 m). Затра ты на перевозку груза от i-поставщика к j-потребителю составляют cij . Требуется определить объёмы грузоперевозок от i-поставщика к j-потребителю хij , при которых достигается минимальная суммарная стоимость перевозок W=Eni=1Emj=1cij xij ->min

При этом весь запас груза должен быть вывезен: