Примеры

Имеется 10 работ (А і А2), каждая из которых характеризуется тремя технико-экономическими показателями:

а] — трудозатраты;

bj — размер, необходимых капиталовложений;

с-j — ожидаемый экономический эффект.

Исходные данные приведены в следующей таблице: \r\n Ах Аг А, Аа As А6 А, Ац As Ло\r\naJ 3 3 3 4 4 2 4 3 6 5\r\nbJ 4 3 2 4 6 4 3 5 3 4\r\nCJ 3 7 5 6 8 4 7 4 7 6\r\nОбщие трудозатраты не должны превышать 20.

і і Al0 vA2 As V A8 V Л9 A6

Решение. Помимо целевой функции и двух ограничений по общему объему трудозатрат и капиталовложений, данную задачу характеризует следующая система неравенств:

X, < х7, х3 < Xg, Х7 < Xjq, х9 < х6,

Х10 + Х2<1, х5 + х8<1, х7 + х4<1, Х8+Х9<1.

В результате расчетов получаем х* = (0101110010).

Пример 2. Оптимизация производственной программы.

Автомобилестроительный завод выпускает три модели автомобилей, которые изготавливаются последовательно в трех цехах. Мощность цехов составляет 300, 250 и 200 человекодней в декаду. В первом цехе для сборки одного автомобиля первой модели требуется б человекодней, второй модели — 4 и третьей модели — 2 человекодня в декаду соответственно. Во втором цехе трудоемкость равна 3,4 и 5 человекодней соответственно, в третьем — по 3 человекодня на каждую модель. Прибыль, получаемая заводом от продажи одного автомобиля каждой модели, составляет соответственно 15, 13 и 10 тыс. долл.

Постройте модель для определения оптимального плана.

Решение. Пусть Xi — количество выпускаемых автомобилей i-й модели в течение декады (i = 1,..., n).

В принятых обозначениях модель имеет вид 15Х| + 13x2 + 10х3 шах, 6Х| + 4х2 + 2Х3< 300, Зх, + 4x2 + 5хз - 250> 3(xt + Xj + х3) < 200, X,, Х2, Х3 — Целые.

Пример 3.

Из минимального количества листов стекла размером 8 х 6 м2 требуется вырезать 10 оконных стекол размером 4 х 4 м2, 20 оконных стекол размером 4 х 5 м2 и 30 оконных стекол размером 3х3 м2. Множество вариантов раскроя (см. главу 3) показано в следующей таблице:\r\n^^ Размер, м2 4x4 4x5 3x3\r\nВариант \r\nI 2 — —\r\n2 1 1 —\r\n3 1 2\r\n4 — 2 —\r\n5 — — 4\r\n6 — 1 2\r\nПостроите модель для определения плана раскроя, требующего минимального количества материала.

Решение. Пусть Хі — количество листов стекла размером 8 х 6 м2, которые следует раскроить по варианту i.

Тогда модель имеет вид

п

F(x) = Z х, min, /= 1 \' 7

2х, + *2 + х3 > 10,

х2 + 2х4 + х6 > 20,

2х3 + 4х5 + 2х6 > 30,

x,, xj, ..., х6 — ЦЕЛЫЕ.

Пример 4. Задача о ранце.

Некая торговая компания имеет свои универсамы в Москве, Санкт-Петербурге, Нижнем Новгороде, Екатеринбурге, Самаре, Воронеже и Казани. В результате ошибок менеджмента экономическое положение компании стало ухудшаться, ей пришлось взять кредит в размере 13 млн руб. и в конечном счете, чтобы вовремя его погасить, срочно продавать некоторые из своих универсамов. Средства, которые компания могла бы получить от продажи универсамов в Москве, Санкт-Петербурге, Нижнем Новгороде, Екатеринбурге, Самаре, Воронеже или Казани, составляют соответственно 5,2; 4,9; 4,5; 3,6; 3,4; 3,2 и 3,1 млн руб. Однако продажа универсамов сопряжена с необходимостью увольнения персонала. Его численность составляет соответственно 200,190,180,170, 150,130 и 110 человек. По требованию объединенного профсоюза работников торговли компания должна минимизировать численность увольняемого персонала.

Постройте модель для нахождения оптимального решения.

Решение. Пронумеруем города в соответствии с порядком их перечисления. Пусть Хі = 1, если универсам, расположенный в городе, продается, и Хі = 0 в противном случае. Тогда оптимизационная модель имеет вид

200х, + 190Х2 + 180х3 + 170х4 + 150х3 + 130х6 + 110х7 -> min,

5,2х, + 4,9x2 + 4,5х3 + 3,6х4 + 3,4х5 + 3,2х6 + З.іх, > 13,

х, є {0, 1} для / = 1, ..., 7.