183746 (629921), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Вычисляем значение целевой функции на этом опорном решении F = 250·2+ 150·3 + 80·8 + 290·6 + 120·15 + 260·9 = 500 + 450 + 640 + 1740 + 1800 + 2340 = 7470.

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

Ui + Vj = Сij

Записываем систему уравнений для нахождения потенциалов:

U 1 + V1 = 2,

U1 + V2 = 4,

U1 + V5 = 3,

U2 + V2 = 8,

U2 + V3 = 6,

U3 + V2 = 15,

U3 + V4 = 9

Далее одному из потенциалов задаем значение произвольно: пусть U1 = 0. Остальные потенциалы находятся однозначно:

U 1 = 0,

V1 = 2, V2 = 4, V5 = 3

U2 = 8 - V2 = 4

U3 = 15 - V2 = 11

V4 = 9 - U3 = -2

V3 = 6 - U2 = 2

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

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

∆14 = U1 + V4 - С14 = 0 - 2 –11 = - 13,

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

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

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

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

∆33 = U3 + V3 – С33 = 11 + 2 – 7 = 6,

∆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.

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

U 1 + 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. Абрамов Л.M., Капустин В.Ф. Математическое программирование. ―Л., 1981.

2. Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.

3. Баумоль У. Экономическая теория и исследование операций. — М.: Прогресс, 1965.

4. Калихман И.Л. Линейная алгебра и программирование. — М.: Высш. шк.,1967.

5. Карасев А.И., Аксютина З.М., Савельева Т.И. Курс высшей математики для экономических вузов. Ч.II. Теория вероятностей и математическое программирование. Линейное программирование: Учеб. пособие для студентов вузов. ― М.: Высш. школа, 1982.

6. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. ― М.: Высш. шк., 1980.

7. Линейное программирование: Учебно-методическое пособие. ― М.: Изд-во МГУ, 1992.

8. Матвеев В.И., Сагитов Р.В., Шершнев В.Г. Курс линейного программирования для экономистов: Учеб. пособие. — М.: Менеджер, 1998.

9. Муртаф Б. Современное линейное программирование. — М.: Мир, 1984.

10. Общий курс высшей математики для экономистов :Учебник / Под ред. В.И. Ермакова. ― М.: ИНФА-М, 2002.

39

Характеристики

Список файлов курсовой работы