Разработка модели и решение задачи линейного программирования

     10x₁+11x₂+11x₃+6x₄≤30

Для построения первого  опорного плана систему неравенств, приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

8x₁ + 7x₂ + 5x₃ + 9x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ = 22

8x₁ + 9x₂ + 7x₃ + 8x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ = 25

 10x₁ + 9x₂ + 9x₃ + 7x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ = 38

     10x₁ + 11x₂ + 11x₃ + 6x₄ + 0x₅ + 0x₆ + 0x₇ + 1x₈ = 30

В качестве начальной  допустимой базы можно взять B⁰ = (5, 6, 7, 8). Ей будет соответствовать следующая таблица.

Таблица 4

               Симплекс-таблица с начальной  допустимой базой

22	8	7	5	9	1	0	0	0
25	8	9	7	8	0	1	0	0
38	10	9	9	7	0	0	1	0
30	10	11	11	6	0	0	0	1
0	-21	-18	-16	-17.5	0	0	0	0

 

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

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

max(-21,-18,-16,-17.5,0,0,0,0) = -21

В качестве ведущего выберем  столбец, соответствующий переменной x₁.

Таблица 5

Симплекс-таблица

22	8	7	5	9	1	0	0	0
25	8	9	7	8	0	1	0	0
38	10	9	9	7	0	0	1	0
30	10	11	11	6	0	0	0	1
0	-21	-18	-16	-17.5	0	0	0	0

 

Вычислим значения D_i по строкам как частное от деления:

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей. Вместо переменной x₅ в план войдет переменная x₁.Разделим 1-ую строку на 8 и прибавим к последней строке, а затем вычтем из всех остальных строк.

Таким образом, очередной  базис равен B⁰ = (1, 6, 7, 8).

max(0,0.38,-2.88,6.13,2.63,0,0,0) = -2.88

В качестве ведущего выберем  столбец, соответствующий переменной x₃.

Таблица 6

Симплекс-таблица

2.75	1	0.88	0.63	1.13	0.13	0	0	0
3	0	2	2	-1	-1	1	0	0
10.5	0	0.25	2.75	-4.25	-1.25	0	1	0
2.5	0	2.25	4.75	-5.25	-1.25	0	0	1
57.75	0	0.38	-2.88	6.13	2.63	0	0	0

 

Вычислим значения D_i по строкам как частное от деления:

и из них выберем наименьшее:

Следовательно, 4-ая строка является ведущей. Вместо переменной x₈ в план войдет переменная x₃. Разделим 4-ую строку на 4.75 и прибавим к последней строке, а затем вычтем из всех остальных строк.

Таким образом, очередной  базис равен B¹ = (1, 6, 7, 3). Последняя строка не содержит отрицательных элементов. Найден оптимальный план.

Окончательный вариант  таблицы:

Таблица 7

Симплекс-таблица с  оптимальным планом

2.42	1	0.58	0	1.82	0.29	0	0	-0.13
1.95	0	1.05	0	1.21	-0.47	1	0	-0.42
9.05	0	-1.05	0	-1.21	-0.53	0	1	-0.58
0.53	0	0.47	1	-1.11	-0.26	0	0	0.21
59.26	0	1.74	0	2.95	1.87	0	0	0.61

 

Оптимальный план можно  записать так:

x₁ = 2.42

x₆ = 1.95

x₇ = 9.05

x₃ = 0.53

F(x) = 21*2,42 + 16*0,53 = 59,26

2.4. Решение поставленной задачи с помощью средств EXСEL (надстройки «Поиск решения», «Анализ данных»)

 

Поиск решения - это надстройка EXCEL, которая позволяет решать оптимизационные задачи. После выбора команд Сервис Þ Поиск решения появится диалоговое окно Поиск решения.

В диалоговом окне Поиск  решения есть три основных параметра:

• Установить целевую  ячейку

• Изменяя ячейки

