Задан отсчет индексов, начиная с 1

m:=3

Указано число предприятий-производителей (заводов)

n:=4

Определено число предприятий-потребителей (магазинов)

j:=1..n i:=1..m

Организованы циклы

t_j:= 1 s_i:= 1

 

Введена матрица стоимости перевозок

Введен вектор запасов

 

Введен вектор спроса

 

Введена целевая функция

x_m,n:=0

Given

В двух последних выражениях следует обратить внимание на форму знаков равенства (жирный знак равенства)

x ≥ 0

x:=Minimize(Z,x)

 

 

Получена матрица оптимальных перевозок

Z(x) =1330

Определена стоимость оптимальных перевозок

 

 

Методические указания к заданию 7

Рассмотрим порядок решения задачи ЛПР с помощью математической системы MATLAB 6.5

Пусть требуется максимизировать ЦФ:

Z=1,1х₁+1,2х₂

при имеющихся ограничениях:

2х₁+х₂≤ 8

0,75х₁+ х₂≤ 6

х₁≥ 0, х₂≥ 0

Так как MATLAB ищет минимум функции, то перед коэффициентами максимизируемой ЦФ необходимо сменить знаки на противоположные.

 

Решение.

Z=[-1.1;-1.2];

A=[2 1;0.75 1];

b=[8;6];

[x,Zval]=linprog(Z,A,b)

Optimization terminated successfully.

x =

1.6000

4.8000

Zval =

-7.5200

 

Таким образом, оптимальные значения х₁= 1.6, х₂=4.8. Максимальное значение целевой функции f = 7,52. При записи ответа знак целевой функции изменен на противоположный.

В данной программе символом Z обозначена ЦФ, символом А – матрица условий, символом b – вектор ограничений. Поиск оптимального плана осуществляется с помощью функции linprog.

Приложение

 

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

В общем виде задачу МП можно сформулировать следующим образом: требуется максимизировать (или минимизировать) целевую функцию (ЦФ)

Z = f(x₁, x₂,…,x_n) (1)

при наличии ограничений на допустимые значения переменных (аргументов) x₁, x₂,…,x_n:

g_i(x₁, x₂,…,x_n) ≤ b_i , (2)

где b_i – некоторые действительные числа (ресурсы, лимиты); выражение в скобках означает, что индекс i изменяется от 1 до m. Величина m показывает, сколько ограничений имеется в данной задаче. Величина n определяет число переменных в задаче (например, число видов выпускаемой продукции).

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

Результат решения задачи МП должен оцениваться количественной мерой – критерием оптимальности. Критерием оптимальности называется количественная оценка качества решения задачи МП (качества планирования производства).

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

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

Процедуру перехода от минимизации к максимизации иллюстрирует следующий рисунок.

 

 

Рис. П1. Переход от максимизации к минимизации

 

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

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

Так, если целевая функция и функции имеющихся ограничений линейны, то такая задача является задачей линейного программирования (ЛПР).

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

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

В задачах параметрического программирования целевая функция или функции ограничений зависят от параметров.

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

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

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

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

Термин «линейное программирование» сходен по звучанию с термином «программирование», то есть составление программ (кодирование) для ЭВМ. Однако это разные понятия.

Термин линейное программирование возник в результате неточного перевода английского термина «linear programming». Правильным переводом термина «linear programming» должно быть не «линейное программирование», а «линейное планирование». Под термином «линейное программирование» следует понимать науку, которая занимается разработкой оптимальных планов организации производства. При этом все используемые в линейном программировании функции должны быть линейными.

Заметим, что первые постановки задач линейного программирования были сделаны известным советским математиком Л.В.Канторовичем.

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

Рассмотрим порядок построения области допустимых решений

При графическом представлении двухмерной задачи ЛПР область допустимых решений называют многоугольником допустимых решений (или иногда – полигоном). Если задача трехмерная (используется три аргумента x₁, x₂, x₃), то область допустимых решений выглядит в виде объемной трехмерной фигуры, ограниченной с разных сторон плоскостями (см. рис. П2).

 

