Линейное программирование и целевая функция

Ограниченияитранспортнаязадача

Здесь a и b — постоянные числа, заданные условиями задачи.[2] Если по условиям задачи вместо равенств предполагаются неравенства, то для неравенства вида «≤» для преобразования его в равенство надо добавить дополнительную переменную xn+1

xn+1

или несколько таких переменных (xn+2

xn+2

и т.д. по числу неравенств). Аналогично, для неравенств вида «≥» дополнительную неотрицательную переменную xn+i

xn+i

следует вычесть (или, что то же самое, прибавить с коэффициентом –1).

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида. Её можно рассматривать как задачу об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Транспортная задача по теории сложности вычислений входит в класс сложности P. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача, определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, спец.метод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.

Пример транспортной задачи

Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице 34.2

Решение:
1. Вводим переменные задачи (матрицу перевозок):

2. Записываем матрицу стоимостей:

3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.

4. Составим систему ограничений задачи.
Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:

Это означает, что запасы поставщиков вывозятся полностью.

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

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

Необходимо также учитывать, что перевозки не могут быть отрицательными:

Ответ: Таким образом, математическая модель рассматриваемой задачи записывается следующим образом:
Найти переменные задачи, обеспечивающие минимум целевой функции (1) и удовлетворяющие системе ограничений (2) и условиям неотрицательности (3).

 

Линейное программирование и целевая функция

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

· математические модели очень большого числа экономических задач линейны относительно искомых переменных;

· эти типы задач в настоящее время наиболее изучены;

· для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

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

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

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

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

Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

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

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

Имеются какие-то переменные х = (х₁, х₂, … х_n) и функция этих переменных f(x) = f (х₁, х₂, … х_n), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х₁, х₂, … х_n
б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

· максимум или минимум целевой функции (критерий оптимальности);

· систему ограничений в форме линейных уравнений и неравенств;

· требование неотрицательности переменных.

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

	(2.4)
	(2.5)
	(2.6)

Коэффициенты a_i,j, b_i, c_j, j = 1, 2,..., n, i =1, 2,..., m – любые действительные числа (возможно 0).

Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными.

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂,..., х_n являются неотрицательными:

	(2.7)
	(2.8)
	(2.9)

К канонической форме можно преобразовать любую задачу линейного программирования.

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

(2.10)

Вводим переменную

.

Тогда неравенство (2.10) запишется в виде:

(2.11)

В каждое из неравенств вводится своя “ уравнивающая ” переменная, после чего система ограничений становится системой уравнений.

2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных

, l - свободный индекс

3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)

4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.

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

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа «<=» или «>=». Все переменные задачи неотрицательны.

	(2.12)

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

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