Варианты задач лп для самостоятельного решения графическим методом

Вариант 1	Вариант 2
Вариант 3	Вариант 4
Вариант 5	Вариант 6
Вариант 7	Вариант 8
Вариант 9

Тема 2. Основы линейного программирования

Цель практического занятия №3: Получить навыки решения задач линейного программирования симплекс-методом

Вопросы по лекционному курсу:

1. Какие задачи линейного программирования можно решать симплексным методом?

2. Каков признак оптимальности в симплексном методе?

3. Как строится первый опорный план?

4. Как определяется ведущий столбец и ведущая строка симплексной таблицы?

5. Как осуществляется пересчет коэффициентов симплексной таблицы?

Методические указания к практическому занятию

Методику решения задач линейного программирования симплекс-методом рассмотрим на следующем примере

Пример 1. На предприятии выпускается n видов продукции П_j (j=1, n). На её изготовление используются ресурсы R₁,R₂,R₃. Размеры допустимых затрат ресурсов ограничены величинами b₁,b₂,b₃. Расход ресурса R_i (i=1,2,3) на производство единицы продукции П_j равен а_ij. Прибыль от реализации единицы продукции П_j равна с_j ден. единиц.

Таблица 1

Исходные данные

Ресурсы (Ri)	Продукция (Пj)				Допустимые затраты ресурсов (bi)
	П1	П2	П3	П4
R1	2	1	1	1	280
R2	1	0	1	1	80
R3	1	2	1	0	250
Прибыль от реализации ед. продукции, ден. ед. (сj)	4	3	6	7

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

1. Составить математическую модель задачи.

2. Привести модель к каноническому виду и заполнить симплексную таблицу.

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

4. Дать экономическое истолкование оптимальному решению X_опт. и наибольшему значению целевой функции F_наиб. (X_опт.).

Решение.

Составим математическую модель задачи.

Пусть х₁ – выпуск продукции П₁, х₂ – выпуск продукции П₂, х₃ – выпуск продукции П₃, х₄ – выпуск продукции П₄.

Общая прибыль от реализации всей продукции составит: 4х₁+3x₂+6x₃+7x₄ ден. ед. и она должна быть максимальна.

Общие затраты ресурса R₁ составляют: 2x₁+x₂+x₃+x₄, а так как допустимые затраты ресурса R₁ равны 280, получаем первое ограничение:

2x₁+x₂+x₃+x₄ ≤ 280.

Аналогично получаем ограничения по ресурсу R₂ , R₃ и R₄:

x₁+x₃+x₄ ≤ 80

x₁+2x₂+x₃ ≤ 250

Кроме того, выпуск продукции не может быть отрицательным, т.е. x_j ≥ 0; j = 1,2,3,4.

Получаем математическую модель задачи: среди неотрицательных решений системы линейных неравенств.

2x₁+x₂+x₃+x₄ ≤ 280

x₁+x₃+x₄ ≤ 80

x₁+2x₂+x₃ ≤ 250

найти решение, обеспечивающее максимум функции F = 4х₁+3x₂+6x₃+7x₄ → max.

2) Приведём математическую модель данной задачи к каноническому виду, для этого к левым частям неравенств системы ограничений прибавим неотрицательные дополнительные (балансовые) переменные: среди неотрицательных решений системы линейных уравнений:

2x₁+x₂+x₃+x₄ = 280

x₁+x₃+x₄ = 80

x₁+2x₂+x₃ = 250

найти решение, обеспечивающее максимум функции F = 4х₁+3x₂+6x₃+7x₄ → max.

Смысл дополнительных переменных:

x₅ – остаток ресурса R₁;

x₆ – остаток ресурса R₂;

x₇ – остаток ресурса R₃;

Заполним симплексную таблицу; базисные переменные x₅, x₆, x₇

Таблица 2.

Симплексная таблица базисных переменных х₅, х₆, х₇

Базис	Свободный член	Переменные							Оценочные отношения
		x1	x2	x3	x4	x5	x6	x7
x5	280	2	1	1	1	1	0	0	280
x6	80	1	0	1	1	0	1	0	80
x7	250	1	2	1	0	0	0	1	∞
F	0	-4	-3	-6	-7	0	0	0

3) Базисное решение (0; 0; 0; 0; 280; 80; 250). Проверим его на оптимальность. Так как в последней строке есть отрицательные коэффициенты, то решение не оптимально.

Из коэффициентов последней строки выбираем наибольший по модулю (-7); первый столбец разрешающий, переменная x₁ = min {280/1; 80/1; 250/0} = min {280; 80; ∞} = 80.

Вторая строка является разрешающей. На пересечении разрешающей строки и столбца стоит разрешающий элемент = 1.

Строим новую таблицу:

а) новые базисные переменные х₅, х₄, х₇;

в) расставляем нули и единицы; например, в клетке, соответствующей основной переменной х₅ по столбцу и строке ставим 1, а в клетке, соответствующей основной переменной х₅ по строке, а основной переменной х₇ по столбцу, ставим 0 и т.п. В последней строке против всех основных элементов ставим 0. Вторая строка получается делением на разрешающий элемент. Остальные клетки заполняем по правилу прямоугольника. Например:

b₁= 280-(80*1)/1=200; а₁₂= 1-(0*1)/1=1.

Получим вторую симплексную таблицу:

Таблица 3

Симплексная таблица базисных переменных х₅, х₄, х₇

Базис	Свободный член	Переменные							Оценочные отношения
		x1	x2	x3	x4	x5	x6	x7
x5	200	1	1	0	0	1	-1	0	200
x4	80	1	0	1	1	0	1	0	∞
x7	250	1	2	1	0	0	0	1	125
F	560	3	-3	1	0	0	7	0

Базисное решение (0; 0; 0; 80; 200; 0; 250). Так как в последней строке есть отрицательные коэффициенты, то решение не оптимально.

Теперь разрешающий 2 столбец; x₂ – переходит в основные, min{200/1; 80/0; 250/2}, третья строка - разрешающая, 2 – разрешающий элемент. Новая симплексная таблица примет вид:

Таблица 4.

Симплексная таблица базисных переменных х₅, х₄, х₂

Базис	Свободный член	Переменные							Оценочные отношения
		x1	x2	x3	x4	x5	x6	x7
x5	75		0		0	1
x4	80		0		1	0
x2	125	1/2	1	1/2	0	0	0	1/2
F	935	9/2	0	5/2	0	0	7	3/2

Критерий оптимальности выполнен, F_наиб = 935; оптимальное базисное решение (0; 125; 0; 80; 75; 0; 0).

4) Экономическое истолкование:

для того чтобы получить максимальную прибыль, равную 935 ден. ед., предприятие должно выпустить 0 ед. продукции 1-го вида, 125 ед. продукции 2-го вида, 0 ед. продукции 3-го вида и 80 ед. продукции 4-го вида. При этом 2 и 4 ресурс израсходуется полностью, останется 75 ед. ресурса R₁.