Рис. П2. Трехмерный график

 

С увеличением размерности задачи ЛПР свыше трех переменных (например, три вида выпускаемой продукции) представить графически область допустимых решений нельзя. При n ≥ 3 будем называть многомерную область допустимых решений гиперполигоном или симплексом.

На рис. П3 показан типичный случай графического решения двумерной задачи ЛПР (он многократно описан в различных литературных источниках).

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

В показанном на рис. П3 случае число ограничений (сторон многоугольника) равно шести (m = 6). Стороны изображенного многоугольника описываются прямыми, уравнения которых берутся из ограничений (2). При построении многоугольника допустимых решений знаки неравенств в ограничениях (2) заменяются знаками равенств. Таким образом, точки внутри многоугольника допустимых решений удовлетворяют сразу всем неравенствам (2).

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

Предположим, что необходимо максимизировать ЦФ вида:

Z = d₁x₁ + d₂x₂

при имеющихся ограничениях:

a₁₁x₁ + a₁₂x₂ ≤ b₁,

a₂₁x₁ + a₂₂x₂ ≤ b_2,

_{… ……}

a_m1x₁ + a_m2x₂ ≤ b_m ,

x₁ ≥ 0, x₂ ≥ 0.

 

 

Для построения многоугольника допустимых решений вначале необходимо построить прямую линию

a₁₁x₁ + a₁₂x₂ = b₁.

Как известно, для построения прямой линии достаточно иметь две точки. Для уменьшения объема вычислений точки целесообразно расположить на осях системы координат.

Взяв x₁ = 0, получим x₂ =b₁/ a₁₂ . Определим координаты второй точки. При x₂ = 0, получим x₁ =b₁/ a₁₁ .

График прямой линии с указанными точками показан на рис. П4.

Построенная прямая линия AB разделяет систему координат на две полуплоскости (I и II). В одной полуплоскости выполняется соотношение:

a₁₁x₁ + a₁₂x₂ ≤ b₁, (3)

а в другой полуплоскости выполняется соотношение:

a₁₁x₁ + a₁₂x₂ ≥ b₁.

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

Рассмотрим конкретный пример.

Предположим, имеется неравенство:

4x₁ + 2x₂ ≤ 8. (4)

Определим координаты двух точек, лежащих на прямой 4x₁ + 2x₂ = 8:

(0;4) и (2;0).

Расположение рассматриваемой прямой линии в декартовой системе координат показано на рис. П5.

Подставляя в неравенство (4) x₁ =0 и x₂ =0, получаем: 0 < 8, то есть начало координат принадлежит полуплоскости II, выделенной на рис. П3 стрелкой. Это означает, что левая нижняя полуплоскость содержит область допустимых решений.

Аналогично строятся остальные графики, которые соответствуют неравенствам (2), указанным в ограничениях. Для каждой прямой стрелкой выделяют полуплоскость, которая содержит область допустимых решений. В результате получается многоугольник допустимых решений, примерный вид которого показан на рис. П3. Многоугольник представляет собой общую часть всех полуплоскостей, которые определяются с помощью ограничений (2).

После построения многоугольника допустимых решений нужно на нём найти, где ЦФ принимает максимальное значение. Это можно сделать разными способами. Например, можно вычислить ЦФ в каждой вершине построенного полигона, а затем путём сопоставления значений ЦФ выделить вершину, в которой она максимальна. Графическое решение в ряде случаев позволяет сократить время нахождения правильного ответа, наглядно представить имеющиеся ограничения и целевую функцию.

Рассмотрим порядок построения графика ЦФ

При графическом решении задачи ЛПР на график с изображением многоугольника допустимых решений наносят прямую линию, которая описывает ЦФ в соответствии с выражением (1). Первоначально прямую линию графика ЦФ проводят таким образом, чтобы она пересекала многоугольник допустимых решений (см. рис. П6).

 

 

