Задача минимизации линейной функции

Сведение задачи минимизации к задаче максимизации линейной функции

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

 

W = c₁x₁ + c₂x₂ + … + c_nx_n.

 

Однако во многих экономических задачах требуется найти минимум линейной функции. Для этого достаточно положить

 

W = -Z = -c₁x₁ – c₂x₂ - … - c_nx_n

 

и решать задачу максимизации полученной функции W при соответствующих ограничениях. Так как ясно, что

 

min Z = -max W.

 

 

Минимизировать линейную функцию

 

Z = -2X₁ + 5X₂

 

при выполнении ограничений

 

7X₁ + 2X₂ ≥ 14,

5X₁ + 6X₂ ≤ 30,

3X₁ + 8X₂ ≥ 24,

X₁ ≥ 0, X₂ ≥ 0.

 

Геометрическое решение задачи на (рис. 5) и ему отвечает оптимальное решение в точке

С (48/11, 15/11) и при этом Z_min = -21/11.

 

 

Рис 5. Геометрическое решение задачи

 

Вводя выравнивающие переменные Y_i ≥ 0 и функцию W = -Z = 2X₁ - 5X₂ → max, задачу запишем в виде.

 

Y₁ = 7X₁ + 2X₂ - 14,

Y₂ = -5X₁ - 6X₂ + 30,

Y₃ = 3X₁ + 8X₂ - 24,

W = 2X₁ - 5X₂.

 

Записываем эту систему в виде таблицы.

 

 

	-X1	-X2	1
Y1	-7	-2	-14
Y2	5	6	30
Y3	-3	-8	-24
W	2	5	0

 

Так как имеются отрицательные свободные члены, то от них избавляемся. Выбираем наименьший отрицательный член в Y₃ – строке и в этой строке берем отрицательный элемент “-8”, который соответствует разрешающему столбцу. Свободные члены делим на соответствующие элементы разрешающего столбца и выбираем наименьшее положительное отношение, тогда Y₃ – строка разрешающая. Производя ШМЖИ с разрешающим элементом “-8”, получаем таблицу.

 

	-X1	-Y3	1
Y1	-50/8	-2/8	-8
Y2	22/8	6/8	12
X2	3/8	-1/8	3
W	-31/8	5/8	-15

 

 

Избавляемся от отрицательного свободного члена в Y₁ – строке, совершая ШМЖИ с разрешающим элементом “-50/8”, получаем таблицу.

 

 

	-Y1	-Y3	1
X1	-8/50	2/50	64/50
Y2	22/50	32/50	424/50
X2	3/50	-7/50	126/50
W	-31/50	39/50	-502/50

 

 

Так как все свободные члены в 1 – столбце неотрицательные, то выбираем разрешающий элемент как в МЖИ для задачи на max. Совершаем ШМЖИ с разрешающим элементом “22/50”, получаем таблицу.

 

 

	-Y2	-Y3	1
X1	4/11	3/11	48/11
Y1	25/11	16/11	212/11
X2	-3/22	-5/22	15/11
W	31/22	37/22	21/11

 

Так как в W – строке и в 1 – столбце нет отрицательных элементов, то получили оптимальное решение X₁ = 48/11, X₂ = 15/11, W_max – 21/11 или  Z_min = –W_max = -21/11,

 

 

Практическая часть

1.  Решить задачу симплекс методом.

 

X₁ + 3X₂ ≤ 300   F = 2X₁ + 3X₂ → max

X₁ + X₂ ≤ 150

X₁ ≥ 0

X₂ ≥ 0

 

Решение

X₁ + 3X₂ + X₃ = 300   F - 2X₁ - 3X₂  = 0

X₁ + X₂ + X₄ = 150

 

Б	С.Ч	X1	X2	X3	X4
X3	300	1	3	1	0
X4	150	1	1	0	1
F	0	-2	-3	0	0

 

Б	С.Ч	X1	X2	X3	X4
X2	100	1/3	1	1/3	0
X4	50	2/3	0	1/3	1
F	300	-1	0	1	0

 

 

(-1) (3)

Б	С.Ч	X1	X2	X3	X4
X2	75	0	1	1/2	-1/2
X1	75	1	0	-1/2	3/2
F	375	0	0	1/2	3/2

 

 

(-1/3) (1)

Ответ: X₁ = 75; X₂ = 75; X₃ = 0; X₄ = 0.

 

Задача №1.

 

   Предприятие выпускает продукцию двух видов. Виды сырья, его запасы, нормы расхода сырья на у.е. каждого вида продукции, прибыль производства от реализации продукции даны в таблице.

 

   Как следует спланировать выпуск продукции, чтобы прибыль предприятия была наибольшей?

 

Решение

 

X₁ + 3X₂ ≤ 20   F = 2X₁ + X₂ →  max

2X₁ + X₂ ≤ 10

2X₁ + 2X₂ ≤ 17

 

 

 

X₁ + 3X₂ + X₃ = 20   F - 2X₁ - X₂  = 0

2X₁ + X₂ + X₄ = 10

2X₁ + 2X₂ + X₅ =17

 

Б	С.Ч	X1	X2	X3	X4	X5
X3	20	1	3	1	0	0
X4	10	2	1	0	1	0
X5	17	2	2	0	0	1
F	0	-2	-1	0	0	0

 

