Решение задач линейного программирования различными методами (стр. 2 из 3)

Найти программу максимального выпуска продукции.

Таблица 5.

факторы	Способ производства					Ресурсы, грн
1	2	3	4	5		Ресурсы, грн
Сырье	12	15	10	12	11	1300
Эл.энергия	0,2	0,1	0,2	0,25	0,3	30
Зарплата	3	4	5	4	2	400
Накладные расходы	6	5	4	6	4	800

Математическая интерпретация задачи

Исходные массивы, записанные в виде, пригодном для решения задачи по программе SIMC

12.000 15.000 10.000 12.000 11.000 < 1300.000

0.200 0.100 0.200 0.250 0.300 < 30.000

3.000 4.000 5.000 4.000 2.000 < 400.000

6.000 5.000 4.000 6.000 4.000 < 800.000

300.000 260.000 320.000 400.000 450.000

Распечатка ЭВМ в результатом решения

ИТЕРАЦИЯ N=1 РЕШЕНИЕ НАЙДЕНО !!!

ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 2 3 4 5

6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000

7 0.000 30.000 0.200 0.100 0.200 0.250 0.300

8 0.000 400.000 3.000 4.000 5.000 4.000 2.000

9 0.000 800.000 6.000 5.000 4.000 6.000 4.000

0.000 300.000 260.000 320.000 400.000 450.000

КОД ОШИБКИ=0

ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ

ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 0.0000

ИТЕРАЦИЯ N=1 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 2 3 4 5

6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000

7 0.000 30.000 0.200 0.100 0.200 0.250 0.300

8 0.000 400.000 3.000 4.000 5.000 4.000 2.000

9 0.000 800.000 6.000 5.000 4.000 6.000 4.000

0.000 -300.000 -260.000 -320.000 -400.000 -450.000

В БАЗИС ВВОДИТСЯ 5 СТОЛБЕЦ

ИЗ БАЗИСА ВЫВОДИТСЯ 7 СТОЛБЕЦ

ИТЕРАЦИЯ N=2 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 2 3 4 7

6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667

5 450.000 100.000 0.667 0.333 0.667 0.833 3.333

8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667

9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333

45000.000 -0.000 -110.000 -20.000 -25.000 1500.000

В БАЗИС ВВОДИТСЯ 2 СТОЛБЕЦ

ИЗ БАЗИСА ВЫВОДИТСЯ 6 СТОЛБЕЦ

ИТЕРАЦИЯ N=3 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 3 4 6 7

2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235

5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412

8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118

9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471

46941.176 45.294 5.882 2.500 9.706 1144.118

КОД ОШИБКИ=0

ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ

X2=17.6471

X5=94.1176

ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 46941.1765

РЕШЕНИЕ НАЙДЕНО !!!

Оптимальный план. Экономическая интерпретация оптимального решения. В соответствии с полученным результатом выпуск продукции по 1,3 и 4 технологическим процессам нецелесообразен.

Задание 4

Моделирование транспортных задач и их решение методом потенциалов

Цель задания: приобрести практические навыки моделирования и решения транспортной задачи ЛП методом потенциалов.

Индивидуальное задание

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

Таблица 6. 06 вариант транспортной задачи

Вид механизма	Себестоимость выполнения единицы работы механизма ,гр.				Количество единиц a_i механизмов
Вид механизма	B₁	B₂	B₃	B₄	Количество единиц a_i механизмов
A₁	11	4	3	1	15
A₂	6	8	9	7	10
A₃	4	8	4	2	35
Потребности b_j участков в механизмах	25	20	10	5

Математическая формулировка транспортной задачи

Пусть x_ij – количество единиц работы, выполненной механизмом вида a_i, на участке работы b_j.Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы:

при ограничениях:

; - все механизмы должны быть задействованы;

; - все участки должны быть загружены;

; - количество единиц работы не может быть отрицательным

Условие разрешимости задачи выполняется:

25+20+10+5=15+10+35; 60=60.

Исходный опорный план, составленный по методу северо-западного угла

Таблица 7

I	a_i
I	a_i	B₁	B₂	B₃	B₄
A₁	11	4 15	3	1	15
A₂	6 5	8 5	9	7	10
A₃	4 20	8	4 10	2 5	35
b_j	25	20	10	5

Решение транспортной задачи методом потенциалов

Итак, видно что в число занятых клеток следует ввести клетку (2,1).

Получим новый улучшенный план – таблица 8.

Таблица 8

I	a_i
I	a_i	B₁	B₂	B₃	B₄
A₁	11	4 15	3	1	15
A₂	6 5	8 5	9	7	10
A₃	4 20	8	4 10	5 5	35
b_j	25	20	10	5

Введём в число занятых клетку (1,4) . Получим новый улучшенный план – Таблица 9.

Таблица 9

I	a_i
I	a_i	B₁	B₂	B₃	B₄
A₁	11	4 10	3 5	1	15
A₂	6	8 10	9	7	10
A₃	4 25	8	4 5	2 5	35
b_j	25	20	10	5

Так как,

- то данный план является оптимальным и значение себестоимости по данному плану.

x₁₂=15; x₂₁=5; x₂₂=5; x₃₁=20;x₃₃=10; x₃₄=5.

Z=15*4+5*6+5*8+20*4+10*4+5*2=260.

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

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

Задание 5

Решение транспортной задачи на ЭВМ

Цель задания: приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2.

Индивидуальное задание:

Таблица 10. 06 вариант транспортной задачи

Вид механизма	Себестоимость выполнения единицы работы механизма ,гр.				Количество единиц a_i механизмов
Вид механизма	B₁	B₂	B₃	B₄	Количество единиц a_i механизмов
A₁	11	4	3	1	15
A₂	6	8	9	7	10
A₃	4	8	4	2	35
Потребности b_j участков в механизмах	25	20	10	5

Исходные массивы для решения транспортной задачи по программе TRAN2

Распечатка с ЭВМ с результатом решения

Оптимальный план транспортной задачи

x₁₂=15; x₂₁=5; x₂₂=5; x₃₁=20;x₃₃=10; x₃₄=5.

Z=15*4+5*6+5*8+20*4+10*4+5*2=260.

Анализ результатов и выводы

Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении.

Задание 6

Решение многоэтапных задач методом динамического программирования