Затем эту прямую перемещают в сторону увеличения ЦФ до тех пор, пока прямая линия имеет хотя бы одну общую точку с полигоном.

Для целевой функции вида Z = d₁x₁ + d₂x₂ прямую линию следует перемещать параллельно самой себе в направлении вектора D (d₁;d₂). Заметим, что при минимизации ЦФ прямую линию смещают в направлении вектора (- d₁,-d₂).

Рассмотрим подробнее порядок построения графика целевой функции вида Z = d₁x₁ + d₂x₂.

Вначале необходимо построить вектор D (d₁; d₂) (см. рис. П7).

Затем нужно построить линию Z1, перпендикулярную вектору D (при этом масштаб по осям должен быть одинаковым). Смещение линии Z1 в направлении вектора D приведет к увеличению значения целевой функции (см. рис. П8).

 

 

При построении вектора-градиента D (d₁; d₂) следует помнить о том, что он имеет экономический смысл. Этот вектор характеризует соотношение цен двух видов продукции. Так при увеличении стоимости второго вида продукции по сравнению со стоимостью первого вида продукции вектор будет приближаться к оси х₂. Сказанное иллюстрирует рис. П9.

 

 

Перечислим операции, которые необходимо выполнить для графического решения задачи ЛПР.

1. Построить прямые линии на основании ограничений (2), в которых знаки неравенств заменить знаками равенств.

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

3. На основании уравнения, которое описывает ЦФ (1), построить вектор-градиент D (d₁; d₂), определяющий направление возрастания целевой функции.

4. Выбрав некоторое постоянное значение h, построить график ЦФ d₁x₁ + d₂x₂ = h, который должен пересекать многоугольник допустимых решений. График ЦФ будет обязательно перпендикулярен вектору D (d₁; d₂). Такой график иногда называют линией уровня.

5. Увеличивать значение h до тех пор, пока график ЦФ имеет хотя бы одну общую точку с полигоном допустимых решений. При увеличении h график ЦФ смещается параллельно самому себе в направлении возрастания вектора D (d₁; d₂).

6. Определить точку (или отрезок), где целевая функция принимает максимальное значение. В этой точке (или на этом отрезке) переменные x_i имеют оптимальные значения.

 

Следует обратить внимание на тот факт, что многоугольник допустимых решений всегда располагается в первой четверти (в первом квадранте). Это объясняется наличием ограничений x₁ ≥ 0, x₂ ≥ 0. С экономической точки зрения это означает, что количество производимой продукции не может характеризоваться отрицательным числом. Другими словами: производимую продукцию не уничтожают. Её либо производят (x_i > 0), либо не производят (x_i = 0).

Представляет определенный интерес случай, когда график целевой функции параллелен графику одного из ограничений.

В этом случае число точек, в которых целевая функция максимальна, бесконечно. Оптимальными являются все точки на отрезке АВ (см. рис. П10).

Мысль о том, что все точки отрезка АВ являются оптимальными и равноправными, отмечается во многих литературных источниках [1, стр.12], [3, стр.20], [6, стр. 157]. Это действительно так. Во всех точках отрезка АВ целевая функция максимальна и постоянна.

Однако расход ресурсов в точках отрезка АВ различен. Естественно, что выгоднее при производстве продукции тратить меньший объем ресурсов (при одном и том же значении дохода, то есть при одном и том же значении ЦФ). Поэтому существующие методики решения задач ЛПР необходимо дополнить следующими операциями.

1. Рассчитать объем использованных ресурсов в точках А и В. Следует иметь ввиду, что оптимальная точка обязательно будет находиться в вершине многоугольника (оптимальная точка не может находиться в других точках, кроме вершин).
2. Выделить точку, в которой экономия ресурсов наибольшая.
3. В некоторых случаях для выделения одной из двух точек необходимо учесть стоимости каждого ресурса.

 

Найденная точка будет являться оптимальным планом производства (в этой точке достигается максимальное значение ЦФ и максимальная экономия ресурсов).

