Симплекс-метод

Решение задач графически и симплекс-методом. Экономическое толкование полученных решений. Решение двойственной задачи для оптимальной системы оценок ресурсов. Определение дефицитных и недефицитных ресурсов. Обоснование эффективности оптимального плана.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Подобные документы

Главная Коллекция "Otherreferats" Экономико-математическое моделирование Симплекс-метод

Рубрика	Экономико-математическое моделирование
Вид	контрольная работа
Язык	русский
Дата добавления	13.09.2015
Размер файла	226,7 K

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*30 + 2*20 + 3*5 + 1*35 + 4*20 = 260

Искомый элемент равен 2

Для этого элемента запасы равны 50, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₁₂ = min(50,25) = 25.

3	2	4	1	50 - 25 = 25
2	x	1	5	40
3	x	7	4	20
30	25 - 25 = 0	35	20	0

Искомый элемент равен 3

Для этого элемента запасы равны 25, потребности 30. Поскольку минимальным является 25, то вычитаем его.

x₁₁ = min(25,30) = 25.

3	2	x	x	25 - 25 = 0
2	x	1	5	40
3	x	7	4	20
30 - 25 = 5	0	35	20	0

Искомый элемент равен 2

Для этого элемента запасы равны 40, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₂₁ = min(40,5) = 5.

3	2	x	x	0
2	x	1	5	40 - 5 = 35
x	x	7	4	20
5 - 5 = 0	0	35	20	0

Искомый элемент равен 1

Для этого элемента запасы равны 35, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x₂₃ = min(35,35) = 35.

3	2	x	x	0
2	x	1	x	35 - 35 = 0
x	x	x	4	20
0	0	35 - 35 = 0	20	0

Искомый элемент равен 4

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₄ = min(20,20) = 20.

3	2	x	x	0
2	x	1	x	0
x	x	x	4	20 - 20 = 0
0	0	0	20 - 20 = 0	0

2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 6. Следовательно, опорный план является вырожденным.

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*25 + 2*25 + 2*5 + 1*35 + 4*20 = 250

Искомый элемент равен 4

Для этого элемента запасы равны 50, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x₁₃ = min(50,35) = 35.

3	2	4	1	50 - 35 = 15
2	3	x	5	40
3	2	x	4	20
30	25	35 - 35 = 0	20	0

Искомый элемент равен 3

Для этого элемента запасы равны 15, потребности 30. Поскольку минимальным является 15, то вычитаем его.

x₁₁ = min(15,30) = 15.

3	x	4	x	15 - 15 = 0
2	3	x	5	40
3	2	x	4	20
30 - 15 = 15	25	0	20	0

Искомый элемент равен 2

Для этого элемента запасы равны 40, потребности 15. Поскольку минимальным является 15, то вычитаем его.

x₂₁ = min(40,15) = 15.

3	x	4	x	0
2	3	x	5	40 - 15 = 25
x	2	x	4	20
15 - 15 = 0	25	0	20	0

Искомый элемент равен 3

Для этого элемента запасы равны 25, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₂₂ = min(25,25) = 25.

3	x	4	x	0
2	3	x	x	25 - 25 = 0
x	x	x	4	20
0	25 - 25 = 0	0	20	0

Искомый элемент равен 4

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₄ = min(20,20) = 20.

3	x	4	x	0
2	3	x	x	0
x	x	x	4	20 - 20 = 0
0	0	0	20 - 20 = 0	0

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*15 + 4*35 + 2*15 + 3*25 + 4*20 = 370

Искомый элемент равен 1

Для этого элемента запасы равны 50, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₁₄ = min(50,20) = 20.

3	2	4	1	50 - 20 = 30
2	3	1	x	40
3	2	7	x	20
30	25	35	20 - 20 = 0	0

Искомый элемент равен 3

Для этого элемента запасы равны 30, потребности 30. Поскольку минимальным является 30, то вычитаем его.

x₁₁ = min(30,30) = 30.

3	x	x	1	30 - 30 = 0
x	3	1	x	40
x	2	7	x	20
30 - 30 = 0	25	35	0	0

