КЛАССИЧЕСКИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача об оптимальном составе смеси

Этот обширный класс задач включает в себя так называемые задачи на составление смесей или задачи на использование заменителей.

Задача составления экономичной шихты для выплавления чугуна и стали, а также получения смесей для металлокерамических изделий.

При получении легированной стали необходимо использовать шихту определенного химического состава, многие элементы шихты достаточно дороги, и вместе с тем в ее состав входят малоценные материалы (чугун, лом и т.д.).

Ставится задача выбора шихты минимальной стоимости, в состав которой должны входить в заданных количествах необходимые химические вещества.

Пусть имеется n-видов компонентов шихты, каждый из которых содержит в различных пропорциях m-видов необходимых химических веществ.

Известно, что в еденице компонента j-го вида (j=1…n) содержится единиц

химического вещества i(i=1…m).

Минимальная потребность в i-том веществе составляет единиц.

Себестоимость производства единицы продукции шихты j-го вида равна , а выдаваемый объем ограничен величиной .

Требуется выбрать такой состав, чтобы количество каждого компонента было не меньше требуемого, а суммарная стоимость была минимальна.

Обозначим через (j=1…n) количество единиц вещества j-го вида. Тогда общее количество i-го химического элемента содержащегося в составе данного компонента шихты выразится суммой:

(1)

Эта сумма не должна быть меньше необходимого минимального по всем видам химического вещества:

(i=1…m) (2)

Вместе с тем потребление каждого компонента ограничено имеющимися запасами :

(j=1…n) (3)

Суммарная стоимость шихты:

(4)

Таким образом оптимальным будет такой состав компонентов, который будет обращать в минимум сумму (1) при соблюдении (2) и (3).

Задача о планировании производства

Есть завод, выпускающий n видов продукции, для производства которого используется m видов сырья. На производство j-го вида продукции идет a_i,j единиц i-го сырья. Цена единицы j-ой продукции с_j, запас i-го вида сырья b_i. Составить план производства продукции, который дает максимальный доход от реализации. Если обозначить x_j – план производства, то математическая постановка задачи, для решения поставленной проблемы имеет вид:

Транспортная задача

Транспортная задача возникает при необходимости найти наиболее рациональный путь перевозки некоторого однородного груза.

При этом безразлично, из каких пунктов он поступает, лишь бы был удовлетворен спрос, и каждый поставщик имеет возможность доставить груз любому потребителю, обратные перевозки не предусматриваются.

Пусть в m-пунктах производится и хранится единиц некоторой продукции, потребность в которой в n-пунктах выражается величинами .

Предполагается, что спрос на продукцию не превышает возможности производства:

Известны затраты по перевозке еденицы продукции из i-го пункта отправления в

j-й пункт потребления.

Составить наиболее экономичный план перевозок по суммарным транспортным расходам.

- количество перевозимой продукции. Задача сводится к определению числа значений неизвестных , i=1…m, j=1…n, удовлетворяющих условиям.

Из каждого пункта отправления вывозится не более произведенного в нем количества продукции:

, i=1…m.

В каждый пункт потребления доставляется не менее требуемого им количества продукта:

Перевозимое количество продукта обратно в пункт отправления не возвращается:

Суммарная стоимость перевозок: