Курсовая работа: Математические методы в решении экономических задач

∆35 = U3 + V5 – С35 = 11 + 3 – 18 = - 4.

Начальное опорное решение не является оптимальным, так как имеются положительные оценки.

Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует наибольшая положительная оценка:

max{3, 6}=6 - для клетки (U3; V3).

Для этой клетки строим цикл.

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

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

Это перемещение производят по следующим правилам:

Каждой из клеток, связанных циклом с данной свободной клеткой приписывают определенный знак, причём свободной клетке – знак плюс, а всем остальным клеткам – поочередно знаки минус и плюс (таблица (1;1)).

В данную свободную клетку переносят меньшее из чисел, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим клеткам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел, считается свободной (таблица (1;2)).

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

Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным n + m – 1 = 3 + 5 – 1 = 7

X2 =  - опорное решение №2. Полученный новый опорный план проверяем на оптимальность.

Вычисляем значение целевой функции на втором опорном решении:

F = 250· 2 + 0·4+ 150·3+ 200·8+ 170·6 + 120·7 + 260·9 = 500 + 0 + 450 + 1600 + 1020 + 840 + 2340 = 6750.

Далее производим проверку оптимальности опорного решения:

U1 + V1 = 2,

U1 + V2 = 4,

U1 + V5 = 3,

U2 + V2 = 8,

U2 + V3 = 6,

U3 + V4 = 9.

U1 = 0,

V1 = 2, V2 = 4, V5 = 3

U2 = 8 - V2 = 4

V3 = 6 - U2 = 2

U3 = 7 – V3 = 5

V4 = 9 - U3 = 4

Проверяем опорное решение Х2 на оптимальность. С этой целью вычисляем оценки  для всех незаполненных клеток таблицы.

∆13 = U1 + V3 - С13 = 0 + 2 – 5 = - 3,

∆14 = U1 + V4 - С14 = 0 + 4 –11 = - 7,

∆21 = U2 + V1 – С21 = 4 + 2 – 12 = - 6,

∆24 = U2 + V4 – С24 = 4 + 4 – 14 = - 6,

∆25 = U2 + V5 – С25 = 4 + 3 – 11 = - 4,

∆31 = U3 + V1 – С31 = 5 + 2 – 10 = - 3,

∆35 = U3 + V5 – С35 = 5 + 4 – 18 = - 9.

Ответ: общая минимальная стоимость перевозок равна F min = 6750ден.ед при решении

Х2 =  .

Заключение

В результате проделанной работы изучено несколько методов решения задачи линейного программирования, а именно графический, симплекс-метод (аналитический и табличный) для прямой и двойственной задачи линейного программирования, а также изучена транспортная задача.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10