Искомый элемент равен 3

Для этого элемента запасы равны 40, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₂₂ = min(40,25) = 25.

3	x	x	1	0
x	3	1	x	40 - 25 = 15
x	x	7	x	20
0	25 - 25 = 0	35	0	0

Искомый элемент равен 1

Для этого элемента запасы равны 15, потребности 35. Поскольку минимальным является 15, то вычитаем его.

x₂₃ = min(15,35) = 15.

3	x	x	1	0
x	3	1	x	15 - 15 = 0
x	x	7	x	20
0	0	35 - 15 = 20	0	0

Искомый элемент равен 7

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₃ = min(20,20) = 20.

3	x	x	1	0
x	3	1	x	0
x	x	7	x	20 - 20 = 0
0	0	20 - 20 = 0	0	0

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*30 + 1*20 + 3*25 + 1*15 + 7*20 = 340

Искомый элемент равен 2

Для этого элемента запасы равны 40, потребности 30. Поскольку минимальным является 30, то вычитаем его.

x₂₁ = min(40,30) = 30.

x	2	4	1	50
2	3	1	5	40 - 30 = 10
x	2	7	4	20
30 - 30 = 0	25	35	20	0

Искомый элемент равен 2

Для этого элемента запасы равны 50, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₁₂ = min(50,25) = 25.

x	2	4	1	50 - 25 = 25
2	x	1	5	10
x	x	7	4	20
0	25 - 25 = 0	35	20	0

Искомый элемент равен 4

Для этого элемента запасы равны 25, потребности 35. Поскольку минимальным является 25, то вычитаем его.

x₁₃ = min(25,35) = 25.

x	2	4	x	25 - 25 = 0
2	x	1	5	10
x	x	7	4	20
0	0	35 - 25 = 10	20	0

Искомый элемент равен 1

Для этого элемента запасы равны 10, потребности 10. Поскольку минимальным является 10, то вычитаем его.

x₂₃ = min(10,10) = 10.

x	2	4	x	0
2	x	1	x	10 - 10 = 0
x	x	x	4	20
0	0	10 - 10 = 0	20	0

Искомый элемент равен 4

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₄ = min(20,20) = 20.

x	2	4	x	0
2	x	1	x	0
x	x	x	4	20 - 20 = 0
0	0	0	20 - 20 = 0	0

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 2*25 + 4*25 + 2*30 + 1*10 + 4*20 = 300

Искомый элемент равен 3

Для этого элемента запасы равны 40, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₂₂ = min(40,25) = 25.

3	x	4	1	50
2	3	1	5	40 - 25 = 15
3	x	7	4	20
30	25 - 25 = 0	35	20	0

Искомый элемент равен 3

Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его.

x₁₁ = min(50,30) = 30.

3	x	4	1	50 - 30 = 20
x	3	1	5	15
x	x	7	4	20
30 - 30 = 0	0	35	20	0

Искомый элемент равен 4

Для этого элемента запасы равны 20, потребности 35. Поскольку минимальным является 20, то вычитаем его.

x₁₃ = min(20,35) = 20.

3	x	4	x	20 - 20 = 0
x	3	1	5	15
x	x	7	4	20
0	0	35 - 20 = 15	20	0

Искомый элемент равен 1

Для этого элемента запасы равны 15, потребности 15. Поскольку минимальным является 15, то вычитаем его.

x₂₃ = min(15,15) = 15.

3	x	4	x	0
x	3	1	x	15 - 15 = 0
x	x	x	4	20
0	0	15 - 15 = 0	20	0

Искомый элемент равен 4

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₄ = min(20,20) = 20.

3	x	4	x	0
x	3	1	x	0
x	x	x	4	20 - 20 = 0
0	0	0	20 - 20 = 0	0

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*30 + 4*20 + 3*25 + 1*15 + 4*20 = 340

Искомый элемент равен 1

Для этого элемента запасы равны 40, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x₂₃ = min(40,35) = 35.

3	2	x	1	50
2	3	1	5	40 - 35 = 5
3	2	x	4	20
30	25	35 - 35 = 0	20	0

Искомый элемент равен 3

Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его.

