Какие задачи относят к задачам линейного программирования?

Транспортная задача

Какова постановка стандартной транспортной задачи?

Классическая транспортная задача (Т3) формулируется следующим

образом:

Имеются m пунктов отправления (ПО) А1, А2...Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно a1, a2,…, am единиц. Имеются n пунктов назначения (ПН) B1, B2,...., Bn, подавших заявки соответственно на bi, b2,..., bn единиц груза. Известны стоимости (или расстояния) cij перевозки единицы груза из каждого пункта отправления Аi, i =1,2,..., m, до каждого пункта назначения Bj, j = 1,2, …, n. Все числа Сij можно представить в виде матрицы стоимостей (или расстояний).

Будем считать, что стоимость перевозки нескольких единиц груза

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

Что такое градиент?

Градиент - вектор, указывающий на направление максимального возрастания функции.

Поясните, в чем заключается метод потенциалов?

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

Указанный недостаток распределительного метода реализуется в методе потенциалов, который позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций (повторений действий)

Поясните, в чем заключается метод минимального элемента?

В результате применения метода минимального элемента получим план перевозок X = (Xij), состоящий не более чем из (m + n – l) перевозок.

Что такое распределительный метод?

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

Опишите, что такое транспортная задача?

Транспортная задача (Т3) возникает при планировании рациональных перевозок грузов, загрузки оборудования и других организационно-экономических процессов, в различных областях деятельности человека. Медицина и здравоохранение не исключение.

Перечислите этапы построения решения транспортной задачи.

После того, как построена математическая модель транспортной задачи, переходим к ее решению, которое можно разбить на несколько этапов:

1) построение транспортной таблицы;

2) определение исходного опорного решения;

3) построение последовательных итераций-приближений к оптимальному решению

11. Какие клетки являются базисными в транспортной таблице?

      Базисными клетками транспортной таблицы являются клетки,      

      соответствующие базисным переменным, а остальные клетки –         

       свободные.

12.Что такое вырожденный план?

Если план задачи включает меньше чем (m + n – 1)

положительных переменных, то он называется вырожденным планом, а если число ненулевых перевозок равно (m + n – 1), то невырожденным

Для чего необходимо изучение методов оптимизации и транспортной задачи в медицине?

для планирования рациональных перевозок грузов, загрузки оборудования и других организационно-экономических процессов, в различных областях деятельности человека. Медицина и здравоохранение не исключение.

 

Раскройте понятие сбалансированности транспортной задачи.

Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется сбалансированной (закрытой).

 

Какие условия должны соблюдаться для сбалансированной транспортной задачи?

1. Сумма всех заявок равна сумме всех запасов.

 

2. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте.

 

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