Последовательность решения задачи

Построение экономико-математической модели задачи

 

1. Переменные

 

Х1 - количество приобретаемых машин типа А, шт.

 

Х2 - количество приобретаемых машин типа В, шт.

 

2. Ограничения

 

1 По площади размещения машин, м²

 

3Х₁ + 5Х₂ < 60

 

2 По затратам денежных средств, млн руб.

(1)

3Х₁ + 4Х₂ < 34

 

3 По приобретению оборудования типа В, шт.

 

Х₁ > 0, Х₂ > 0, Х₁, Х₂ – целые числа.

 

3. Целевая функция

Критерий оптимальности – Максимум производительности оборудования, т.

 

Z = 2Х₁ + 3Х₂ => max

 

 

Математическая формулировка задачи.

 

Найти такие целочисленные значения переменных Х₁ и Х₂ , что выполняются ограничения задачи (1) и достигается максимальное значение целевой функции Z.

Экономическая формулировка задачи.

 

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

.

Подготовка задачи к решению симплексным методом

 

Запишем задачу (1) в каноническом виде:

 

3Х₁ + 5Х₂ + Х₃ = 60

3Х₁ + 4Х₂ + Х₄ = 34 (2)

Х₂ + Х₅ = 8

 

Х_j > 0, j = 1, 5; Х₁, Х₂ – целые числа

 

Z = 2Х₁ + 3Х₂ + 0Х₃ + 0Х₄ + 0Х₅ = > max

 

Решение задачи симплексным методом

ИТЕРАЦИЯ 1

ШАГ 1. Выписываем исходное допустимое базисное решение

 

Х₁ Х₂ Х₃ Х₄ Х₅

Х₁ =

0 0 60 34 8

 

и соответствующее ему значение целевой функции Z.

 

Z = 2 * 0 + 3 * 0 + 0 * 60 + 0 * 34 + 0 * 8 = 0.

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₁ = 1

Тогда Δ Х₃ = -3

Δ Х₄ = -3

Δ Х₅ = 0

Δ Z = 2 * 1 + 3 * 0 + 0 * (-3) + 0 * (-3) + 0 * 0 = 2 > 0.

Вывод: Решение Х₁ неоптимальное. Переменную Х₁ целесообразно ввести в базис поскольку от этого значение целевой функции Z увеличится.

 

ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

Х₃ = 60 - 3Х₁ 60 - 3Х₁ > 0 Х₁ > 20

Х₄ = 34 - 3Х₁ = > 34 - 3Х₁ > 0 = > Х₁ > --- (*)

Х₅ = 8 - 0 -- --

 

Замена прежней базисной переменной произойдет во втором уравнении.

Вывод: В новом базисе будут находиться переменные Х1, Х3, Х5, а переменная Х4 станет небазисной.

ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.

Для этого:

1. Разделим почленно второе уравнение системы (2) на 3. Это будет второе уравнение новой системы (3).

2. Исключим переменную Х₁ из первого уравнения. Для этого из первого уравнения системы (2) вычтем второе уравнение системы (3), умноженное на 3:

 

3Х₁ + 5Х₂ + Х₃ = 60

3Х₁ + 4Х₂ + Х₄ = 34

Х₂ + Х₃ - Х₄ = 26

 

Это будет первое уравнение новой системы (3).

3. Перепишем в новую систему уравнений (3) третье уравнение из системы (2) в том же виде

 

После таких преобразований новая система уравнений будет иметь вид:

 

Х₂ + Х₃ - Х₄ = 26

 

4 1 34

Х₁ + --Х₂ + -- Х₄ = -- (3)

3 3 3

Х₂ + Х₅ = 8

 

ИТЕРАЦИЯ 2

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х₁ Х₂ Х₃ Х₄ Х₅

Х₂ = 34

--- 0 26 0 8

и соответствующее ему значение целевой функции:

34 68

Z = 2 * --- + 3 * 0 + 0 * 26 + 0 * 0 + 0 * 8 = ---

3 3

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₂ = 1

Тогда Δ Х₃ = - 1

Δ Х₁ = - --

Δ Х₅ = - 1

 

4 8

Δ Z = 2 * (- ---) + 3 * 1 + 0 * (- 1) + 0 * 0 + 0 * (- 1) = - --- + 3 > 0

3 3

Вывод: Решение Х₂ не оптимальное. Переменную Х₂ целесообразно ввести в базис, поскольку от этого значение целевой функции увеличится.

ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

Х₃ = 26 - Х₂ 26 - Х₂ > 0 Х₂ < 26

 

34 4 34 4 34

Х₁ = --- - --Х₂ => --- - --- Х₂ > 0 => Х₂ < ---

3 3 3 3 4

 

