Последовательность решения задачи
Построение экономико-математической модели задачи
1. Переменные
Х1 - количество приобретаемых машин типа А, шт.
Х2 - количество приобретаемых машин типа В, шт.
2. Ограничения
1 По площади размещения машин, м2
3Х1 + 5Х2 < 60
2 По затратам денежных средств, млн руб.
(1)
3Х1 + 4Х2 < 34
3 По приобретению оборудования типа В, шт.
Х1 > 0, Х2 > 0, Х1, Х2 – целые числа.
3. Целевая функция
Критерий оптимальности – Максимум производительности оборудования, т.
Z = 2Х1 + 3Х2 => max
Математическая формулировка задачи.
Найти такие целочисленные значения переменных Х1 и Х2 , что выполняются ограничения задачи (1) и достигается максимальное значение целевой функции Z.
Экономическая формулировка задачи.
Определить, сколько необходимо приобрести оборудования типа А и сколько приобрести оборудования типа В, чтобы уложиться в выделенные ресурсы, выполнить план приобретения оборудования В и обеспечить максимальную производительность оборудования.
.
Подготовка задачи к решению симплексным методом
Запишем задачу (1) в каноническом виде:
 | |||
 | |||
3Х1 + 5Х2 + Х3 = 60
 |
3Х1 + 4Х2 + Х4 = 34 (2)
 |
Х2 + Х5 = 8
 |
Хj > 0, j = 1, 5 ; Х1, Х2 – целые числа
Z = 2Х1 + 3Х2 + 0Х3 + 0Х4 + 0Х5 = > max
Решение задачи симплексным методом
ИТЕРАЦИЯ 1
ШАГ 1.Выписываем исходное допустимое базисное решение
 |  |
Х1 Х2 Х3 Х4 Х5
Х1 =
0 0 60 34 8
и соответствующее ему значение целевой функции Z.
Z = 2 * 0 + 3 * 0 + 0 * 60 + 0 * 34 + 0 * 8 = 0.
ШАГ 2.Проверяем оптимальность полученного решения.
Пусть Δ Х1 = 1
Тогда Δ Х3 = -3
Δ Х4 = -3
Δ Х5 = 0
Δ Z = 2 * 1 + 3 * 0 + 0 * (-3) + 0 * (-3) + 0 * 0 = 2 > 0.
Вывод:Решение Х1 неоптимальное. Переменную Х1 целесообразно ввести в базис поскольку от этого значение целевой функции Z увеличится.
ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.
Х3 = 60 - 3Х1 60 - 3Х1 > 0 Х1 > 20
Х4 = 34 - 3Х1 = > 34 - 3Х1 > 0 = > Х1 > --- (*)
Х5 = 8 - 0 -- --
Замена прежней базисной переменной произойдет во втором уравнении.
Вывод: В новом базисе будут находиться переменные Х1, Х3, Х5, а переменная Х4 станет небазисной.
ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.
Для этого:
1. Разделим почленно второе уравнение системы (2) на 3. Это будет второеуравнение новой системы (3).
2. Исключим переменную Х1 из первого уравнения. Для этого из первого уравнения системы (2) вычтем второе уравнение системы (3), умноженное на 3:
3Х1 + 5Х2 + Х3 = 60
3Х1 + 4Х2 + Х4 = 34
Х2 + Х3 - Х4 = 26
Это будет первое уравнение новой системы (3).
3. Перепишем в новую систему уравнений (3) третье уравнение из системы (2) в том же виде
После таких преобразований новая система уравнений будет иметь вид:
Х2 + Х3 - Х4 = 26
4 1 34
Х1 + --Х2 + -- Х4 = -- (3)
3 3 3
 |
Х2 + Х5 = 8
ИТЕРАЦИЯ 2
ШАГ 1. Выписываем очередное допустимое базисное решение:
 |  |
Х1 Х2 Х3 Х4 Х5
Х2 = 34
--- 0 26 0 8
и соответствующее ему значение целевой функции:
34 68
Z = 2 * --- + 3 * 0 + 0 * 26 + 0 * 0 + 0 * 8 = ---
3 3
ШАГ 2. Проверяем оптимальность полученного решения.
Пусть Δ Х2 = 1
Тогда Δ Х3 = - 1
Δ Х1 = - --
Δ Х5 = - 1
4 8
Δ Z = 2 * (- --- ) + 3 * 1 + 0 * (- 1) + 0 * 0 + 0 * (- 1) = - --- + 3 > 0
3 3
Вывод:Решение Х2 не оптимальное. Переменную Х2 целесообразно ввести в базис, поскольку от этого значение целевой функции увеличится.
ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.
 |  |
