2.2. Нахождение координат угловых точек симплекса решений.
Нахождение координат точек O, A, D не представляет особых трудностей, и их можно сразу же выписать:
O (0;0)
A (0;200)
D (200;0)
Для нахождения координат точки C предварительно отметим, что она является точкой пересечения прямых (2.1) и (2.2). Следовательно, для нахождения ее координат необходимо совместно решить уравнения этих прямых.
Таким образом, координаты точки C (140; 120).
Точка B лежит на пересечении прямых (2.2) и (2.3). Поэтому ее координаты находим, решая следующую систему уравнений:
Таким образом, координаты точки B (60; 180).
2.3. Выбор оптимального плана.
В линейном программировании доказывается теорема о том, что если оптимальное решение задачи линейного программирования существует, то оно обязательно совпадает с координатами одной из угловых точек симплекса решений системы линейных ограничений (2).
Вычисляем значения целевой функции (1) в каждой угловой точке и выбираем наибольшее:
Таким образом, оптимальный план выпуска изделий соответствует точке C и равен x1=140 шт. Изделия 1 и x2=120 шт. Изделия 2. Выручка от реализации в этом случае будет максимальна и составит 13200 руб.
Найдем остатки сырья каждого типа, обозначая их x3; x4; x5 соответственно.
Ответ: Оптимальный план выпуска изделий составляет x1=140 шт. Изделия 1 и x2=120 шт. Изделия 2. Выручка от их последующей реализации в этом случае будет максимальна и составит 13200 руб. При этом все запасы Сырья I и Сырья II будут израсходованы полностью, а остаток Cырья III составит 100 кг.
3. Симплексный метод решения задачи.
Для решения задачи этом методом ее необходимо записать в канонической форме. Для этого введем еще три дополнительные переменные, которые имеют смысл остатков сырья после окончания производства всех запланированных изделий, а именно:
- остатки сырья первого типа;
-
остатки сырья второго типа;
-
остатки сырья третьего типа.
Тогда система ограничений задачи примет вид:
Уравнения (3.1)-(3.3) выражают собой баланс сырья в процессе производства.
Задача линейного программирования с системой ограничений (3) и целевой функцией (1), называется канонической формой записи задачи линейного программирования.
Симплексный метод решения задачи линейного программирования позволяет свести все вычисления к заполнению стандартных таблиц—симплекс-таблиц - по стандартным правилам.
Каждой симплекс-таблице соответствует план выпуска изделий. Пересчет таблиц продолжают до тех пор, пока очередная симплекс-таблица не будет соответствовать оптимальному плану выпуска.
3.1. Построение симплекс-таблицы № 1.
Симплекс-таблица № 1
|
Неизвестные |
|
||||
Базис |
x1 |
x2 |
x3 |
x4 |
x5 |
bi |
x3 |
2 |
1 |
1 |
0 |
0 |
400 |
x4 |
3 |
4 |
0 |
1 |
0 |
900 |
x5 |
1 |
3 |
0 |
0 |
1 |
600 |
-F |
60 |
40 |
0 |
0 |
0 |
0 |
1) В первой строке симплекс-таблицы помещены все переменные х1, х2, x3, х4, х5, а во второй - четвертой строках коэффициенты, стоящие при этих переменных в системе (3).
В первом столбце расположены переменные x3, х4, х5, принятые за базисные на данном шаге, а в последнем столбце - свободные члены системы (3): 400, 900, 600. Этим же значениям на данном шаге равны базисные переменные соответственно по строкам.
Последняя строка таблицы называется индексной. В ней размещены стоимости выпускаемых изделий в соответствующих столбцах, а в последнем столбце этой индексной строки стоит -F, получаемая сумма с обратным знаком от реализации предполагаемого к выпуску количества изделий.
Для первой симплекс-таблицы свободными переменными будут х1, x2, которые «автоматически» приравниваются к нулю. Очевидно, что это соответствует нулевому плану выпуска изделий, поэтому базисные переменные будут равны x3 = 400, x4 = 900, x5 = 600.
Значение целевой функции при этом, естественно, равно нулю:
.