Х₅ = 8 - Х₂ 8 - Х₂ > 0 Х₂ < 8 (*)

 

Вывод: В третьем уравнении базисной станет переменная Х₂, а переменная Х₅ выйдет из базиса.

ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.

Так как в системе (3) в третье уравнение переменная Х2 входит с коэффициентом +1, перепишем его в том же виде в новую систему (4) третьим уравнением.

Преобразуем систему уравнений (3) так, чтобы переменная Х2 отсутствовала в первых двух уравнениях.

Для этого:

1. Исключим переменную Х₂ из первого уравнения (из первого уравнения системы (3) вычтем третье уравнение новой системы (4)):

 

Х₂ + Х₃ - Х₄ = 26

Х₂ + Х₅ = 8

Х₃ - Х₄ - Х₅ = 18

 

Получим первое уравнение новой системы (4).

2. Исключим переменную Х₂ из второго уравнения (из второго уравнения системы (3) вычтем третье уравнение системы (4), умноженное на 4/3):

 

4 1 34

Х₁ + --Х₂ + -- Х₄ = ---

3 3 3

4 4 32

--Х₂ + -- Х₅ = ---

3 3 3

1 4 2

Х₁ + --Х₄ - --Х₅ = --

3 3 3

 

Получим второе уравнение новой системы (4).

 

После преобразований новая система уравнений будет иметь вид:

Х₃ - Х₄ - Х₅ = 18

 

 

1 4 2

Х₁ + --Х₄ - --Х₅ = -- (4)

3 3 3

Х₂ + Х₅ = 8

 

ИТЕРАЦИЯ 3.

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х₁ Х₂ Х₃ Х₄ Х₅

 

Х₃ = 2

-- 8 18 0 0

 

и соответствующее ему значение целевой функции:

 

2 76 1

Z = 2 * --- + 3 * 8 + 0 * 18 + 0 * 0 + 0 * 0 = --- = 25 ---

3 3 3

 

 

ШАГ 2. Проверяем оптимальность полученного решения.

 

Пусть Δ Х₄ = 1

Тогда Δ Х₃ = 1

Δ Х₁ = - --

Δ Х₂ = 0

 

1 2

Δ Z = 2 * (- ---) + 3 * 0 + 0 * 1 + 0 * 1 + 0 * 0 = - --- < 0.

3 3

 

Вывод: Так как Δ Z < 0, переменную Х₄ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

 

Шаг 2 продолжается.

 

Пусть Δ Х₅ = 1

Тогда Δ Х₃ = 1

Δ Х₁ = --

Δ Х₂ = - 1

 

4 8

Δ Z = 2 * --- + 3 * (- 1) + 0 * 1 + 0 * 0 + 0 * 1 = --- - 3 < 0.

3 3

 

Вывод: Так как Δ Z < 0, переменную Х₅ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

Вывод по шагу 2: Поскольку на данной итерации ни одну из небазисных переменных нецелесообразно вводить в базис, решение Х₃ является оптимальным.

 

Как можно заметить, среди компонент оптимального плана есть нецелые:

 

Х₁ =

Согласно алгоритму решения задач целочисленного линейного программирования, построим правильное отсечение по второму уравнению, где получилось нецелочисленное значение:

 

1 4 2

--- Х₄ - --- Х₅ > ---

3 3 3

т.е.

 

1 2 2

-- Х₄ + --Х₅ > -- (5)

3 3 3

Примечание 1. Символ … означает дробную часть числа. Дробной частью а числа а называется разность между этим числом и его целой частью [ а ], т.е. наибольшим целым числом, не превосходящим а.

Например, если а = 2---, то

 

1 1 1 1 1

2 -- = 2-- - [ 2-- ] = 2-- - 2 = --

3 3 3 3 3

 

21/3

0 1 2 3 х

 

 

если а = - 2 --, то

 

 

1 1 1 1 2

- 2 -- = - 2-- - [ - 2-- ] = - 2-- + 3 = --

3 3 3 3 3

 

- 21/3

-3 -2 -1 0 х

 

Сформируем новую систему (6), добавив в систему (4) полученное правильное отсечение (5):

Х₃ - Х₄ - Х₅ = 18

 

 

1 4 2

Х₁ + --Х₄ - --Х₅ = --

3 3 3

Х₂ + Х₅ = 8 (6)

 

 

1 2 2

--Х₄ + --Х₅ > --

3 3 3

 

Продолжим решение нашей задачи. Для этого сначала нужно записать задачу (6) в каноническом виде, добавив в четвертое ограничение переменную Х6 с коэффициентом (-1), а затем построить вспомогательную задачу, добавив в четвертое ограничение искусственную переменную Х₇.

Вспомогательная задача будет иметь следующий вид:

Х₃ - Х₄ - Х₅ = 18

 

 

