Математическое программирование, базы данных, ПО

10) построить вектор n (с1, с2) по коэффициентам целевой функции f = c1x1 + c2x2;

11) в семействе параллельных прямых целевой функции выделить одну, например, через начало координат;

12) перемещать прямую целевой функции параллельно самой себе по области решения, достигая max f при движении вектора n и min f при движении в противоположном направлении.

13) найти координаты точек max и min по чертежу и вычислить значения функции в этих точках (ответы).

14). Постановка транспортной задачи.

Приведем экономическую формулировку транспортной задачи по критерию стоимости: Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2,…, Аm соответственно в количествах а1, а2,…, аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2,…, Вn соответственно в количествах b1, b2,…, bn единиц. Стоимость перевозки (тариф) единицы продукта из Ai в Bj известна для всех маршрутов AiBj и равна Cij (i=1, m; j=1, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозиться и запросы всех пунктов потребления удовлетворяются (закрытая модель), а суммарные транспортные расходы минимальны.

Условия задачи удобно располагать в таблицу, вписывая в клетки количество перевозимого груза из Ai в Bj груза Xij > 0, а в маленькие клетки соответствующие тарифы Cij: 8. Математическая модель транспортной задачи.

Из предыдущей таблицы легко усматривается и составляется математическая модель транспортной задачи для закрытой модели Число r = m + n — 1, равное рангу системы (1), называется рангом транспортной задачи. Если число заполненных клеток (Xij ¹ 0) в таблице равно r, то план называется невырожденным, а если это число меньше r, то план вырожденный — в этом случае в некоторые клетки вписывается столько нулей (условно заполненные клетки), чтобы общее число заполненных клеток было равно r.

Случай открытой модели Σаi ¹ Σbj легко сводится к закрытой модели путем введения фиктивного потребителя Bn+1 c потребностью bn+1=Σai-Σbj, λθαξ - фиктивного поставщика Аm+1 c запасом am+1=Σbj-Σai; οπθ ύтом тарифы фиктивных участников принимаются равными 0.

9. Способы составления 1-таблицы (опорного плана).

X. Способ северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью вывозиться груз из Аi, либо полностью удовлетворяется потребность Bj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы ai и не удовлетворяются потребности bj. В заключение проверяют, что найденные компоненты плана Xij удовлетворяют горизонтальным и вертикальным уравнениям и что выполняется условие невырожденности плана.