Х 1 = Х 2 = Х 3 = 0, Х 4 = Х 5 = Х 6 = 100, F = 0.
В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.
В соответствии с симплекс—методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х 1.
Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х 1:
100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞.
Выбираем строку из системы уравнений, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере – это первая строка, которой соответствует отношение 20000.
Умножим первую строку на 200, чтобы получить Х 1 с единичным коэффициентом:
Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000.
Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с Х 1, получим
7/900 Х 2 + 4/900 Х 3 – 2/3 Х 4 + Х 5 = 100/3.
Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F , получим:
2 Х 2 – 11 Х 3 – 3000 Х 4 = F – 300000.
В результате система уравнений преобразуется к виду, в котором переменная Х 1 входит только в первое уравнение:
Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000,
7/900 Х 2 + 4/900 Х 3 – 2/3 Х 4 + Х 5 = 100/3,
Х 3 / 80 + Х 6 = 100,
2 Х 2 – 11 Х 3 – 3000 Х 4 = F – 300000.
Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее другой вершине выпуклого многогранника в шестимерном пространстве:
Х 1 = 20000, Х 2 = Х 3 = Х 4 = 0, Х 5 = 100/3, Х 6 = 100, F = 300000.
В терминах исходной задачи это решение означает, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.
Повторим описанную выше операцию. В строке с F имеется еще один положительный коэффициент – при Х 2 (если бы положительных коэффициентов было несколько – мы взяли бы максимальный из них). На основе коэффициентов при Х 2 (а не при Х 1, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:
20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.
Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х 2 равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х 2, предварительно умножив их на подходящие числа, т. е. такие, чтобы все коэффициенты при Х 2 стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:
Х 1 + 9/7 Х 3 + 1800/7 Х 4 – 600/7 Х 5 = 120000/7,
Х 2 + 4/7 Х 3 – 600/7 Х 4 + 900/7 Х 5 = 30000/7,
Х 3 / 80 + Х 6 = 100,
– 85/7 Х 3 – 19800/7 Х 4 – 1800/7 Х 5 = F – 308571.
Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х 3 = Х 4 = Х 5 = 0. Из остальных уравнений следует, что при этом Х 1 = 120000/7 = 17143, Х 2 = 30000/7 = 4286, Х 6 = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс—метода закончил свою работу, оптимальное решение найдено.
Практические рекомендации таковы: надо выпустить 17143 кухни, вчетверо меньше, т. е. 4286, кофемолок, самоваров не выпускать вообще. При этом прибыль будет максимальной и равной 308571. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.
Транспортная задача. Различные технико—экономические и экономические задачи менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В качестве очередного примера рассмотрим т. н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по—разному организовать «прикрепление» потребителей к складам, т. е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.
Например, может идти речь о перевозке песка – сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом – водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов – их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться. Поэтому затраты на доставку товара с определенного склада тому или иному потребителю можно считать известными.
Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 3. В ней, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i, i = 1,2,3, потребителю j, j = 1,2,3,4. Например, самая дешевая доставка – со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение – при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.
Надо спланировать перевозки, т. е. выбрать объемы Х ij поставок товара со склада i потребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во—первых, заданы запасы на складах:
X 11 + Х 12 + Х 13 + Х 14 = 60,
X 21 + Х 22 + Х 23 + Х 24 = 80,
X 31 + Х 32 + Х 33 + Х 34 = 60.
Во—вторых, известны потребности клиентов:
X 11 + Х 21 + Х 31 = 50 ,
X 12 + Х 22 + Х 32 = 40 ,
X 13 + Х 23 + Х 33 = 70 ,
X 14 + Х 24 + Х 34 = 40 .
Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны – еще 12 ограничений.
Целевая функция – издержки по перевозке, которые необходимо минимизировать:
F = 2 X 11 + 5 Х 12 + 4 Х 13 + 5 Х 14 + X 21 + 2 Х 22 + Х 23 + 4 Х 24 +
+ +3 X 31 + Х 32 + 5 Х 33 + 2 Х 34 → min.
Кроме обсуждаемой, рассматриваются также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.
Линейное программирование имеет дело с числовыми переменными. Если вспомнить общую постановку оптимизационной задачи, приведенную в начале главы, то Х – вектор в конечномерном линейном пространстве, А – многогранник в таком пространстве. Рассмотрим несколько задач оптимизации, в которых Х и А имеют иную математическую природу.
3.2.2. Целочисленное программирование
Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к целочисленному программированию. Рассмотрим несколько таких задач.
Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м 2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м 2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м 2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.