Б	С.Ч	X1	X2	X3	X4	X5
X3	15	0	5/2	1	-1/2	0
X1	5	1	1/2	0	1/2	0
X5	7	0	1	0	-1	1
F	10	0	0	0	1	0

 

 

(-1)(-2)(2)

Ответ: X₁ = 5; X₂ = 0; X₃ = 15; X₄ = 0; X₅ = 7.

 

Задача №2.

 

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

 

Как следует спланировать выпуск продукции, чтобы прибыль предприятия была наибольшей?

 

Решение

 

2X₁ + 3X₂ + 7X₃ ≤ 1250   F = 41X₁ + 35X₂ + 96X₃ → max

X₁ + X₂ ≤ 250

5X₁ + 3X₂ ≤ 900

 

2X₁ + 3X₂ + 7X₃ + X₄ = 1250   F - 41X₁ - 35X₂ - 96X₃ = 0

X₁ +X₂ + X₅ = 250

5X₁ +3X₂ + X₆ = 900

Б	С.Ч	X1	X2	X3	X4	X5	X6
X4	1250	2	3	7	1	0	0
X5	250	1	1	0	0	1	0
X6	900	5	3	0	0	0	1
F	0	-41	-35	-96	0	0	0

 

Б	С.Ч	X1	X2	X3	X4	X5	X6
X3	1250/7	2/7	3/7	1	1/7	0	0
X5	250	1	1	0	0	1	0
X6	900	5	3	0	0	0	1
F	120000/7	-95/7	43/7	0	96/7	0	0

 

 

(96)

Б	С.Ч	X1	X2	X3	X4	X5	X6
X3	890/7	0	9/35	1	1/7	2/7	-2/35
X5	70	0	2/5	0	0	1	-1/5
X1	180	1	3/5	0	0	0	1/5
F	137100/7	0	100/7	0	96/7	0	19/7

 

Ответ: X₁ = 180; X₂ = 0; X₃ = 890/7; X₄ = 0; X₅ = 70; X₆ = 0.

 

Задача №3.

  Для изготовления четырех видов продукции используется три вида сырья.

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

 

  Как следует спланировать выпуск продукции, чтобы прибыль предприятия была наибольшей?

 

Решение

 

2X₁ + 3X₂ + 3X₃ + X₄ ≤ 20   F = 2X₁ + 4X₂ + 3X₃ + 2X₄ → max

X₁ + X₂ + 2X₃ + 2X₄ ≤ 11

X₁ + 2X₂ + 3X₃ + X₄ ≤ 25

 

2X₁ + 3X₂ + 3X₃ + X₄ + X₅ = 20   F - 2X₁ - 4X₂ - 3X₃ - 2X₄ = 0

X₁ + X₂ + 2X₃ + 2X₄ + X₆ = 11

X₁ + 2X₂ + 3X₃ + X₄ + X₇ = 25

 

 

X₁ + 3X₂ ≤ 20   F = 2X₁ + X₂ → max

2X₁ + X₂ ≤ 10

2X₁ + 2X₂ ≤ 17

 

Б	С.Ч	X1	X2	X3	X4	X5	X6	X7
X5	20	2	3	3	1	1	0	0
X6	11	1	1	2	2	0	1	0
X7	25	1	2	3	1	0	0	1
F	0	-2	-4	-3	-2	0	0	0

Б	С.Ч	X1	X2	X3	X4	X5	X6	X7
X2	20/3	2/3	1	1	1/3	1/3	0	0
X6	13/3	1/3	0	1	5/3	-1/3	1	0
X7	35/3	-1/3	0	1	1/3	-2/3	0	1
F	80/3	2/3	0	1	-2/3	4/3	0	0

 

 

(-1)(-2)(4)

Б	С.Ч	X1	X2	X3	X4	X5	X6	X7
X2	29/5	3/5	1	4/5	0	2/5	-1/5	0
X4	13/5	1/5	0	3/5	1	-1/5	3/5	0
X7	54/5	-2/5	0	4/5	0	-3/5	-1/5	1
F	282/5	4/5	0	7/5	0	6/5	2/5	0

 

 

(-1/3)(-1/3)(2/3)

 

Ответ: X₁ = 0; X₂ = 29/5; X₃ = 0; X₄ = 13/5; X₅ = 0; X₆ = 0; X₇ = 54/5.

 

Заключение

     Остановимся на простейших истолкованиях симплексно­го метода.

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

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

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

     Симплекс – выпуклый многоугольник в n – мерном пространстве с n + 1 вершинами, не лежащими на одной гиперплоскости. Симплексы выделены в отдельный класс потому, что симплекс – это простейший многоугольник, содержащий некоторый объем n – мерного пространства.

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

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

     Математическое программирование (оптимальное программирование) – область математики, объединяющая различные математические методы и дисциплины: линейное программирование, динамическое программирование, выпуклое программирование и др. Общая задача математического программирования состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. 

 

 

 

Список использовавшейся литературы

1) А. С. Шапкин, Н. П. Мазаева; Математические методы и модели исследования операций, 2005.

2) Н.Ш. Кремер, Б А Путко, И.М. Тришин, М.Н. Фридман; Исследование операций в экономике. - ЮНИТИ, 2002.

3)