Х3 = 26 - Х2 26 - Х2 > 0 Х2 < 26
34 4 34 4 34
Х1 = --- - --Х2 => --- - --- Х2 > 0 => Х2 < ---
3 3 3 3 4
Х5 = 8 - Х2 8 - Х2 > 0 Х2 < 8 (* )
Вывод: В третьем уравнении базисной станет переменная Х2, а переменная Х5 выйдет из базиса.
ШАГ 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных.
Так как в системе (3) в третье уравнение переменная Х2 входит с коэффициентом +1, перепишем его в том же виде в новую систему (4) третьим уравнением.
Преобразуем систему уравнений (3) так, чтобы переменная Х2 отсутствовала в первых двух уравнениях.
Для этого:
1. Исключим переменную Х2 из первого уравнения (из первого уравнения системы (3) вычтем третье уравнение новой системы (4)):
Х2 + Х3 - Х4 = 26
Х2 + Х5 = 8
Х3 - Х4 - Х5 = 18
Получим первое уравнение новой системы (4).
2. Исключим переменную Х2 из второго уравнения (из второго уравнения системы (3) вычтем третье уравнение системы (4), умноженное на 4/3):
4 1 34
Х1 + --Х2 + -- Х4 = ---
3 3 3
 |
4 4 32
--Х2 + -- Х5 = ---
3 3 3
1 4 2
Х1 + --Х4 - --Х5 = --
3 3 3
Получим второе уравнение новой системы (4).
После преобразований новая система уравнений будет иметь вид:
 | |||
 | |||
Х3 - Х4 - Х5 = 18
1 4 2
Х1 + --Х4 - --Х5 = -- (4)
3 3 3
 |
Х2 + Х5 = 8
ИТЕРАЦИЯ 3.
ШАГ 1. Выписываем очередное допустимое базисное решение:
 |
Х1 Х2 Х3 Х4 Х5
Х3 = 2
-- 8 18 0 0
и соответствующее ему значение целевой функции:
2 76 1
Z = 2 * --- + 3 * 8 + 0 * 18 + 0 * 0 + 0 * 0 = --- = 25 ---
3 3 3
ШАГ 2. Проверяем оптимальность полученного решения.
Пусть Δ Х4 = 1
Тогда Δ Х3 = 1
Δ Х1 = - --
Δ Х2 = 0
1 2
Δ Z = 2 * (- ---) + 3 * 0 + 0 * 1 + 0 * 1 + 0 * 0 = - --- < 0.
3 3
Вывод: Так как Δ Z < 0, переменную Х4 нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.
Шаг 2 продолжается.
Пусть Δ Х5 = 1
Тогда Δ Х3 = 1
Δ Х1 = --
Δ Х2 = - 1
4 8
Δ Z = 2 * --- + 3 * (- 1) + 0 * 1 + 0 * 0 + 0 * 1 = --- - 3 < 0.
3 3
Вывод: Так как Δ Z < 0, переменную Х5 нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.
Вывод по шагу 2: Поскольку на данной итерации ни одну из небазисных переменных нецелесообразно вводить в базис, решение Х3 является оптимальным.
Как можно заметить, среди компонент оптимального плана есть нецелые:
Х1 =
Согласно алгоритму решения задач целочисленного линейного программирования, построим правильное отсечение по второму уравнению, где получилось нецелочисленное значение:
1 4 2
--- Х4 - --- Х5 > ---
3 3 3
т.е.
1 2 2
-- Х4 + --Х5 > -- ( 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):
| |
Х3 - Х4 - Х5 = 18
1 4 2
Х1 + --Х4 - --Х5 = --
3 3 3
| |
Х2 + Х5 = 8 (6)
1 2 2
--Х4 + --Х5 > --
3 3 3
Продолжим решение нашей задачи. Для этого сначала нужно записать задачу (6) в каноническом виде, добавив в четвертое ограничение переменную Х6 с коэффициентом (-1), а затем построить вспомогательную задачу, добавив в четвертое ограничение искусственную переменную Х7.
Вспомогательная задача будет иметь следующий вид:
 |