Порядок разработки математической модели при решении задачи ЛПР рассмотрим на конкретном примере.

 

 

Пример

Фирма производит две модели мобильных телефонов. Условно эти модели назовем следующим образом: А – F111 и В – W222. Их производство ограничено наличием комплектующих деталей: дисплеев и аккумуляторов. Для каждого телефона модели А требуется один дисплей, а для каждого телефона модели В – два дисплея. Фирма может израсходовать не более 1400 дисплеев в рабочую смену (имеются ограничения на поставку дисплеев). В каждый телефон модели А необходимо установить две аккумуляторные батареи, а в каждый телефон модели В – одну батарею. В смену можно использовать не более 1600 аккумуляторных батарей. Стоимость мобильного телефона типа А составляет 6 тысячи рублей, а стоимость телефона модели В – 5 тысяч рублей.

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

 

Решение

Чтобы получить математическую модель, обозначим через х₁ количество выпущенных за смену телефонов модели А, а через х₂ – количество выпущенных телефонов модели В. Задача состоит в том, чтобы найти оптимальные значения х₁ и х₂.

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

 

Z = 6х₁ + 5х₂.

 

Поскольку х₁ и х₂ выражают ежедневный объём (количество) выпускаемых изделий, то эти величины не могут быть отрицательными, т. е. х₁ ≥ 0, х₂ ≥ 0. Остальные ограничения можно записать так:

1·x1 + 2·x2 ≤ 1400 – ограничение на наличие дисплеев,

2·x1 + 1·x2 ≤ 1600 – ограничение на наличие аккумуляторных батарей.

Задача состоит в том, чтобы найти значения x₁ и x₂, которые удовлетворяют ограничениям и максимизируют целевую функцию.

Вначале решим задачу графически.

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

Для первой прямой x₁ + 2·x₂ = 1400 найдем две точки, которые расположены на осях системы координат.

Точка а: x₁= 0, x₂= 700.

Точка b: x₂= 0, x₁= 1400.

Аналогично построим вторую прямую линию 2x₁ + x₂ = 1600.

Точка с: x₁= 0, x₂= 1600.

Точка d: x₂= 0, x₁= 800.

Учитывая знаки неравенств в ограничениях, найдем область допустимых решений: 0aed.

 

 

Построим вектор-градиент для ЦФ. Для удобства построений вектора D умножим коэффициенты в уравнении Z = 6х1 + 5х2 на константу 200. В результате получим точку с координатами (1200; 1000). Построив вектор-градиент, найдем оптимальное положение графика целевой функции. Из графика видно, что линия FG перпендикулярна вектору-градиенту и имеет одну точку соприкосновения с областью допустимых решений. Оптимальный план производства отмечен точкой e (600;400).

Проверим, хватит ли отпущенных лимитов для реализации составленного плана производства.

Так как х₁ = 600, а х₂ = 400, то при подстановке в первое ограничение получим:

600 + 2·400 = 1400 (то есть ограничение выполняется).

При подстановке во второе ограничение получим:

2·600 + 400 =1600 (второе ограничение также выполняется).

Значение ЦФ в точке оптимума составит:

Z = 6 ·600 + 5·400 = 5600 тыс. рублей.

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

 

Список литературы

 

1. Банди Б. Основы линейного программирования: Пер. с англ.- М.: Радио и связь, 1989. – 176 с.

2. Кораблин М.А. Информатика поиска управленческих решений.- М.: СОЛОН-Пресс, 2003. - 192 с.

3. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие.- М.: Высш. шк., 1993. – 336 с.

4. Математический энциклопедический словарь./Гл. ред. Ю.В.Прохоров.- М.: Сов. энциклопедия, 1988.- 847 с.

5. Справочник по математике для экономистов/Под ред. В.И.Ермакова.- М.: Высш. шк.,1997.- 384 с.

6. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. Кн. 1. – М.: Мир, 1986. – 352 с.

7. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.: Высш. шк., 2002. – 544 с.