2 Задача линейного программирования

Менеджеру производственной фирмы требуется составить оптимальный по прибыли план выпуска запчастей двух видов, используя для этого ресурсы трех типов. Их запасы ограничены значениями в₁, в₂, в₃ соответственно. Пусть а₁₁, а₁₂ количество ресурсов первого типа, расходуемых на запчасти каждого вида, соответственно. Аналогичный смысл имеют символы а₂₁, а₂₂ и а₃₁, а₃₂.

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

Требуется:

а) записать условия задачи в таблицу стандартной формы;

б) решить задачу табличным симплекс- методом

в) решить задачу в среде EXCEF

г) составить и решить двойственную задачу.

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

а) Условия задачи в таблице стандартной формы:

Ресурсы	Запасы	Расх. коэфф.
		1	2
Количество ресурсов I типа	268	12	4
Количество ресурсов II типа	120	4	4
Количество ресурсов III типа	252	3	12
Прибыль, у.е.	-	30	40

б) Решить задачу табличным симплекс-методом

Пусть х₁, х₂, х₃ – количество изделий каждого вида.

12х₁ + 4х₂ ≤ 268

4х₁ + 4х₂ ≤ 120

3х₁ + 12х₂ ≤ 252

х₁, х₂ ≥ 0

F= 30х₁ + 40х₂ → max

1. Система ограничений должна быть приведена к каноническому виду.

К левой части неравенства 1 системы ограничений следует прибавить неотрицательную переменную х₃ – чтобы преобразовать неравенство 1 в равенство.

К левой части неравенства 2 системы ограничений следует прибавить неотрицательную переменную х₄ - чтобы преобразовать неравенство 2 в равенство.

К левой части неравенства 3 системы ограничений следует прибавить неотрицательную переменную х₅ - чтобы преобразовать неравенство 3 в равенство.

12х₁ + 4х₂ + х₃ = 268

4х₁ + 4х₂ + х₄ = 120

3х₁ + 12х₂ + х₅ = 252

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

Определимся с начальным опорным решением.

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

Переменная x3 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. х₃ - базисная переменная.

Переменная x4 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. х₄ - базисная переменная.

Переменная x5 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. х₅ - базисная переменная.

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

X н = ( 0 , 0 , 268 , 120 , 252 )

Вернемся к функции F.

F = 30х₁ + 40х₂ → max

Функция F не содержит базисных переменных.

Для составления начальной симплекс таблицы выполнены все условия.

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

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

1. Составляется исходная симплекс-таблица:

Базисные переменные	х1	х2	x3	x4	x5	Свободные члены	Отношение
x3	12	4	1	0	0	268	268/4=67
x4	4	4	0	1	0	120	120/4=30
x5	3	12	0	0	1	252	252/12=21
F	-30	-40	0	0	0	0

За ведущий выбирается столбец 2 , так как -40 - наименьший элемент в F строке. Элемент F строки, принадлежащий столбцу свободных членов не рассматриваем.

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

Разделим элементы ведущей строки на 12:

Базисные переменные	х1	х2	x3	x4	x5	Свободные члены
x3	12	4	1	0	0	268
x4	4	4	0	1	0	120
x5	1/4	1	0	0	1/12	21
F	-30	-40	0	0	0	0

От элементов строки 1 нужно отнять соответствующие элементы строки 3, умноженные на 4.

От элементов строки 2 нужно отнять соответствующие элементы строки 3, умноженные на 4.

От элементов строки F нужно отнять соответствующие элементы строки 3, умноженные на - 40.

Базисные переменные	х1	х2	x3	x4	x5	Свободные члены
x3	11	0	1	0	-1/3	184
x4	3	0	0	1	-1/3	36
x2	1/4	1	0	0	1/12	21
F	-20	0	0	0	10/3	840

х₂ = ( 0 , 21 , 184 , 36 , 0)

F = 840 = 20 х₁ -10/3 х₅

Значение функции F для данного решения: F (х₂) = 840

2. За ведущий выберем столбец 1 , так как -20 наименьший элемент в F строке. Элемент F строки, принадлежащий столбцу свободных членов не рассматривается.

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