Х3 - Х4 - Х5 = 18
1 4 2
Х1 + --Х4 - --Х5 = --
3 3 3
| |
Х2 + Х5 = 8 (7)
1 2 2
--Х4 + --Х5 - Х6 + Х7 = --
3 3 3
 |
Хj > 0, j = 1, 7; Х1, Х2 – целые числа
Z = 2 *Х1 + 3*Х2 + 0*Х3 + 0*Х4 + 0*Х5 - 0*Х6 - М*Х7 = > max
ИТЕРАЦИЯ 4
ШАГ 1. Выписываем очередное допустимое базисное решение:
 |
Х1 Х2 Х3 Х4 Х5 Х6 Х7
Х4 = 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.Проверяем оптимальность полученного решения.
Пусть Δ Х4 = 1
Тогда Δ Х3 = 1
Δ Х1 = - --
Δ Х2 = 0
Δ Х7 = - --
1 1 2 1
Δ Z = 2 * (- -- ) + 3 * 0 + 0 * 1 + 0 * 1 + 0 * 0 - 0 * 0 - М (- -- ) = - -- + --М > 0
3 3 3 3
Вывод: Решение Х4 неоптимальное. Переменную Х4 целесообразно ввести в базис, поскольку при этом значение целевой функции увеличится.
ШАГ 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.
Х3 = 18 + Х5 - -
2 4
Х1 = -- + -- Х5 - -
3 3
Х2 = 8 - Х5 => 8 - Х5 > 0 => Х5 < 8
2 2 2 2
Х7 = --- - --- Х5 -- - --Х5 > 0 Х5 < 1 (*)
3 3 3 3
Вывод: Замена базисной переменной должна произойти в четвертом уравнении. Переменная Х5 станет базисной, а искусственная переменная Х7 выйдет из базиса.
ШАГ 4.Пересчет системы линейных уравнений с учетом нового состава базисных переменных.
Преобразуем систему уравнений (7) так, чтобы в четвертое уравнение новой системы (8) переменная Х5 вошла с коэффициентом +1, и отсутствовала бы в трех других.
Для этого:
1. Получим четвертое уравнение новой системы (8). Для чего четвертое уравнение системы (7) почленно умножим на 3/2 и коэффициент при Х5 станет равным +1.
2. Исключим переменную Х5 из трех первых уравнений системы (7). Получим три первые уравнения новой системы (8).
После преобразований новая система уравнений будет иметь вид:
1 3 3
Х3 - -- Х4 - -- Х6 + -- Х7 = 19
2 2 2
Х1 + Х4 - 2Х6 + 2Х7 = 2
1 3 3
Х2 - --Х4 + --Х6 - -- Х7 = 8 (7)
2 2 2
1 3 3
--Х4 + Х5 - --Х6 + --Х7 = 1
2 2 2
ИТЕРАЦИЯ 5
ШАГ 1. Выписываем очередное допустимое базисное решение:
Х1 Х2 Х3 Х4 Х5 Х6 Х7
Х5 =
2 7 19 0 1 0 0
и соответствующее ему значение целевой функции:
Z = 2 * 2 + 3 * 7 + 0 * 19 + 0 * 0 + 0 * 1 - 0 * 0 - М * 0 = 25
ШАГ 2. Проверяем оптимальность полученного решения.
Пусть Δ Х4 = 1
Тогда Δ Х3 = --
Δ Х1 = - 1
Δ Х2 = --
Δ Х5 = - --
1 1 1 1
Δ Z = 2 * (-1) + 3 * -- + 0 * -- + 0 * 1 + 0 * (- -- ) - 0 * 0 - М * 0 = - -- < 0
2 2 2 2
Вывод: Так как Δ Z < 0 , переменную Х4 нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.
Шаг 2 продолжаем.
Пусть Δ Х6 = 1
Тогда Δ Х3 = --
Δ Х1 = 2
Δ Х2 = - --
Δ Х5 = --
3 3 3 1
Δ Z = 2 * 2 + 3 * (- -- ) + 0 * -- + 0 * 0 + 0 * -- - 0 * 1 - М * 0 = - -- < 0
2 2 2 2
Вывод: Так как Δ Z < 0 , переменную Х6 нецелесообразно вводить в базис, поскольку значение целевой функции от этого уменьшится.
Вывод по шагу 2: Поскольку на данной итерации ни одну из небазисных переменных нецелесообразно вводить в базис, решение Х5 является оптимальным.