Постановка задачи. Графический метод

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

Пример 1 (транспортная задача)

На две товарные станции привезли по 30 комплектов мебели. Мебель необходимо развести по трем магазинам (по 20 комплектов в каждый). Известна стоимость перевозок с каждой станции в каждый магазин:

Требуется составить оптимальный (с наименьшими затратами) план перевозок.

Математическая постановка задачи:

Пусть х1, х2,..., х6- количество комплектов, которые надо перевезти со станций в магазины. Учитывая ограничения, получим для x_i ³ 0 систему:

Получили систему из четырех уравнений с шестью неизвестными, у которой бесконечно много решений. Среди них надо выбрать такое, на котором целевая функция: f=7х1 + 3х2 + 5х3 + 9х4 + 8х5 + 6х6 достигает минимума.

Пример 2 (расчет рациона)

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

Каждая корова должна получать не меньше 200 единиц жиров, 130 единиц белков и 75 единиц углеводов. Требуется подешевле накормить коров с учетом этих данных.

Математическая постановка задачи:

Пусть надо дать корове 1-ой смеси х1 единиц, 2-ой смеси- х2 единиц. Тогда

Среди решений данной системы надо выбрать такое, на котором достигается минимум целевой функции f=7x1+6x2.

Пример 3 (распределение ресурсов)

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

Требуется получить максимальную прибыль.

Математическая постановка задачи:

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

Среди решений данной системы требуется найти такое, на котором достигается максимум целевой функции f=70x1+50x2.

Сходство математической постановки всех трех задач в том, что имеется целевая функция, у которой надо найти максимум или минимум, имеется система ограничений. При этом как ограничения, так и целевая функция являются линейными. Кроме того, во всех задачах есть требование неотрицательности переменных величин x_i. Поскольку методы математического анализа для поиска экстремумов функций нескольких переменных для линейных функций не работают, то была создана теория линейного программирования, ориентированная на данный класс задач.

Задача линейного программирования в общем виде:

Дана система ограничений: АХ £ В, X ³ 0, где А - матрица, Х и В - столбцы (возможно, разной длины). Дана линейная целевая функция: f = (с, х). Требуется определить компоненты вектора X, удовлетворяющие системе ограничений, при которых данная целевая функция принимает минимальное значение.

Определения. Решение называется допустимым в задаче линейного программирования, если оно удовлетворяет условиям: АХ £ В, Х ³ 0.

Если существует хоть одно допустимое решение, то задача называется допустимой.

Вектор Х, который дает минимум целевой функции среди всех допустимых решений, называется оптимальным решением.

Если существует оптимальное решение, то говорят, что задача поставлена корректно.

Если в примере 2 умножить систему ограничений на -1, то вместо системы ограничений АХ ³ В получим АХ £ В, т.е. получим задачу в общем виде.

В примере 1 вместо АХ £ В имеем АХ = В. Это частный случай.

В примере 3 вместо f = 70х1 + 50х2 -> max ищем f1 = -70х1 - 50х2 -> min.

(но не надо забывать в ответе поменять знак!)

Любую задачу линейного программирования можно свести к КАНОНИЧЕСКОМУ ВИДУ:

АХ = В, Х³ 0, f = (с, х) -> min.

Но при решении задачи нельзя механически заменять знак неравенства на знак равенства, т.к. после этого система, скорее всего, не будет иметь решения.

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

Например, задачу 3 можно так свести к канонической форме:

f = 70х1 + 50х2 -> max f1 = -70х1 - 50х2 -> min

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

и f = 7х1 + 6х2 -> min

Решим эти задачи двумя способами: пример 1- аналитически, пример 3- графически.

В задаче 1 имеем 4 уравнения и 6 неизвестных, т.е. 2 степени свободы. Чтобы описать пространство решений, надо выбрать 2 независимые (свободные) переменные и через них выразить остальные переменные. Например, в качестве СВОБОДНЫХ возьмем х1 и х4. Неизвестные х2, х3, х5, х6 называются БАЗИСНЫМИ. Выразим их через свободные переменные и подставим все в целевую функцию:

х2= 20 -х1; х3= 20 – х4; х5= 10 - х1 + х4; х6= 10 + х1 – х4;

f = 7х1 + 3(20 - х1) + 5(20-х4) + 9х4 + 8(10 - х1 +х4) + 6(10+ х1 – х4) = 300 + 2х1 + 6х4.

Таким образом, мы нашли общее решение системы уравнений. При этом х1 и х4- свободные переменные, они могут принимать любые неотрицательные значения. Среди всех решений надо выбрать оптимальное. Т.к. f =300 + 2х1 + 6х3, и должно быть х_i ³ 0, то ясно, что в оптимальном решении х1=0, х4=0. Тогда х2 = 20, х3 =20, х5 = 10, х6 = 10, f=300.