20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.
Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при
– 85/7
Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль
Практические рекомендации таковы: надо выпустить 17143 кухни, вчетверо меньше, т. е. 4286, кофемолок, самоваров не выпускать вообще. При этом прибыль будет максимальной и равной 308571. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.
Транспортная задача. Различные технико—экономические и экономические задачи менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В качестве очередного примера рассмотрим т. н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по—разному организовать «прикрепление» потребителей к складам, т. е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.
Например, может идти речь о перевозке песка – сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом – водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов – их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться. Поэтому затраты на доставку товара с определенного склада тому или иному потребителю можно считать известными.
Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 3. В ней, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада
Надо спланировать перевозки, т. е. выбрать объемы
Во—вторых, известны потребности клиентов:
Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны – еще 12 ограничений.
Целевая функция – издержки по перевозке, которые необходимо минимизировать:
+ +3
Кроме обсуждаемой, рассматриваются также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.
Линейное программирование имеет дело с числовыми переменными. Если вспомнить общую постановку оптимизационной задачи, приведенную в начале главы, то
3.2.2. Целочисленное программирование
Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к целочисленному программированию. Рассмотрим несколько таких задач.
Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м 2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м 2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м 2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.
Пусть
При этом должны быть выполнены следующие ограничения:
по стоимости (в тыс. долларов США)
5
по занимаемой площади (в м 2)
8
а также вновь появляющиеся специфические ограничения по целочисленности, а именно,
Сформулированная математическая задача отличается от задачи линейного