Решить задачу линейного программирования распределительным методом, начальное опорное решение, заполнив методом северо-западного угла (диагональным методом).
1. Записать экономико-математическую модель задачи.
2. Из последней таблицы записать полученное оптимальное решение.
Ответ
Х опт=4000030003005005000, Z max=56600
Решение
1)Математическая модель транспортной задачи: Z = ∑∑cijxij, (1) при условиях: ∑xij = ai, i = 1,2,…, m, (2) ∑xij = bj, j = 1,2,…, n, (3) xij ≥ 0 Запишем экономико-математическую модель для нашей задачи. Переменные: x11 – площадь посева овса в 1-ом типе почвы. x12 – площадь посева овса в 2-ом типе почвы. x13 – площадь посева овса в 3-ем типе почвы. x21 – площадь посева ячменя в 1-ом типе почвы. x22 – площадь посева ячменя в 2-ом типе почвы. x23 – площадь посева ячменя в 3-ем типе почвы. x31 – площадь посева пшеницы в 1-ом типе почвы. x32 – площадь посева пшеницы в 2-ом типе почвы. x33 – площадь посева пшеницы в 3-ем типе почвы. Ограничения по запасам: x11 + x12 + x13 ≤ 400 (для овса) x21 + x22 + x23 ≤ 600 (для ячменя) x31 + x32 + x33 ≤ 1000 (для пшеницы) Ограничения по потребностям: x11 + x21 + x31 = 1200 (для 1-го типа почвы) x12 + x22 + x32 = 500 (для 2-го типа почвы) x13 + x23 + x33 = 300 (для 3-го типа почвы) Целевая функция: Z=30x11 + 27x12 + 29x13 + 27x21 + 28x22 + 30x23 + 25x31 + 30x32 + 27x33 → mаx
2) Так как ∑ a = 400 + 600 + 1000 = 2000 ∑ b = 1200 + 500 + 300 = 2000 модель транспортной задачи является закрытой.
Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
1 2 3
овес 30[400] 27 29 400
ячмень 27[600] 28 30 600
пшеница 25[200] 30[500] 27[300] 1000
1200 500 300
Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5
. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: Z(x) = 30*400 + 27*600 + 25*200 + 30*500 + 27*300 = 56300
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 30; 0 + v1 = 30; v1 = 30 u2 + v1 = 27; 30 + u2 = 27; u2 = -3 u3 + v1 = 25; 30 + u3 = 25; u3 = -5 u3 + v2 = 30; -5 + v2 = 30; v2 = 35 u3 + v3 = 27; -5 + v3 = 27; v3 = 32
v1=30 v2=35 v3=32
u1=0 30[400] 27 29
u2=-3 27[600] 28 30
u3=-5 25[200] 30[500] 27[300]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых l= cij-( ui + vj ) меньше нуля(1;2): ∆12 = -8 (1;3): ∆13 = - 3 (2;2): ∆22 = -4 Выбираем максимальную оценку свободной клетки (1;2): 27 Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 Запасы
1 30[400][-] 27[+] 29 400
2 27[600] 28 30 600
3 25[200][+] 30[500][-] 27[300] 1000
Потребности 1200 500 300
Цикл приведен в таблице (1,2 → 1,1 → 3,1 → 3,2). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
