Запасы сырья в столярной мастерской, расход его на изготовление одного
шкафа или стола, а также доход от продажи готового изделия - все это
указано в следующей таблице:
Требуется составить такой план производства, чтобы доход от реализации
шкафов и столов был наибольшим.
Замечание. На изготовление столов и шкафов идут и другие материалы:
клей, лак, шурупы, замки, ручки и др. Для упрощения будем считать, что
этих материалов достаточно для любого варианта плана.
Предположим, что мастерская сделает х шкафов и у столов, для этого
потребуется Зх + у толстых досок. А так как в наличии имеется 360 таких
досок, то должно выполняться неравенство Зх + у 360. Ведь мастерская
может получить наибольший доход и тогда, когда доски не будут
израсходованы полностью.
Рассуждая аналогично, получим следующие неравенства:
При этих условиях доход F, который получит мастерская, составит: F = l0X
+ 6Y (руб.). Таким образом, задачу можно
сформулировать так.
Дана система четырех неравенств первой степени (линейных неравенств):
которую называют линейной формой. Требуется среди неотрицательных (из
смысла хну ясно, что х>=0, г/>=0)
решений системы (1) выбрать такое, при котором форма (2) принимает
наибольшее значение.
Существует несколько способов решения поставленной задачи. Самый простой
из них - геометрический. Но прежде чем приступить к ее решению, выясним,
какая геометрическая картина соответствует системе неравенств.
Начнем с простейших примеров. Пусть дано неравенство у > 2. Выберем
прямоугольную систему координат хОу; очевидно, что этому неравенству
будут удовлетворять все точки плоскости, расположенные выше прямой у - 2
(рис. 1). На рисунке 2 заштрихована часть плоскости, точки которой
удовлетворяют неравенству х < 3, а на рисунке 3 - системе неравенств:
Вспомним, что математически эта задача нами была сформулирована так.
(рис. 8). Можно показать, что если прямая \\х + By + С = 0 перемещается
параллельно самой себе, удаляясь от начала координат, (причем
коэффициенты А и В не меняются, то коэффициент С общего уравнения прямой
возрастает по абсолютной величине. Значит, в нашей задаче с ростом
абсолютной величины С будет возрастать и линейная форма F. Теперь
понятно, как следует искать оптимальный план. Для этого через любую
точку многогранника решений неравенств проводим линию уровня (прямую) и
перемещаем ее параллельно самой себе в сторону возрастания линейной
формы. Мы остановимся, когда все точки области решений неравенств
окажутся по одну сторону от этой прямой. Из рисунка 7 ясно, что
оптимальному плану будет соответствовать точка пересечения прямых (III)
и (IV) - вершина многоугольника решений. Чтобы найти координаты этой
вершины, решим совместно уравнения прямых (III) и (IV);
Рассмотрим систему (4). Если сложим почленно первые три уравнения и
вычтем четвертое, то получим пятое уравнение. Значит, в системе (4)
пятое уравнение лишнее. О таком уравнении говорят, что оно - следствие
первых четырех уравнений, а о всей системе говорят, что она линейно
зависима. Поэтому из рассмотрения можно исключить пятое уравнение
(впрочем, в этом примере можно было бы исключить из системы любое из
данных пяти уравнений). Оставшиеся четыре уравнения уже будут линейно
независимы.
Таким образом, мы имеем четыре линейно независимых уравнения первой
степени с шестью неизвестными. Из этих уравнений четыре неизвестных
можно выразить через
два остальных. В этом случае говорят, что такая система имеет четыре
зависимых неизвестных и два свободных неизвестных
Очевидно, что значение формы будет уменьшаться с увеличением абсолютной
величины свободного члена в уравнениях линий уровня. Перемещая линию
уровня параллельно самой себе и удаляя при этом ее от начала координат,
видим, что наименьшее значение форма F примет в точке пересечения прямых
Еще раз прочитаем математические формулировки задачи об использовании
сырья и транспортной задачи. Мы замечаем, что они весьма схожи. Различие
заключается только в том, что в одной задаче была дана система линейных
неравенств, а в другой - система линейных уравнений. Но в ходе решения
второй задачи мы смогли перейти от системы уравнений к системе
неравенств.
В дальнейшем "мы покажем, что при надобности сможем так же легко
преобразовать неравенства в уравнения. Следовательно, можно сделать так,
что математические формулировки этих задач будут совершенно одинаковыми
(конечно, они будут отличаться количеством неизвестных и коэффициентами
при неизвестных).
Оказывается, такую математическую формулировку можно придать многим
задачам из области экономики. Общая формулировка этих задач будет такой:
дана система M алгебраических уравнений с
n неизвестными:
Система (6) называется системой ограничений данной задачи. Ограничения
могут быть заданы также в виде неравенств.
В рассмотренных нами задачах требовалось определить небольшое число
неизвестных (в первом два, во втором шесть), и в каждой из этих задач
было по два свободных неизвестных. При решении многих практических задач
приходится иметь дело с гораздо большим числом неизвестных. Например,
если рассмотреть транспортную задачу о перевозке однородного груза из 5
пунктов отправления в 20 пунктов назначения, то число неизвестных станет
равным 100, а свободных неизвестных будет 76 (в таблице будет 5 строк и
20 столбцов, система ограничений будет состоять из 25 уравнений, одно из
которых будет следствием остальных).
Оказывается, сложность решения задачи линейного программирования зависит
от количества свободных неизвестных. Чем их меньше, тем легче решить
задачу. Проще всего задача решается, когда имеется два свободных
неизвестных.
Именно такими были рассмотренные нами задачи. Напомним, что для решения
каждой из них мы построили соответствующий многоугольник решений и через
любую точку этого многоугольника провели линию уровня линейной формы.
Затем, перемещая линию уровня параллельно самой себе в сторону
возрастания (или убывания) линейной формы, нашли оптимальное решение.
Оно расположено на одной из вершин многоугольника решений.
В случае трех свободных неизвестных мы уже будем иметь дело с трехмерным
пространством, и системе неравенств будет соответствовать выпуклое
многогранное тело, или многогранник решений, а каждому конкретному
значению линейной формы - плоскость, которую называют поверхностью
уровня. И задачу в принципе можно было бы решать так же, как и при двух
свободных неизвестных: построить многогранник решений, через любую его
точку провести поверхность уровня и, перемещая параллельно самой себе в
сторону возрастания (убывания) линейной формы, найти оптимальное
решение. Соответствующая точка совпадет с одной из вершин многогранника
решений. Но сделать все эти построения на чертеже хотя и возможно, но
очень сложно.
А в случае четырех и более свободных неизвестных от чертежа трудно ждать
помощи. Поэтому для решения основной задачи линейного программирования
при трех и более свободных неизвестных необходимо искать другие методы.
Вспомним, что оптимальное решение получалось у нас на вершине
многоугольника решений; в случае, когда свободных неизвестных больше
двух, оптимальное решение всегда будет достигаться на вершине
многогранника решений. Правда, таких вершин может оказаться и две (это
случай, когда линия параллельна одной из сторон многоугольника решений),
тогда условию оптимальности удовлетворяет каждая точка отрезка,
соединяющего эти вершины; в трехмерном случае таких вершин может
оказаться даже три и т. д. Но и в этих случаях можно сказать, что если
оптимальное решение существует, то оно достигается на некоторой вершине
многогранника решений.
Значит, чтобы найти оптимальное решение некоторой задачи линейного
программирования, достаточно сравнить значения линейной формы во всех
вершинах многогранника решений и выбрать нужное. Кажется, все просто! Но
простота здесь только кажущаяся.
В самом деле, пусть в качестве многогранника решений будет одно из самых
простейших тел - многомерный куб, число его вершин можно подсчитать по
формуле:
В = 2n,
где В - число вершин, а п - размерность пространства. При
n = 2 (квадрат) В = 4; при
n = 3 (обычный трехмерный куб) В = 8; а, например, при
n = 10 (десятимерный куб) В = 1024; при
n = 76 (как в случае транспортной задачи о
перевозке груза из 5 пунктов отправления в 20 пунктов назначения) В
выражается числом из 23 цифр.
Отсюда видно, что если решать задачу таким методом, то в некоторых
случаях с ней не справится даже электронная счетная машина.
Чтобы упростить решение задач линейного программирования, чаще всего
стремятся сделать так, чтобы оптимальное решение совпало с началом
координат, где все свободные неизвестные равны нулю.
Обращаем внимание на то обстоятельство, что в случае оптимального
базисного решения системы коэффициенты при неизвестных в линейной форме
будут одного знака. Все они будут отрицательными, когда линейная форма
достигнет наибольшего значения, и положительными, когда линейная форма
достигнет наименьшего значения.
В заключение отметим, что если основная задача линейного
программирования имеет оптимальное решение, то существует оптимальное
базисное решение, которое может быть получено симплекс-методом из любого
базисного решения.
Сравнивая геометрический метод и симп-лекс-метод решения основной задачи
линейного программирования, видим, что первый быстрее приводит к цели,
но, как мы уже говорили, им можно воспользоваться лишь в случае двух
свободных неизвестных, а в случае трех и более свободных неизвестных
приходится пользоваться симплекс-методом.
Во многих случаях составление научно обоснованного плана связано с
решением задач, приводящихся к основной задаче линейного
программирования. При этом приходится решать задачи, содержащие сотни и
тысячи неизвестных. Для решения таких задач широко используются ЭВМ.
А.Т. Цветков
Размещение фотографий и
цитирование статей с нашего сайта на других ресурсах разрешается при
условии указания ссылки на первоисточник и фотографии.
