Методика решения задач линейного программирования

Пусть предприятие производит всего два вида приборов А и В (п = 2), для чего необходимы два вида ресурсов — оборудование а и b (т = 2). На производство единицы прибора А оборудование а используется 2 часа (а₂1 = 2), а оборудование Ъ — 1 час (а₂₁ = 1). На производство единицы прибора В оборудование а используется 1 час (а₁₂ = 1), а оборудование Ь — 2 часа (а₂₂ = 2). Администрация предприятия может выделить для изготовления приборов А и В оборудование а в течение 10 часов (Ь_а = 10), оборудование b — в течение 8 часов (Ь₂ = 8). Прибыль от единицы прибора, А — 5 у.е. (Cj = 5), от единицы прибора В — 2 у.е. (С₂ = 2).

Тогда условия (8.1) и (8.2) запишутся в виде:

Для решения задачи неравенства превращаются в равенства введением дополнительных переменных. В данном примере эти переменные будут обозначать время, в течение которого не используется оборудование а и Ь:

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

Эту же задачу можно решать при условии, что за каждый час простоя оборудования взимается штраф 1 у.е. В этом случае вместо выражения (8.6) целевая функция будет иметь вид:

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

Рассмотрим решение системы (8.5) при условии (8.7). В соответствии с постановкой задачи должны быть найдены неотрицательные значения х_х и х₂, максимизирующие функцию С (неотрицательность искомых переменных является одним из условий, характеризующих задачи линейного программирования). Решать будем так называемым симплекс-методом Данцига, сущность которого заключается в последовательном улучшении решения и доведении его до оптимального.

За исходное решение принимают произвольное. Удобно принимать такое, где исходные переменные (х_х, х₂) полагаются равными нулю, а дополнительные переменные (у₃, у₄) равны свободным членам уравнений. В нашем примере х_х =х₂ = 0;у₃ = 10; у₄ = 8. Переменные, не равные нулю, будем называть основными независимо от того, исходные они или дополнительные, а переменные, равные нулю, — неосновными.

Выразим целевую функцию через неосновные переменные х_ь х₂ из системы (8.5):

Подставляя (8.8) в (8.7), получим.

Таким образом, исходное решение будет равно:

В системе (8.5) основные переменные (у₃, у₄), имеющие коэффициенты, равные 1, и условие максимума (8.9), выраженное через неосновные переменные, являются исходными для выполнения первого шага оптимизации. Наша цель — увеличить значение С. Можно ли это сделать, переведя в основные (не равные нулю) переменные х_а или х₂? В данном случае можно, так как х_х > 0, х₂ > 0 и с ростом х_х или х₂ функция С будет расти. Из двух переменных х_х и х₂ в основную переводим ту, у которой больше коэффициент в целевой функции, так как при этом получим большее приращение целевой функции и, следовательно, потребуется меньшее число итераций (шагов решения) для получения оптимального решения. Переводим в основные переменные X], т. е. берем х_х > 0. Какое же численное значение можно взять для Xj? Исходя из поставленной задачи, мы видим, что чем больше х_х, тем больше С. Но при этом необходимо учитывать ограничения (8.8) и условие неотрицательности переменных. Из первого уравнения системы (8.8) можно увеличить до 5, из второго — до 8. Выбирает х_х = 5, т. е. наименьшее из двух положительных отношений.

Основная переменная предыдущего решения у₃ перейдет теперь в неосновную (у₃ = 0). Из первого уравнения системы (8.8) запишем выражение и подставим его во второе уравнение системы (8.8) и в функцию (8.9). В итоге получим:

Следовательно, вторым решением будет.

Выполним второй шаг оптимизации. Так как в выражении (8.11) коэффициент при у₃ отрицателен, то увеличение С достигается только за счет увеличения переменной х_ъ которая должна быть переведена в основную. Для выбора значения х₂ из (8.10) получаем соотношения.

1₁_ _з₁.

ll/2'3/2j.

Отсюда максимальное возможное значение х₂ равно 2, при этом у₄ = = 0. Находим х₂ из второго уравнения (8.10):

и подставляем в (8.10) и (8.11):

Полученное третье решение {x_1; х_ъ у3, у₄} = {4, 2, 0, 0} является оптимальным, так как коэффициенты неосновных переменных у₃, у₄ в выражении (8.13) отрицательны и никакое положительное значение Уз илиу₄не может увеличить целевую функцию С = 24. Таким образом, поиск оптимального решения сводится к переходу от одного возможного (допустимого) решения к другому, причем величина С возрастает на каждом шаге. О достижении оптимальности судят по знакам коэффициентов целевой функции.

Решение данного простого примера может быть интерпретировано геометрически.

Если и х₂ рассматривать как координаты точек на плоскости, то все точки многоугольника 0АВС, являющегося общей частью треугольников ОAN и ОМС, удовлетворяют неравенствам (8.3) и могут быть решениями нашей задачи (рис. 8.1). Многоугольник ОАВС образует область допустимых решений. Исходному решению соответствует точка 0 (0,0) на плоскости, которая дает С = -18. Второе решение соответствует точке А (5,0) при С = 22 и третье — точке В (4,2) при С = 24. Решение задач линейного программирования сводится, таким образом, к перебору вершин многоугольника, оптимальное решение обязательно получается в одной из вершин, так как задача линейная и оптимума внутри области возможных решений не может быть.

Рис. 8.1. Графическое представление задачи линейного программирования

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