Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах (а также в функции f).
Такую задачу называют "основной" или "стандартной" в линейном программировании.
Многие проблемы производства, проектирования, прогнозирования сводятся к широкому классу задач оптимизации, для решения которых применяются математические методы.
Типовыми задачами такого плана являются:
- ассортимент продукции – максимизация выпуска товаров при ограничениях на сырьё для производства этих товаров.
- штатное расписание – составление штатного расписания для достижения наилучших результатов при наименьших расходах
- планирование перевозок -минимизация затрат на транспортировку товаров,
- составление смеси – достижение заданного качества смеси наименьших расходах,
- прочие разнообразные задачи оптимального распределения ресурсов и оптимального проектирования.
Задачу оптимизации можно поставить в следующем виде:
1) целевая функция F(x)→ max, min, const решение должно быть оптимальным. Возможны 3 вида целевой функции – максимизация, минимизация, назначение заданного значения.
2) Ограничения – устанавливают зависимости между переменными
3) Граничные условия – показывают, в каких пределах могут быть значения искомых переменных в оптимальном решении.
Решение задач оптимизации с помощью Excel надстройки «Поиск решения».
В MS Excel существует возможность найти оптимальное решение с помощью надстройки «Поиск решения»
Сервис – Поиск решения, если в меню сервис отсутствует поиск решения, то
Сервис – надстройки и установить флажок в поиске решения
Опции окна «Поиск решения»
Установить целевую ячейку
Указывается ячейка, содержания целевую функцию рассматриваемой задачи
Равной
Следует выбрать из трех (max, min, значению) тот, который определяет min взаимосвязи между решением и целевой ячейках
Изменяя ячейки
Указываются ячейки, которые должны изменяться в процессе поиска решения задачи, т е ячейки которые являются переменными задачи.
Ограничения
Отображаются ограничения, налагаемые на переменные задачи. Допускается ограничения в виде равенств, неравенств, а также требования целочисленности переменных. Ограничения добавляются по одному с помощью кнопки «Добавить»
Кнопка параметры
Позволяет изменять условия и варианты поиска решения исследуемой задачи
*Пример: планирования производства материалов.
Фирма выпускает 2 типа строительных материалов А и В . Продукция обоих видов поступает в продажу. Для производства материалов используются 2 исходных продукта: I и II. максимально возможные суточные запасы этих продуктов составляют 7 и 9 тонн соответственно. Расходы продуктов I и II на 1 тонну соответствующих материалов приведены в таблице:
Исходный продукт
Расход материалов, тонн
Максимально возможный запас
Материал А
Материал В
I
II
Изучение рынка сбыта показало, что суточный спрос на сатериал В никогда не превышает спроса на материал А более чем на 1 тонну. Кроме того спрос на материал А никогда не превышает 3 тонны в сутки. Оптовые цены одной тонны материалов равны 4 000 у.е. для В и 3000 у.е. для А. Какое количество материалов каждого вида должна производить фабрика, чтобы доход от реализации был максимальным.
Решение:
1) Формулировка математической модели задачи
- переменные для решения задачи : Х1 – суточный объем производства материала А, Х2 для материала В
- определение целевой функции. Суммарная суточная прибыль от производства Х1, материала А и Х2 материала В равна:
F=3000Х1+4000Х2
Поэтому цель фабрики – среди всех допустимых значений Х2 и Х1 найти такие, которые максимизируют суммарную прибыль от производства материалов F
F→ max,
- ограничения на переменные:
1) ограничения производства красок не может быть отрицательным, т.е.
Х1>=0, X2>=0
2) расход исходного продукта для производства обоих видов материалов не может превосходить максимально возможного запаса данного исходного продукта, т.е.3Х1+3Х2<=7
2X1+3X2<=9
3)ограничения на величину спроса на материалы
Х2-Х1<=1
X1<=3
Таким образом, получаем модель задачи:
Найти максимум следующей функции:
F=3000Х1+4000Х2→ max
При ограничениях вида:
3Х1+2Х2<=7
2X1+3X2<=9
Х2-Х1<=1
X1<=3
Х1>=0, X2>=0
2)подготовка листа рабочей книги – вводим необходимый текст, данные и формулы
переменныеХ1 и Х2 находятся в ячейках С2 и С3.
Целевая функция находится в ячейке С5 и содержит формулу: = 3000*С2+4000*С3
A
B
C
D
планирование производства материалов
x1
x2
Целевая функция
.=3000*C2+4000*C3
Ограничения
.=3*C2+2*C3
.=2*C2+3*C3
.=C3-C2
.=C2
Сервис-поиск решения.
Установить целевую ячейку: С5
Равной max
Изменяя ячейки: С2:С3
Ограничения:
С7<=D7
С8<=D8
С9<=D9
С10<=D10
Параметрах отметить галочками
Линейная модель
Неотрицательные значения
Ответ:Х1=1
Х2=2
Целевая функция 11000
Пример 2
Фабрика выпускает три вида тканей, причем суточное плановое задание составляет 90 метров тканей первого вида, 70 метров – второго , и 60 метров третьего. Суточные ресурсы следующие: 780 единиц производственного оборудования, 850 единиц сырья, 790 единиц электроэнергии, расход которых на один метр тканей представлены в таблицы:
Ресурсы
Ткани
I
II
III
Оборудование
Сырьё
электроэнергия
Цена за 1 метр ткани вида I равна 80 у.е. II- 70 у.е. III- 60 у.е. определить, сколько метров ткани каждого вида следует выпускать, чтобы общая стоимость выпускаемой продукции была максимальной
Решение:
1) формулировка математической модели задачи:
– переменные для решения задачи: Х1 – суточный объем производства ткани I вида, Х2 – суточный объем производства тканей II вида, Х3 –III вида
- определение функции цели суммарная суточная прибыль от производства Х1, Х2, Х3 тканей :
F=80х1+70х2+60х3
Поэтому цель фабрики – среди всех допустимых значений х1,х2,х3 найти такие которые максимизирует суммарную прибыль от производства тканей
F=80х1+70х2+60х3→ max
- ограничения на переменные
-объем производства тканей не может быть отрицательными, т.е.
Х1>=0, X2>=0,X3>=0
-расход ресурсов для производства тканей не должен превосходить максимально возможного запаса данного ресурса т.е.
2х1+3х2+4х3<=780
1x1+4x2+5x3<=850
3x1+4x2+2x3<=790
Ограничение на плановое задание
X1>=90
X2>=70
X3>=60
2) подготовка листа рабочей книги для вычислений – на рабочии лист вводим необходимый текст, данные и формулы. Переменные задачи х1, х2, х3 находятся в ячейках С3,С4,С5
целевая функция находится в ячейках С7 и содержит формулу = 80*С3+70*С4+60*С5
3) работа с надстроикой поиск решения – ввести необходимые данные и ограничения, в окне параметра отметить линейная модель и максимальное значение.
при 
.