• Ограничения

Сначала нужно заполнить  поле «Установить целевую ячейку». Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить конкретное значение.

Второй важный параметр средства Поиск решения — это параметр «Изменяя ячейки». Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.

Третий параметр, который  нужно вводить, для Поиска решения – это ограничения.

Для решения задачи необходимо:

• Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

• Ввести исходные данные.
• Ввести зависимость для целевой функции
• Ввести зависимости для ограничений.
• Запустить Поиск решений.
• Назначение целевой функции (установить целевую ячейку).
• Ввод ограничений.
• Ввод параметров для решения ЗЛП.

Начнем решение задачи в программе Excel. Введем переменные:

Таблица 8

Ввод данных

	A	B	C	D
1	X1	X2	X3	X4
2	0	0	0	0

 

Запишем систему ограничений  на значения переменных:

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

Таблица 9

Ввод ограничений

	A	B	C
5	0 (=8*A2+7*B2+5*C2+9*D2)	<=	22
6	0 (=8*A2+9*B2+7*C2+8*D2)	<=	25
7	0 (=10*A2+9*B2+9*C2+7*D2)	<=	38
8	0 (=10*A2+11*B2+11*C2+6*D2)	<=	30

 

 

Установим расположение ячейки, в которой будет вычисляться  значение целевой функции и введем формулу для вычисления целевой функции:

 

 

Таблица 10

Ввод целевой функции

	A	B
11	F=	0 (=21*A2+18*B2+16*C2+17,5*D2)

 

Откроем диалоговое окно «Поиск решения». В нем зададим  расположение целевой ячейки (в котором вычисляется значение целевой функции), вид оптимального решения (максимальное значение), расположение ячеек, которые будут изменяться при поиске решения (из них состоит вектор-строка оптимального плана), а также ограничения на изменяемые значения.

Рис. 3. Этап «Поиск решения»

Далее необходимо установить определённые параметры. В диалоговом окне «Поиск решения» выбираем «Параметры» и устанавливаем галочки на «Линейная модель» и «Неотрицательные значения».

Рис. 4. Этап «Параметры поиска решения»

После ввода необходимых  данных нажмем кнопку «Выполнить» диалогового окна. В случае, если решение существует (и все данные введены верно), появляется сообщение:

Рис. 5. Этап «Результаты поиска решения»

После нажатия кнопки «ОК» в ячейках строки оптимального плана появляются значения его оптимальных элементов (оптимальный план); в ячейке целевой функции вычисляется соответствующее этому плану оптимальное значение целевой функции.

 

 

 

 

 

Таблица 11

Таблица результатов

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

1) Отчет по результатам

Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$B$11	F= <=	0	59,26315789
Изменяемые  ячейки
	Ячейка	Имя	Исходное значение	Результат
	$A$2	x1	0	2,421052632
	$B$2	x2	0	0
	$C$2	x3	0	0,526315789
	$D$2	x4	0	0
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$A$5	ограничения	22	$A$5<=$C$5	связанное	0
	$A$6	ограничения	23,05263158	$A$6<=$C$6	не связан.	1,947368421
	$A$7	ограничения	28,94736842	$A$7<=$C$7	не связан.	9,052631579
	$A$8	ограничения	30	$A$8<=$C$8	связанное	0

 

2) Отчет по устойчивости

3) Отчет по пределам

		Целевое
	Ячейка	Имя	Значение
	$B$11	F= <=	59,26315789
		Изменяемое			Нижний	Целевой		Верхний	Целевой
	Ячейка	Имя	Значение		предел	результат		предел	Результат
	$A$2	x1	2,421052632		0	8,421052632		2,421052632	59,26315789
	$B$2	x2	0		0	59,26315789		0	59,26315789
	$C$2	x3	0,526315789		0	50,84210526		0,526315789	59,26315789
	$D$2	x4	0		0	59,26315789		0	59,26315789