Базисные переменные	х1	х2	x3	x4	x5	Свободные члены	Отношение
x3	11	0	1	0	-1/3	184	184/11=16,7
x4	3	0	0	1	-1/3	36	36/3=12
x2	1/4	1	0	0	1/12	21	21/0,25=84
F	-20	0	0	0	10/3	840	-

Можно разделить элементы строки 2 на 3.

Базисные переменные	х1	х2	x3	x4	x5	Свободные члены
x3	11	0	1	0	-1/3	184
x4	1	0	0	1/3	-1/9	12
x2	1/4	1	0	0	1/12	21
F	-20	0	0	0	10/3	840

От элементов строки 1 отнимаются соответствующие элементы строки 2, умноженные на 11.

От элементов строки 3 отнимаются соответствующие элементы строки 2, умноженные на 1/4.

От элементов строки F отнимаются соответствующие элементы строки 2, умноженные на -20.

Базисные переменные	х1	х2	x3	x4	x5	Свободные члены
x3	0	0	1	-11/3	8/9	52
x1	1	0	0	1/3	-1/9	12
x2	0	1	0	-1/12	1/9	18
F	0	0	0	20/3	10/9	1080

Таким образом, F = 1080

F = 20/3 x₄ +10/9 x₅

Значение функции F для данного решения: F (X 1) = 1080

Учитывая, что все x i ≥ 0, по условию задачи, наибольшее значение функции F равно свободному члену 1080, т.е. мы получили оптимальное решение.

X опт = (12 , 18 , 0 , 0 , 0 )

в) решить задачу в среде EXCEL

Для того, чтобы решить задачу в среде Excel, следует воспрользоваться программой «Поиск решения».

Ввод исходных значений в соответствии с рисунком 2.

Рисунок 2 – Исходные значения к задаче линейного программировании

После этого устанавливаются необходимые ограничения в программе «Поиск решения» и получаются следующие результаты в соответствии с рисунком 3.

Рисунок 3 – Результат вычислений

Таким образом, видно, что результаты вычислений в среде Excel полностью совпадают с результатами табличных вычислений

г) Составить и решить двойственную задачу

Для составления двойственной задачи следует вернуться к исходной:

12х₁ + 4х₂ + 4х₃ ≤ 268 12у₁ +4у₂ + 3у₃ ≥ 30

4х₁ + 4х₂ + 4х₃ ≤ 120 4у₁ +4у₂ + 12у₃ ≥ 40

3х₁ + 12х₂ + 3х₃ ≤ 252

х₁, х₂ ≥ 0 у₁, у₂, у₃ ≥ 0

F= 30х₁ + 40х₂ → max G = 268y₁ + 120 у₂ + 252 у₃ → min

Напоминание: х _опт = (12,18), F_max = 1080

1) Из любого ограничения двойственной задачи следует, что размерность у_i совпадает с размерностью правой части (рубли/ ед. ресурса). Поэтому у_i имеют смысл цены единицы ресурса. Их так и называют – теневые цены ресурсов.

Сравнивая теневые цены ресурсов можно решить, в какой из них выгоднее вкладывать дополнительные средства.

Выше было отмечено, что у₁ = 2/3, у₂=10/3. Таким образом, дополнительные средства выгоднее вкладывать в закупку сырья.

3) Так как х₁ > 0 и х₂ > 0, то

12у₁ +4у₂ + 3у₃ = 30

4у₁ +4у₂ + 12у₃ = 40

А так как первое ограничение исходной задачи обращается при оптимальном решении в строгое неравенство, то у₁ = 0.

Итак, у₂ =20/3, у₃ =10/9.→ у_опт = (0, 20/3, 10/9)

2) F_max = 1080, G_min =0*268 + 120* (20/3) + 252* (10/9) = 1080.

Таким образом, пункт а) теоремы двойственности выполнен

4) Можно подчеркнуть, что у₁ = 0 означает не дефицитность первого ресурса,

у₂ =20/3, у₃ =10/9 - дефицитность последних двух ресурсов.