x₁₁ = min(50,30) = 30.

3	2	x	1	50 - 30 = 20
x	3	1	5	5
x	2	x	4	20
30 - 30 = 0	25	0	20	0

Искомый элемент равен 2

Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.

x₁₂ = min(20,25) = 20.

3	2	x	x	20 - 20 = 0
x	3	1	5	5
x	2	x	4	20
0	25 - 20 = 5	0	20	0

Искомый элемент равен 3

Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₂₂ = min(5,5) = 5.

3	2	x	x	0
x	3	1	x	5 - 5 = 0
x	x	x	4	20
0	5 - 5 = 0	0	20	0

Искомый элемент равен 4

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₄ = min(20,20) = 20.

3	2	x	x	0
x	3	1	x	0
x	x	x	4	20 - 20 = 0
0	0	0	20 - 20 = 0	0

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*30 + 2*20 + 3*5 + 1*35 + 4*20 = 260

Искомый элемент равен 5

Для этого элемента запасы равны 40, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₂₄ = min(40,20) = 20.

3	2	4	x	50
2	3	1	5	40 - 20 = 20
3	2	7	x	20
30	25	35	20 - 20 = 0	0

Искомый элемент равен 3

Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его.

x₁₁ = min(50,30) = 30.

3	2	4	x	50 - 30 = 20
x	3	1	5	20
x	2	7	x	20
30 - 30 = 0	25	35	0	0

Искомый элемент равен 2

Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.

x₁₂ = min(20,25) = 20.

3	2	x	x	20 - 20 = 0
x	3	1	5	20
x	2	7	x	20
0	25 - 20 = 5	35	0	0

Искомый элемент равен 3

Для этого элемента запасы равны 20, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₂₂ = min(20,5) = 5.

3	2	x	x	0
x	3	1	5	20 - 5 = 15
x	x	7	x	20
0	5 - 5 = 0	35	0	0

Искомый элемент равен 1

Для этого элемента запасы равны 15, потребности 35. Поскольку минимальным является 15, то вычитаем его.

x₂₃ = min(15,35) = 15.

3	2	x	x	0
x	3	1	5	15 - 15 = 0
x	x	7	x	20
0	0	35 - 15 = 20	0	0

Искомый элемент равен 7

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₃ = min(20,20) = 20.

3	2	x	x	0
x	3	1	5	0
x	x	7	x	20 - 20 = 0
0	0	20 - 20 = 0	0	0

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

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*30 + 2*20 + 3*5 + 1*15 + 5*20 + 7*20 = 400

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₂ + v₂ = 3; 2 + u₂ = 3; u₂ = 1

u₂ + v₃ = 1; 1 + v₃ = 1; v₃ = 0

u₃ + v₃ = 7; 0 + u₃ = 7; u₃ = 7

u₂ + v₄ = 5; 1 + v₄ = 5; v₄ = 4

	v₁=3	v₂=2	v₃=0	v₄=4
u₁=0	3[30]	2[20]	4	1
u₂=1	2	3[5]	1[15]	5[20]
u₃=7	3	2	7[20]	4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;4): 0 + 4 > 1; ?₁₄ = 0 + 4 - 1 = 3

(2;1): 1 + 3 > 2; ?₂₁ = 1 + 3 - 2 = 2

(3;1): 7 + 3 > 3; ?₃₁ = 7 + 3 - 3 = 7

(3;2): 7 + 2 > 2; ?₃₂ = 7 + 2 - 2 = 7

(3;4): 7 + 4 > 4; ?₃₄ = 7 + 4 - 4 = 7

max(3,2,7,7,7) = 7

Выбираем максимальную оценку свободной клетки (3;1): 3

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (3,1 > 3,3 > 2,3 > 2,2 > 1,2 > 1,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₃ + v₁ = 3; 3 + u₃ = 3; u₃ = 0

u₃ + v₃ = 7; 0 + v₃ = 7; v₃ = 7

u₂ + v₃ = 1; 7 + u₂ = 1; u₂ = -6

u₂ + v₄ = 5; -6 + v₄ = 5; v₄ = 11

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

	v₁=3	v₂=2	v₃=7	v₄=11
u₁=0	3[25]	2[25]	4	1
u₂=-6	2	3	1[20]	5[20]
u₃=0	3[5]	2	7[15]	4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;3): 0 + 7 > 4; ?₁₃ = 0 + 7 - 4 = 3

