Математические методы в решении экономических задач (стр. 6 из 6)

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

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

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

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

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

250	200	290	260	150
V1	V2	V3	V4	V5
400	U1	2502	04	5	11	150 3
370	U2	12	2008	1706	14	11
380	U3	10	15	1207	2609	18

Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным 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. Абрамов Л.M., Капустин В.Ф. Математическое программирование. ―Л., 1981.

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

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

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

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

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

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

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

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

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