Методы оптимальных решений

Задание 1

F = 7×1+x2 > max/min, при системе ограничений:

x1+3×2?2.

• 4x1−2×2?35
• 5x1−13×2?18

x1? 0.

x2? 0.

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

x1+3×2=2 (1) прямая, проходит через точки (2;0) и (-1;1),.

• 4x1−2×2=35 (2) прямая, проходит через точки (9,75; 2) и (8,75; 0)
• 5x1−13×2=18 (3) прямая, проходит через точки (1; -1) и (3,6; 0)

x1 = 0 (4) ось Ох2.

x2 = 0 (5) ось Ох1.

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

Обозначим границы области многоугольника решений.

Построим прямую, отвечающую значению функции F = 0: F = 7×1+x2 = 0.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F (X). Начало вектора — точка (0; 0), конец — точка (7; 1).

Определим границы ограниченной области:

1) Так как точка A получена в результате пересечения прямых (5) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

2) Так как точка B получена в результате пересечения прямых (2) и (5), то ее координаты удовлетворяют уравнениям этих прямых:

3) Так как точка С получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Сравним значения целевой функции в вершинах области:

F (A)= 7*3,6 + 1*0 = 25,2 минимальное значение.

F (B)= 7*8,75 + 1*0 = 61,25.

F© = 7*9,98+1*2,45 = 72,29 максимальное значение.

Ответ: максимальное значение целевой функции F (X) = 72,29 в точке; минимальное значение целевой функции F (X) = 25,2 в точке .

Задание 2

Так как нужно определить объёмы производства каждого вида продукции, переменными являются:

X1 — объём производства изделия, А в шт.

Х2 — объём производства изделия В в шт.

Целевая функция. Так как стоимость 1 изделия, А равна16 руб., доход от её продажи составит 16Х1 руб. Аналогично доход от реализации изделия В составит 19Х2 руб. При допущении независимости объёмов сбыта каждого из изделий общий доход равен сумме двух слагаемых — дохода от продажи изделий, А и дохода от продажи изделий В.

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

f (X) = 16X1 + 19X2.

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

Максимальное значение целевой функции F (X) = 16×1+19×2 при следующих условиях-ограничений.

• 19×1+31×2?1121
• 16×1+9×2?706
• 19×1+x2?1068

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

• 19×1 + 31×2 + 1×3 + 0×4 + 0×5 = 1121
• 16×1 + 9×2 + 0×3 + 1×4 + 0×5 = 706
• 19×1 + 1×2 + 0×3 + 0×4 + 1×5 = 1068

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

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

Решим систему уравнений относительно базисных переменных: x3, x4, x5.

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,1121,706,1068).

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

min (1121: 31, 706: 9, 1068: 1) = 365/31.

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (20) и находится на пересечении ведущего столбца и ведущей строки.

Вместо переменной x3 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент =31. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

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

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

min (365/31: 19/31, 38 017/31: 1015/31, 103 126/31: 1812/31) = 3697/325 полуплоскость неравенство целевой многоугольник Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (1015/31) и находится на пересечении ведущего столбца и ведущей строки.

Вместо переменной x4 в план 2 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент =1015/31. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.

Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

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

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Оптимальный план можно записать так:

x1 = 3697/325?36,3, x2 = 13 297/325? 13,9.

F (X) = 16*3697/325 + 19*13 297/325 = 8459/65? 845,14.

Ответ: Максимальная прибыль составит 8459/65? 845,14 руб при реализации 3697/325?36,3, изделий вида, А и 13 297/325? 13,9изделий вида В.

Задание 3

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

Проверим необходимое и достаточное условие разрешимости задачи.

• ?a = 200 + 300 + 250 = 750
• ?b = 210 + 150 + 120 + 135 + 135 = 750

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

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

План начинается заполняться с верхнего левого угла. Искомый элемент равен 20. Для этого элемента запасы равны 200, потребности 210. Поскольку минимальным является 200, то вычитаем его. x11 = min (200,210) = 200.

Движемся вправо по строке — искомый элемент равен 27. Для этого элемента запасы равны 300, потребности 10. Поскольку минимальным является 10, то вычитаем его. x21 = min (300,10) = 10.