1 4 2

Х₁ + --Х₄ - --Х₅ = --

3 3 3

Х₂ + Х₅ = 8 (7)

 

 

1 2 2

--Х₄ + --Х₅ - Х6 + Х7 = --

3 3 3

 

 

Хj > 0, j = 1, 7; Х₁, Х₂ – целые числа

 

Z = 2 * Х₁ + 3 *Х₂ + 0*Х₃ + 0*Х₄ + 0*Х₅ - 0*Х₆ - М*Х₇ = > max

 

 

ИТЕРАЦИЯ 4

ШАГ 1. Выписываем очередное допустимое базисное решение:

Х1 Х2 Х3 Х4 Х5 Х6 Х7

Х₄ = 2 2

-- 8 18 0 0 0 --

3 3

 

и соответствующее ему значение целевой функции.

 

2 2 76 2

Z = 2 * -- + 3 * 8 + 0 * 18 + 0 * 0 + 0 * 0 - 0 * 0 - --М = --- - --М > 0

3 3 3 3

 

 

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₄ = 1

Тогда Δ Х₃ = 1

Δ Х₁ = - --

Δ Х₂ = 0

Δ Х₇ = - --

 

1 1 2 1

Δ Z = 2 * (- --) + 3 * 0 + 0 * 1 + 0 * 1 + 0 * 0 - 0 * 0 - М (- --) = - -- + --М > 0

3 3 3 3

Вывод: Решение Х₄ неоптимальное. Переменную Х₄ целесообразно ввести в базис, поскольку при этом значение целевой функции увеличится.

 

ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.

Х₃ = 18 + Х₅ - -

2 4

Х₁ = -- + -- Х₅ - -

3 3

 

Х₂ = 8 - Х₅ => 8 - Х₅ > 0 => Х₅ < 8

 

2 2 2 2

Х₇ = --- - --- Х₅ -- - --Х₅ > 0 Х₅ < 1 (*)

3 3 3 3

 

Вывод: Замена базисной переменной должна произойти в четвертом уравнении. Переменная Х₅ станет базисной, а искусственная переменная Х₇ выйдет из базиса.

 

ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.

Преобразуем систему уравнений (7) так, чтобы в четвертое уравнение новой системы (8) переменная Х₅ вошла с коэффициентом +1, и отсутствовала бы в трех других.

Для этого:

1. Получим четвертое уравнение новой системы (8). Для чего четвертое уравнение системы (7) почленно умножим на 3/2 и коэффициент при Х₅ станет равным +1.

2. Исключим переменную Х₅ из трех первых уравнений системы (7). Получим три первые уравнения новой системы (8).

После преобразований новая система уравнений будет иметь вид:

 

1 3 3

Х₃ - -- Х₄ - -- Х₆ + -- Х₇ = 19

2 2 2

 

Х₁ + Х₄ - 2Х₆ + 2Х₇ = 2

 

1 3 3

Х₂ - --Х₄ + --Х₆ - -- Х₇ = 8 (7)

2 2 2

 

1 3 3

--Х₄ + Х₅ - --Х₆ + --Х₇ = 1

2 2 2

 

 

ИТЕРАЦИЯ 5

ШАГ 1. Выписываем очередное допустимое базисное решение:

 

Х1 Х2 Х3 Х4 Х5 Х6 Х7

Х₅ =

2 7 19 0 1 0 0

 

и соответствующее ему значение целевой функции:

 

Z = 2 * 2 + 3 * 7 + 0 * 19 + 0 * 0 + 0 * 1 - 0 * 0 - М * 0 = 25

 

ШАГ 2. Проверяем оптимальность полученного решения.

Пусть Δ Х₄ = 1

 

Тогда Δ Х₃ = --

Δ Х₁ = - 1

Δ Х₂ = --

Δ Х₅ = - --

 

1 1 1 1

Δ Z = 2 * (-1) + 3 * -- + 0 * -- + 0 * 1 + 0 * (- --) - 0 * 0 - М * 0 = - -- < 0

2 2 2 2

 

Вывод: Так как Δ Z < 0, переменную Х₄ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

 

Шаг 2 продолжаем.

Пусть Δ Х₆ = 1

 

Тогда Δ Х₃ = --

 

Δ Х₁ = 2

 

Δ Х₂ = - --

Δ Х₅ = --

 

3 3 3 1

Δ Z = 2 * 2 + 3 * (- --) + 0 * -- + 0 * 0 + 0 * -- - 0 * 1 - М * 0 = - -- < 0

2 2 2 2

Вывод: Так как Δ Z < 0, переменную Х₆ нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.

Вывод по шагу 2: Поскольку на данной итерации ни одну из небазисных переменных нецелесообразно вводить в базис, решение Х₅ является оптимальным.