Методы оптимальных решений

 

                                1 ПОСТАНОВКА ЗАДАЧИ

 

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

Таблица 1 – Исходные данные для решения задачи

 

Тип сырья	Нормы расхода на одно изделие, кг на 1 изделие			Запасы сырья, кг
	А	В	С
1	11	22	31	108
2	31	41	22	130
3	51	63	53	190
Прибыль, у.д.е.	13	8	19

 

- объем выпуска изделий  вида А

- объем выпуска изделий  вида B

 - объем выпуска изделий вида C

 

 

 

 

 

2 НАХОЖДЕНИЕ НЕЦЕЛОЧИСЛЕННЫХ  РЕШЕНИЙ

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

Решим задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 13x1+8x2+19x3 при следующих условиях ограничений:

            11x1+22x2+31x3≤108 
  U:      31x1+41x2+22x3≤130 
          51x1+63x2+53x3≤190

          11x1 + 22x2 + 31x3 + 1x4 + 0x5 + 0x6 = 108 
U:     31x1 + 41x2 + 22x3 + 0x4 + 1x5 + 0x6 = 130 
          51x1 + 63x2 + 53x3 + 0x4 + 0x5 + 1x6 = 190

 

Таблица 2 – Построение таблицы симплексным методом

Б	СЧ
	108	11	22	31	1	0	0
	130	31	41	22	0	1	0
	190	51	63	53	0	0	1
	0	-13	-8	-19	0	0	0

          Решим систему уравнений относительно базисных переменных: 
x4, x5, x6. Полагая, что свободные переменные равны 0, получим первый опорный план: X = (0,0,0,108 ,130,190)

Переходим к основному алгоритму симплекс-метода.

1. Текущий опорный план  не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.

Вычислим значения разрешающего коэффициента (РК) по строкам как частное от деления: bi / ai и из них выберем наименьшее:

Следовательно, 1-ая строка я вляется ведущей.

Таблица 3 – Пересечение элементов

Б	СЧ							Разрешающий коэффициент
	108	11	22	31	1	0	0	108/31=3,48min
	130	31	41	22	0	1	0	130/22=5.9
	190	51	63	53	0	0	1	190/51=3,58
	0	-13	-8	-19	0	0	0

 

 

 

 

 

После преобразований получаем новую таблицу 4.

Таблица 4 – Симплекс-таблица после преобразования

Б	СЧ
	108/31	11/31	22/31	1	1/31	0	0
	1654/31	719/31	787/31	0	-22/31	1	0
	166/31	998/31	787/31	0	-53/31	0	1
	2052/31	-194/31	170/31	0	19/31	0	0

 

2. Текущий опорный план  не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения РК по строкам как частное от деления: bi / ai и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей.

Таблица 5 - Пересечение элементов

Б	СЧ							РК
	108/31	11/31	22/31	1	1/31	0	0	108/11=9.82
	1654/31	719/31	787/31	0	-22/31	1	0	1654/719=2.3
	166/31	998/31	787/31	0	-53/31	0	1	166/998=0.16min
	2052/31	-194/31	170/31	0	19/31	0	0

 

 

  После преобразований получаем новую таблицу 6.

 

Б	СЧ
	1709/499	0	429/998	1	51/998	0	-11/998
	24699/499	0	7083/998	0	521/998	1	-719/998
	83/499	1	787/998	0	-53/998	0	31/998
	33550/499	0	5199/499	0	140/499	0	97/499

 

Индексная строка не содержит отрицательных элементов - найден оптимальный план.

Вывод можно записать так:

1. Максимальный доход составит  33550/499=67.2345у. д. е.
2. Оптимальный план производства заключается в выпуске продукции:

• A: в объеме 0, 17 кг.
• B: в объеме 0 кг.
• C: в объеме 3, 42 кг.

                    3. №1:  11×0, 17+22×0+31×3, 42=107, 89(ост. 0, 11)

                        №2:  31×0, 17+41×0+22×3, 42=80, 51(ост. 49, 49)

                        №3:  51×0, 17+63×0+53×3, 42=189, 93(ост. 0, 07)