С железнодорожных станций А и В нужно развезти грузы на склады 1, 2 и 3. На станции А весь груз можно погрузить на 80 машин, а на станции В – на 100 машин. Склады должны принять: 1 – 50 машин, 2 – 70 машин, 3 – 60 машин. Количество бензина (в литрах), которое расходует одна машина на пробег от станции до склада, дается следующей таблицей.

Станция Склад 1Склад 2Склад 3 А245 В453

Пусть x – число машин, отправленных со станции А на склад 1, а y – со станции А на склад 2. Тогда план перевозок задается следующей таблицей.

Станция Склад 1Склад 2Склад 3 Аxy80-x-y В50-x70-yx+y-20 все числа должны быть неотрицательными (т.к. количество машин не может быть отрицательным числом)

Из таблиц находим общий расход бензина: S (x; y) = 2x + 4y + 5(80 – x – y) + 4(50 – x) + 5(70 – y) + 3(x + y – 20) = 890 – 4x – 3y.

Итак, нам надо минимизировать целевую функцию S(x; y)=890 – 4x – 3y в области ограничений

Решение будем проводить в первой координатной четверти (x,y>0) (0; 70) (10; 70) (50; 30) (0; 20) x y Рис. 17

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

Вычислим значение функции S(x; y) = 890 – 4x – 3y в вершинах многоугольника (0; 70) (10; 70) (50; 30) (0; 20) x y Рис. 17 S (0; 20) = 830, S (0; 70) = 680, S (10; 70) = 640, S (50; 30) = 600, S (50; 0) = 690, S (20; 0) = 810.

Наименьшее из этих значений, равное 600, функция S(x; y)=890–4x–3y принимает при x = 50, y = 30. При этих значениях таблица принимает вид: Станция Склад 1Склад 2Склад 3 А50300 В04060 Ответ: при такой схеме перевозок будет наименьший расход бензина, равный 600 литров.

Примеры задач линейного программирования Цех выпускает трансформаторы двух видов. На один трансформатор первого вида расходуется 3 кг проволоки и 5 кг трансформаторного железа, а на один трансформатор второго вида – 2 кг проволоки и 3 кг железа. От реализации одного трансформатора первого вида цех получает прибыль в 1,2 у. е., а от реализации одного трансформатора второго вида – 1 у. е. Сколько трансформаторов каждого вида должен выпустить цех, чтобы получить наибольшую прибыль, если цех располагает 480 кг железа и 300 кг проволоки?

Задача о пищевом рационе. Для кормления коров на ферме используются сено, силос, концентраты. Чтобы составить дневной рацион, нужно соблюсти следующие условия: 1. Ресурсы позволяют затратить не более: сена - 50 кг, силоса - 25 кг, концентратов - 10 кг; 2. Кормовых единиц должно быть не менее 20; 3. Белка должно быть не менее 2000 г; 4. Кальция должно быть не менее 100 г. Каким образом составить дневной рацион так, чтобы его себестоимость была наименьшей?