Далее искомый элемент равен 19. Для этого элемента запасы равны 290, потребности 150. Поскольку минимальным является 150, то вычитаем его. x22 = min (290,150) = 150.

Искомый элемент равен 20. Для этого элемента запасы равны 140, потребности 120. Поскольку минимальным является 120, то вычитаем его. x23 = min (140,120) = 120.

Искомый элемент равен 16. Для этого элемента запасы равны 20, потребности 135. Поскольку минимальным является 20, то вычитаем его. x24 = min (20,135) = 20.

Искомый элемент равен 16. Для этого элемента запасы равны 20, потребности 135. Поскольку минимальным является 20, то вычитаем его. x24 = min (20,135) = 20.

Искомый элемент равен 23. Для этого элемента запасы равны 135, потребности 135. Поскольку минимальным является 135, то вычитаем его. x35 = min (135,135) = 135.

Получили следующий опорный план:

Таблица 1.

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n — 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F (x) = 20*200 + 27*10 + 19*150 + 20*120 + 16*20 + 21*115 + 23*135 = 15 360.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 20; 0 + v1 = 20; v1 = 20.

u2 + v1 = 27; 20 + u2 = 27; u2 = 7.

u2 + v2 = 19; 7 + v2 = 19; v2 = 12.

u2 + v3 = 20; 7 + v3 = 20; v3 = 13.

u2 + v4 = 16; 7 + v4 = 16; v4 = 9.

u3 + v4 = 21; 9 + u3 = 21; u3 = 12.

u3 + v5 = 23; 12 + v5 = 23; v5 = 11.

Таблица 2.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij.

• (1;2): 0 + 12 > 10; ?12 = 0 + 12 — 10 = 2
• (3;1): 12 + 20 > 26; ?31 = 12 + 20 — 26 = 6
• (3;2): 12 + 12 > 17; ?32 = 12 + 12 — 17 = 7
• (3;3): 12 + 13 > 19; ?33 = 12 + 13 — 19 = 6

max (2,6,7,6) = 7.

Выбираем максимальную оценку свободной клетки (3;2): 17.

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» .

Таблица 3.

Цикл приведен в таблице (3,2 > 3,4 > 2,4 > 2,2).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 4) = 115. Прибавляем 115 к объемам грузов, стоящих в плюсовых клетках и вычитаем 115 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 4.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 20; 0 + v1 = 20; -v1 = 20.

u2 + v1 = 27; 20 + u2 = 27; u2 = 7.

u2 + v2 = 19; 7 + v2 = 19; v2 = 12.

u3 + v2 = 17; 12 + u3 = 17; u3 = 5.

u3 + v5 = 23; 5 + v5 = 23; v5 = 18.

u2 + v3 = 20; 7 + v3 = 20; v3 = 13.

u2 + v4 = 16; 7 + v4 = 16; v4 = 9.

Таблица 5.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij.

• (1;2): 0 + 12 > 10; ?12 = 0 + 12 — 10 = 2
• (2;5): 7 + 18 > 22; ?25 = 7 + 18 — 22 = 3

max (2,3) = 3.

Выбираем максимальную оценку свободной клетки (2;5): 22.

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» .

Таблица 6.

Цикл приведен в таблице (2,5 > 2,2 > 3,2 > 3,5).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 2) = 35. Прибавляем 35 к объемам грузов, стоящих в плюсовых клетках и вычитаем 35 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 7.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 20; 0 + v1 = 20; v1 = 20.

u2 + v1 = 27; 20 + u2 = 27; u2 = 7.

u2 + v3 = 20; 7 + v3 = 20; v3 = 13.

u2 + v4 = 16; 7 + v4 = 16; v4 = 9.

u2 + v5 = 22; 7 + v5 = 22; v5 = 15.

u3 + v5 = 23; 15 + u3 = 23; u3 = 8.

u3 + v2 = 17; 8 + v2 = 17; v2 = 9.

Таблица 8.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij.

• (3;1): 8 + 20 > 26; ?31 = 8 + 20 — 26 = 2
• (3;3): 8 + 13 > 19; ?33 = 8 + 13 — 19 = 2

max (2,2) = 2.

Выбираем максимальную оценку свободной клетки (3;1): 26.

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» .

Таблица 9.

Цикл приведен в таблице (3,1 > 3,5 > 2,5 > 2,1).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 10.

u1 + v1 = 20; 0 + v1 = 20; v1 = 20.

u3 + v1 = 26; 20 + u3 = 26; u3 = 6.

u3 + v2 = 17; 6 + v2 = 17; v2 = 11.

u3 + v5 = 23; 6 + v5 = 23; v5 = 17.

u2 + v5 = 22; 17 + u2 = 22; u2 = 5.

u2 + v3 = 20; 5 + v3 = 20; v3 = 15.

u2 + v4 = 16; 5 + v4 = 16; v4 = 11.

Таблица 11.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij.

• (1;2): 0 + 11 > 10; ?12 = 0 + 11 — 10 = 1
• (1;3): 0 + 15 > 13; ?13 = 0 + 15 — 13 = 2
• (3;3): 6 + 15 > 19; ?33 = 6 + 15 — 19 = 2

max (1,2,2) = 2.

Выбираем максимальную оценку свободной клетки (1;3): 13.

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» .

Таблица 12.

Цикл приведен в таблице (1,3 > 1,1 > 3,1 > 3,5 > 2,5 > 2,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 5) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 13.

u1 + v1 = 20; 0 + v1 = 20; v1 = 20.

u3 + v1 = 26; 20 + u3 = 26; u3 = 6.

u3 + v2 = 17; 6 + v2 = 17; v2 = 11.

u1 + v3 = 13; 0 + v3 = 13; v3 = 13.

u2 + v3 = 20; 13 + u2 = 20; u2 = 7.

u2 + v4 = 16; 7 + v4 = 16; v4 = 9.

u2 + v5 = 22; 7 + v5 = 22; v5 = 15.

Таблица 14.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij.

(1;2): 0 + 11 > 10; ?12 = 0 + 11 — 10 = 1.

Выбираем максимальную оценку свободной клетки (1;2): 10.

Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» .

Таблица 15.

Цикл приведен в таблице (1,2 > 1,1 > 3,1 > 3,2).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (1, 1) = 110. Прибавляем 110 к объемам грузов, стоящих в плюсовых клетках и вычитаем 110 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 16.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v2 = 10; 0 + v2 = 10; v2 = 10.

u3 + v2 = 17; 10 + u3 = 17; u3 = 7.

u3 + v1 = 26; 7 + v1 = 26; v1 = 19.

u1 + v3 = 13; 0 + v3 = 13; v3 = 13.

u2 + v3 = 20; 13 + u2 = 20; u2 = 7.

u2 + v4 = 16; 7 + v4 = 16; v4 = 9.

u2 + v5 = 22; 7 + v5 = 22; v5 = 15.

Таблица 17.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij.

(3;3): 7 + 13 > 19; ?33 = 7 + 13 — 19 = 1.

Выбираем максимальную оценку свободной клетки (3;3): 19.

Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» .

Таблица 18.

Цикл приведен в таблице (3,3 > 3,2 > 1,2 > 1,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 2) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 19.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v2 = 10; 0 + v2 = 10; v2 = 10.

u1 + v3 = 13; 0 + v3 = 13; v3 = 13.

u2 + v3 = 20; 13 + u2 = 20; u2 = 7.

u2 + v4 = 16; 7 + v4 = 16; v4 = 9.

u2 + v5 = 22; 7 + v5 = 22; v5 = 15.

u3 + v3 = 19; 13 + u3 = 19; u3 = 6.

u3 + v1 = 26; 6 + v1 = 26; v1 = 20.

Таблица 20.

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj? cij.

Минимальные затраты составят: F (x) = 10*150 + 13*50 + 20*30 + 16*135 + 22*135 + 26*210 + 19*40 = 14 100.

Ответ: Минимальные затраты составят: F (x) = 14 100.

При этом из 1-го склада необходимо направить во 2-й магазин 150 единиц груза, в 3-й магазин 50 единиц груза. Из 2-го склада необходимо направить в 3-й магазин 30 единиц груза, в 4-й магазин 135 единиц груза, в 5-й магазин 135 единиц груза. Из 3-го склада необходимо направить в 1-й магазин 210 единиц груза, в 3-й магазин 40 единиц груза.