(1;4): 0 + 11 > 1; ?₁₄ = 0 + 11 - 1 = 10

(3;4): 0 + 11 > 4; ?₃₄ = 0 + 11 - 4 = 7

max(3,10,7) = 10

Выбираем максимальную оценку свободной клетки (1;4): 1

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (1,4 > 1,1 > 3,1 > 3,3 > 2,3 > 2,4).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₃ + v₁ = 3; 3 + u₃ = 3; u₃ = 0

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

u₂ + v₄ = 5; 1 + u₂ = 5; u₂ = 4

u₂ + v₃ = 1; 4 + v₃ = 1; v₃ = -3

	v₁=3	v₂=2	v₃=-3	v₄=1
u₁=0	3[10]	2[25]	4	1[15]
u₂=4	2	3	1[35]	5[5]
u₃=0	3[20]	2	7	4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(2;1): 4 + 3 > 2; ?₂₁ = 4 + 3 - 2 = 5

(2;2): 4 + 2 > 3; ?₂₂ = 4 + 2 - 3 = 3

max(5,3) = 5

Выбираем максимальную оценку свободной клетки (2;1): 2

Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (2,1 > 2,4 > 1,4 > 1,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₂ + v₁ = 2; 3 + u₂ = 2; u₂ = -1

u₂ + v₃ = 1; -1 + v₃ = 1; v₃ = 2

u₃ + v₁ = 3; 3 + u₃ = 3; u₃ = 0

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

	v₁=3	v₂=2	v₃=2	v₄=1
u₁=0	3[5]	2[25]	4	1[20]
u₂=-1	2[5]	3	1[35]	5
u₃=0	3[20]	2	7	4

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Минимальные затраты составят:

F(x) = 3*5 + 2*25 + 1*20 + 2*5 + 1*35 + 3*20 = 190

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (5), в 2-й магазин (25), в 4-й магазин (20)

Из 2-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (35)

Из 3-го склада необходимо весь груз направить в 1-й магазин

Метод минимального элемента

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.

Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Искомый элемент равен 1

Для этого элемента запасы равны 50, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₁₄ = min(50,20) = 20.

3	2	4	1	50 - 20 = 30
2	3	1	x	40
3	2	7	x	20
30	25	35	20 - 20 = 0	0

Искомый элемент равен 1

Для этого элемента запасы равны 40, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x₂₃ = min(40,35) = 35.

3	2	x	1	30
2	3	1	x	40 - 35 = 5
3	2	x	x	20
30	25	35 - 35 = 0	0	0

Искомый элемент равен 2

Для этого элемента запасы равны 30, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₁₂ = min(30,25) = 25.

3	2	x	1	30 - 25 = 5
2	x	1	x	5
3	x	x	x	20
30	25 - 25 = 0	0	0	0

Искомый элемент равен 2

Для этого элемента запасы равны 5, потребности 30. Поскольку минимальным является 5, то вычитаем его.

x₂₁ = min(5,30) = 5.

3	2	x	1	5
2	x	1	x	5 - 5 = 0
3	x	x	x	20
30 - 5 = 25	0	0	0	0

Искомый элемент равен 3

Для этого элемента запасы равны 5, потребности 25. Поскольку минимальным является 5, то вычитаем его.

x₁₁ = min(5,25) = 5.

3	2	x	1	5 - 5 = 0
2	x	1	x	0
3	x	x	x	20
25 - 5 = 20	0	0	0	0

Искомый элемент равен 3

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₁ = min(20,20) = 20.

3	2	x	1	0
2	x	1	x	0
3	x	x	x	20 - 20 = 0
20 - 20 = 0	0	0	0	0

Значение целевой функции для этого опорного плана равно:

F(x) = 3*5 + 2*25 + 1*20 + 2*5 + 1*35 + 3*20 = 190

Этап II. Улучшение опорного плана.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₂ + v₁ = 2; 3 + u₂ = 2; u₂ = -1

u₂ + v₃ = 1; -1 + v₃ = 1; v₃ = 2

u₃ + v₁ = 3; 3 + u₃ = 3; u₃ = 0

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

	v₁=3	v₂=2	v₃=2	v₄=1
u₁=0	3[5]	2[25]	4	1[20]
u₂=-1	2[5]	3	1[35]	5
u₃=0	3[20]	2	7	4

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Минимальные затраты составят:

F(x) = 3*5 + 2*25 + 1*20 + 2*5 + 1*35 + 3*20 = 190

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (5), в 2-й магазин (25), в 4-й магазин (20)

Из 2-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (35)

Из 3-го склада необходимо весь груз направить в 1-й магазин

Метод двойного предпочтения

Этап I. Поиск первого опорного плана.

1. Используя метод двойного предпочтения, построим первый опорный план транспортной задачи. В каждой строке находим минимальный элемент. Ставим напротив него знак V. Затем находим минимальный элемент каждого столбца. Ставим напротив него знак V.

Если таблица стоимостей велика, то перебор всех элементов затруднителен. В этом случае используют метод двойного предпочтения, суть которого заключается в следующем.

В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку VV.

В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки.

Затем распределяют перевозки по ячейкам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

Искомый элемент находится в клетке (2;3) и равен 1.

	1	2	3	4
1	3	2	4	1[VV]
2	2[V]	3	1[VV]	5
3	3	2[V]	7	4

Искомый элемент равен 1

Для этого элемента запасы равны 40, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x₂₃ = min(40,35) = 35.

3	2	x	1	50
2	3	1	5	40 - 35 = 5
3	2	x	4	20
30	25	35 - 35 = 0	20	0

Искомый элемент находится в клетке (2;1) и равен 2.

	1	2	3	4
1	3	2	4	1[VV]
2	2[VV]	3	1	5
3	3	2[V]	7	4

Искомый элемент равен 2

Для этого элемента запасы равны 5, потребности 30. Поскольку минимальным является 5, то вычитаем его.

x₂₁ = min(5,30) = 5.

3	2	x	1	50
2	x	1	x	5 - 5 = 0
3	2	x	4	20
30 - 5 = 25	25	0	20	0

Искомый элемент находится в клетке (3;1) и равен 3.

	1	2	3	4
1	3	2	4	1[VV]
2	2	3	1	5
3	3[VV]	2[V]	7	4

Искомый элемент равен 3

Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.

x₃₁ = min(20,25) = 20.

3	2	x	1	50
2	x	1	x	0
3	x	x	x	20 - 20 = 0
25 - 20 = 5	25	0	20	0

Искомый элемент находится в клетке (1;4) и равен 1.

	1	2	3	4
1	3[VV]	2[VV]	4	1[VV]
2	2	3	1	5
3	3	2	7	4

Искомый элемент равен 1

Для этого элемента запасы равны 50, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₁₄ = min(50,20) = 20.

3	2	x	1	50 - 20 = 30
2	x	1	x	0
3	x	x	x	0
5	25	0	20 - 20 = 0	0

Искомый элемент находится в клетке (1;1) и равен 3.

	1	2	3	4
1	3[VV]	2[V]	4	1
2	2	3	1	5
3	3	2	7	4

Искомый элемент равен 3

Для этого элемента запасы равны 30, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₁₁ = min(30,5) = 5.

3	2	x	1	30 - 5 = 25
2	x	1	x	0
3	x	x	x	0
5 - 5 = 0	25	0	0	0

Искомый элемент находится в клетке (1;2) и равен 2.

	1	2	3	4
1	3	2[V]	4	1
2	2	3	1	5
3	3	2	7	4

Искомый элемент равен 2

Для этого элемента запасы равны 25, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₁₂ = min(25,25) = 25.

3	2	x	1	25 - 25 = 0
2	x	1	x	0
3	x	x	x	0
0	25 - 25 = 0	0	0	0

Значение целевой функции для этого опорного плана равно:

F(x) = 3*5 + 2*25 + 1*20 + 2*5 + 1*35 + 3*20 = 190

Этап II. Улучшение опорного плана.

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

u₂ + v₁ = 2; 3 + u₂ = 2; u₂ = -1

u₂ + v₃ = 1; -1 + v₃ = 1; v₃ = 2

u₃ + v₁ = 3; 3 + u₃ = 3; u₃ = 0

u₁ + v₂ = 2; 0 + v₂ = 2; v₂ = 2

u₁ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

	v₁=3	v₂=2	v₃=2	v₄=1
u₁=0	3[5]	2[25]	4	1[20]
u₂=-1	2[5]	3	1[35]	5
u₃=0	3[20]	2	7	4

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Минимальные затраты составят:

F(x) = 3*5 + 2*25 + 1*20 + 2*5 + 1*35 + 3*20 = 190

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (5), в 2-й магазин (25), в 4-й магазин (20)

Из 2-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (35)

Из 3-го склада необходимо весь груз направить в 1-й магазин

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ:

Вагнер. Вступление в исследование операций. - М.: Мир, 1973

Грубер И. Економетрія. - К.: Астарта, 1996 - Т1.

Зайченко Ю.П., Шумилова С.А., Исследование операций. Сб. задач. - К.: Вища шк., 1990

Зайченко Ю.П. Исследование операций. - К.: Вища шк., 1990 р.

Калихман И.Л., Сборник задач по математическому программированию. - М.: Высш. шк., 1975

Крушевский А.В., Довідник по економіко-математичному моделюванню. - К.: Техника, 1982

Кузнєцов Ю.Н., Кузубов В.И., Волощенко А.Б., Математичне програмування. - М.: Вища шк., 1976

Мирошник М.М., Економико-математические методы и модели в планировании и управлении материально-техничним обеспечением. - М.: - Вища шк., 1999

Невелівши А.М., Прогнозування й планування матеріальних ресурсів. - К.: Техніка, 1975

Размещено на Allbest.ru

Страница:

контрольная работа "Симплекс-метод" скачать

Потребности

Применение графического метода и симплекс-метода для решения задач линейного программирования
Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.

контрольная работа [398,2 K], добавлен 15.08.2012
Оптимизация плана производства
Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.

курсовая работа [458,6 K], добавлен 10.12.2013
Линейное программирование
Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.

контрольная работа [467,8 K], добавлен 13.06.2012
Исследование операций
Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.

курсовая работа [54,1 K], добавлен 05.03.2010
Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.

контрольная работа [367,5 K], добавлен 11.05.2014
Оптимизация ипользования ресурсов
Исследование задачи оптимизации ресурсов при планировании товарооборота торгового предприятия в общем виде. Формирование математической модели задачи. Решение симплекс-методом. Свободные члены системы ограничений и определение главных требований к ним.

курсовая работа [68,6 K], добавлен 21.06.2011
Решение задачи линейного программирования симплекс-методом
Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.

реферат [193,4 K], добавлен 28.12.2008
Определение оптимальных значений вероятности событий
Решение задачи линейного программирования симплекс-методом. План перевозок при минимальных затратах на них. Определение оптимального значения изменения численности работников. Решение матричной игры двух лиц с применением чистой и смешанной стратегий.

контрольная работа [152,3 K], добавлен 16.05.2013
Математические методы принятия управленческих решений
Расчет задачи линейного программирования вручную симплекс методом и машинным способом в Ms Excel с применением электронной таблицы. Сравнение полученных результатов с ручным решением. Математическая модель двойственной задачи с пояснениями результатов.

контрольная работа [1,4 M], добавлен 31.03.2012
Определение оптимального плана движения морских судов симплекс-методом
Характеристика направлений перевозок и флота. Расчет нормативов работы судов на схемах движения. Составление математической модели задачи. Нахождение оптимального плана работы флота и оптимальных схем движения судов, построение симплекс таблицы.

курсовая работа [1,4 M], добавлен 24.10.2012

Другие документы, подобные "Симплекс-метод"

весь список подобных работ

скачать работу можно здесь

сколько стоит заказать работу?

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.