Тема 9. Математическое программирование.

1. Уметь построить область допустимых планов, которая задается системой линейных уравнений и неравенств.

2. Уметь построить вектор-градиент целевой функции и линию нулевого уровня.

3. Знать различные формы записи задачи линейного программирования (ЗЛП).

4. Уметь переходить от одной формы ЗЛП к другой.

5. Знать алгоритм симплекс-метода.

6. Знать критерий оптимальности решения ЗЛП на максимум.

7. Уметь для ЗЛП, заданной в симметричной форме, построить двойственную ей задачу.

8. Уметь построить начальный опорный план транспортной задачи (ТЗ) методом северо-западного угла и методом минимального элемента.

9. Знать критерий оптимальности решения ТЗ.

10. Уметь перейти к нехудшему опорному решению ТЗ.

Задачи для самостоятельного выполнения

ЗЛП решить графически:

1. Тема 9. Математическое программирование. - student2.ru

2. Тема 9. Математическое программирование. - student2.ru

3. Тема 9. Математическое программирование. - student2.ru

4. Тема 9. Математическое программирование. - student2.ru

5. Тема 9. Математическое программирование. - student2.ru

ЗЛП решить симплекс-методом:

1. Тема 9. Математическое программирование. - student2.ru (здесь Тема 9. Математическое программирование. - student2.ru - номер студента по списку)

Для приведённых ЗЛП написать двойственную:

1. Тема 9. Математическое программирование. - student2.ru

2. Тема 9. Математическое программирование. - student2.ru

3. Тема 9. Математическое программирование. - student2.ru

4. Тема 9. Математическое программирование. - student2.ru

5. Тема 9. Математическое программирование. - student2.ru

Составить первоначальный план ТЗ методом северо-западного угла и(или) методом минимального элемента по следующим данным:

1 Таблица 9.1

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru

2 Таблица 9.2

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru

3 Таблица 9.3

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru

4 Таблица 9.4

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru

5 Таблица 9.5

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru

Образцы решения ЗЛП:

Задание 1

Решить задачу линейного программирования графическим методом

Тема 9. Математическое программирование. - student2.ru ;

Тема 9. Математическое программирование. - student2.ru

Тема 9. Математическое программирование. - student2.ru

Решение

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

Тема 9. Математическое программирование. - student2.ru

Строим прямые, определяемые уравнениями (I) – (Y) и определяем полуплоскости, удовлетворяющие исходным неравенством. Пересечение этих полуплоскостей образует пятиугольник АВСDE.

Тема 9. Математическое программирование. - student2.ru Рисунок 6 – Область допустимых решений

2. Строим вектор Тема 9. Математическое программирование. - student2.ru

3. Проводим линию нулевого уровня Тема 9. Математическое программирование. - student2.ru , перпендикулярную вектору Тема 9. Математическое программирование. - student2.ru

4. Перемещаем линию нулевого уровня в направлении вектора Тема 9. Математическое программирование. - student2.ru . Первая точка контакта линии уровня с пятиугольником АВСDE является точка Е и, следовательно, Тема 9. Математическое программирование. - student2.ru . Последняя точка контакта – точка С и, следовательно, Тема 9. Математическое программирование. - student2.ru .

5. Найдем координаты точек Е и С.

Е – точка пересечения прямых (IY) и (Y).

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru

Е(2; 2), Тема 9. Математическое программирование. - student2.ru = Е(2; 2) = Тема 9. Математическое программирование. - student2.ru .

С – точка пересечения прямых (III) и (II).

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru

С ( Тема 9. Математическое программирование. - student2.ru ), Тема 9. Математическое программирование. - student2.ru = Z ( Тема 9. Математическое программирование. - student2.ru ) = Тема 9. Математическое программирование. - student2.ru

Ответ: Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru .

Задание 2

Для изготовления 4-х видов продукции используют три вида сырья. Количество сырья вида Тема 9. Математическое программирование. - student2.ru , необходимое для изготовления единицы продукции вида Тема 9. Математическое программирование. - student2.ru , запасы сырья Тема 9. Математическое программирование. - student2.ru и прибыль от реализации единицы продукции вида Тема 9. Математическое программирование. - student2.ru заданы матрицей

Тема 9. Математическое программирование. - student2.ru = Тема 9. Математическое программирование. - student2.ru .

Требуется:

1) составить экономико-математическую модель задачи, пользуясь которой, можно найти план выпуска продукции, при котором общая прибыль Тема 9. Математическое программирование. - student2.ru будет наибольшей;

2) симплексным методом найти оптимальный план выпуска продукции и максимальную величину прибыли;

3) составить задачу, двойственную к исходной, и пояснить ее экономическую суть. Используя теорию двойственности, установить соответствие между переменными прямой и двойственной задач, найти двойственные оценки;

4) с помощью двойственных оценок исследовать:

а) степень полезности отдельных видов ресурсов в условиях производства;

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

Решение

1) Составим экономико-математическую модель задачи. Обозначим через Х1, Х2, Х3, Х4 количество весовых единиц четырех видов продукции, которые планируется изготовить. Тогда прибыль, полученная от реализации выпущенной продукции, будет равна:

Тема 9. Математическое программирование. - student2.ru (9. 1)

Переменные Тема 9. Математическое программирование. - student2.ru должны удовлетворять ограничениям, накладываемым на расход имеющихся в распоряжении предприятия ресурсов сырья, что выражается неравенствами:

Тема 9. Математическое программирование. - student2.ru (9. 2)

По смыслу задачи

Тема 9. Математическое программирование. - student2.ru (9. 3)

Таким образом, условия (9. 1) – (9.3) определяют экономико-математическую модель поставленной задачи.

2) Решим задачу линейного программирования (9.1)–(9.3) симплексным методом. Для этого перейдем к канонической форме записи задачи линейного программирования, введя дополнительные (балансовые) переменные Тема 9. Математическое программирование. - student2.ru , которые означают возможные остатки ресурсов сырья:

Тема 9. Математическое программирование. - student2.ru (9. 1′)

Тема 9. Математическое программирование. - student2.ru (9. 2′)

Тема 9. Математическое программирование. - student2.ru . (9. 3′)

Составим начальную симплексную таблицу по данным математической модели (9. 1′)–(9. 3′).

Таблица 9.6

БП СБ Ао Х1 Х2 Х3 Х4 Х5 Х6 Х7 Θ Тема 9. Математическое программирование. - student2.ru
Х5 Тема 9. Математическое программирование. - student2.ru
Х6 Тема 9. Математическое программирование. - student2.ru
Х7 Тема 9. Математическое программирование. - student2.ru
Zj–Cj –6 –9 –6 –8  

Этой симплексной таблице соответствует опорный план Тема 9. Математическое программирование. - student2.ru , который не является оптимальным, так как в индексной строке Zj–Cj есть отрицательные элементы. Построим новый опорный план, более близкий к оптимальному. Для этого выполним симплексные преобразования таблицы 1. Наибольший по модулю отрицательный элемент индексной строки (–9) указывает на то, что переменную Тема 9. Математическое программирование. - student2.ru надо ввести в число базисных переменных (т.е. столбец, соответствующий переменной Тема 9. Математическое программирование. - student2.ru , берем в качестве разрешающего). Чтобы определить переменную, которую необходимо вывести из числа базисных, составляем симплексные отношения и выбираем наименьшее из них:

Тема 9. Математическое программирование. - student2.ru .

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

Таблица 9.7

БП СБ Ао Х1 Х2 Х3 Х4 Х5 Х6 Х7 Θ
Х5 2,5 –1,5 –0,5 Тема 9. Математическое программирование. - student2.ru
Х6 –0,25 0,25 0,5 –0,75 Тема 9. Математическое программирование. - student2.ru
Х2 0,75 1,25 0,5 0,25 Тема 9. Математическое программирование. - student2.ru
Zj–Cj 0,75 5,25 –3,5 2,25  

Полученный опорный план Тема 9. Математическое программирование. - student2.ru не является оптимальным, так как в индексной строке есть отрицательный элемент (–3,5), который соответствует переменной Х4 (а соответствующий столбец будет разрешающим). Определим разрешающую строку, выбрав из симплексных отношений наименьшее:

Тема 9. Математическое программирование. - student2.ru .

Таким образом, в качестве разрешающей строки необходимо взять строку, соответствующую переменной Х5. Это означает, что базисную переменную Х5 необходимо заменить свободной переменной Х4. Проводя симплексные преобразования, мы придем к таблице 9.8.

Таблица 9.8

БП СБ Ао Х1 Х2 Х3 Х4 Х5 Х6 Х7 Θ
Х4              
Х6              
Х2              
Zj-Cj 2,94 3,94 0,88 1,81  
    Y4 Y5 Y6 Y7 Y1 Y2 Y3  

В полученной симплексной таблице в индексной строке нет отрицательных элементов, поэтому опорный план Тема 9. Математическое программирование. - student2.ru является оптимальным, он является единственным, так как все индексные оценки свободных переменных больше 0.

Вывод. Максимальная возможная прибыль предприятия (в имеющихся условиях) будет 125 денежных единиц, если оно произведёт 5 единиц измерения продукции 2-го вида и 10 единиц измерения продукции 4-го вида, а продукцию 1-го и 3-го видов вообще выпускать не будет. При таком плане производства ресурсы 1-го и 3-го видов будут израсходованы полностью ( Тема 9. Математическое программирование. - student2.ru ), но останется неизрасходованным ресурс 2-го вида в объеме 5 единиц измерения ( Тема 9. Математическое программирование. - student2.ru ).

3) Составим математическую модель двойственной задачи. Запишем матрицу математической модели исходной задачи.

Тема 9. Математическое программирование. - student2.ru .

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

Тема 9. Математическое программирование. - student2.ru .

Обозначив через Тема 9. Математическое программирование. - student2.ru – (прикидочные) цены ресурсов, по матрице Тема 9. Математическое программирование. - student2.ru строим математическую модель двойственной задачи.

Тема 9. Математическое программирование. - student2.ru (9. 4)

Тема 9. Математическое программирование. - student2.ru (9. 5)

Тема 9. Математическое программирование. - student2.ru (9. 6)

Перейдем к канонической форме записи математической модели двойственной задачи введя дополнительные (балансовые) переменные Тема 9. Математическое программирование. - student2.ru , которые означают возможные превышения затрат на производство 1 единицы измерения каждого вида продукции над прибылью, получаемой предприятием.

Тема 9. Математическое программирование. - student2.ru (9. 4′)

Тема 9. Математическое программирование. - student2.ru (9. 5′)

Тема 9. Математическое программирование. - student2.ru (9. 6′)

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

Тема 9. Математическое программирование. - student2.ru .

Для нашей задачи имеем оптимальный план двойственной задачи:

Тема 9. Математическое программирование. - student2.ru .

4) Оценки для 1-го и 3-го видов ресурсов положительные. Это указывает, что эти виды ресурсов наиболее дефицитные (и используются полностью). Увеличение объема ресурса 1-го вида на одну единицу измерения позволило бы получить увеличение максимальной прибыли предприятия на 0,88 денежных единиц; а для ресурса 3-го вида соответственно на 1,81 денежную единицу. Равенство нулю оценки для ресурса 2-го вида ( Тема 9. Математическое программирование. - student2.ru ) говорит о том, что дальнейшее увеличение объема этого вида ресурса не повлияет на прибыль предприятия (ресурс 2-го вида при оптимальном плане производства остается в избытке).

Дополнительные двойственные переменные являются мерой убыточности продукции, которую согласно оптимальному плану нецелесообразно выпускать. Так как Тема 9. Математическое программирование. - student2.ru = 2,94, то это говорит, что на производстве 1 единицы продукции 1-го вида терпит убытки в количестве 2,94 денежные единицы. Следовательно, при необходимости производства продукции 1-го вида для ее рентабельности необходимо повысить цену на эту продукцию не менее чем на 2,94 денежные единицы.

Так как Тема 9. Математическое программирование. - student2.ru =3,94, то это говорит, что на производстве 1-й единицы продукции 3-го вида предприятие терпело убытки в объеме 3,94 денежные единицы (поэтому оно и не планирует эту продукцию производить). При необходимости производство этого вида продукции цена ее реализации должна быть увеличена не менее чем на 3,94 денежные единицы.

Задание 3.

Имеется три поставщика и пять потребителей некоторой продукции. Количество груза Тема 9. Математическое программирование. - student2.ru , которое может отгрузить поставщик Тема 9. Математическое программирование. - student2.ru , стоимость перевозки из пункта Тема 9. Математическое программирование. - student2.ru в пункт Тема 9. Математическое программирование. - student2.ru единицы груза Тема 9. Математическое программирование. - student2.ru и потребности потребителей в грузе Тема 9. Математическое программирование. - student2.ru , Тема 9. Математическое программирование. - student2.ru заданы матрицей:

Тема 9. Математическое программирование. - student2.ru = Тема 9. Математическое программирование. - student2.ru .

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

Решение

Строим математическую модель задачи. Через Хij обозначим объем продукции, доставленной от поставщика Ai (i=l,2,3) потребителю Bj ( Тема 9. Математическое программирование. - student2.ru ). Отметим, что в данном случае сумма количества продукции, которую могут отгрузить все поставщики, совпадает с суммой потребностей потребителей:

310+360+230=140+190+180+170+220 = 900 .

Значит, задача закрытого типа и имеет решение. Математическая модель задачи принимает вид:

Тема 9. Математическое программирование. - student2.ru (9. 7)

Тема 9. Математическое программирование. - student2.ru (9. 8)

Тема 9. Математическое программирование. - student2.ru . (9. 9)

Строим начальную распределительную таблицу 9. 9:

Таблица 9.9

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru В1 В2 Вз В4 В5 аi Ui
А1                   -4
А2 + 3 * – 8          
A3 – 1   + 2                 -6
Тема 9. Математическое программирование. - student2.ru  
Тема 9. Математическое программирование. - student2.ru    

Построенному опорному решению отвечают затраты:

Z1 = 90∙2+220∙1+100∙8+90∙6+170∙10+140∙1+90∙2 = 3760.

Проверим полученный опорный план на оптимальность. Для этого i-й строке и j-му столбцу ставим в соответствие числа Ui и Vj (потенциалы). Для каждой базисной переменной Хij потенциалы должны удовлетворять условию

Ui +Vj = Сij. Получаем систему:

U1+V3 = 2, Так как система состоит из 7 уравнений, а неизвестных

U1+V5 = l, 8, то, чтобы найти численное решение этой системы, U2+V2 = 8, одно из неизвестных зададим произвольно, тогда

U2+V3 = 6, остальные переменные найдутся из системы однозначно.

U2+V4 = 10,

U3+V1 = 1,

U3+V2 = 2.

Пусть U2 = 0, тогда V2 = 8, V3 = 6, V4 = 10, U1 = − 4, U3 = −6, V1 = 7,

V5 = 5.

Теперь для небазисных переменных (свободных клеток) найдем оценки

Sij = Сij –( Ui +Vj) :
S11 = 5 – (– 4 + 7) = 2 S21 = 3 – ( 0 + 7) = −4
S12 = 3 – (– 4 + 8 ) = – 1 S25 = 5 – (0 + 5) = 0
S14 = 4 – (– 4 + 10) = – 2 S33 = 3 – (– 6 + 6) = 3
S35 = 4 – (– 6 + 5) = 5 S34= 5 – (– 6 + 10) = l  

В силу критерия оптимальности опорного плана (все оценки Sij неотрицательны) делаем вывод, что построенный план не оптимален, т.к. среди оценок есть отрицательные. В базис введем переменную Х21 (отвечающую наибольшей по модулю отрицательной оценке) и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки " + " и " – ", начиная с (2,1), которой присваиваем знак " + ". Выбираем наименьшее значение из клеток со знаком

" – " (min (140,100) = 100) и перераспределим продукцию вдоль контура: прибавляя 100 к значениям в клетках со знаком "+" и вычитая из значений в клетках со знаком " – ". В результате приходим к таблице 9.10.

Таблица 9. 10

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru В1 В2 Вз В4 В5 аi Ui
А1     −4
А2 + 3 100     – 10  
A3 – 1     + 5 *         -2
Тема 9. Математическое программирование. - student2.ru  
Тема 9. Математическое программирование. - student2.ru    

Полученному решению отвечают затраты:

Z2 = 90∙2+220∙1+100∙3+90∙6+170∙10+40∙1+190∙2=3360.

Проверяем полученный план на оптимальность и получаем, что S34 = –3 < 0. Значит, решение неоптимальное и строим в таблице 12 новый цикл пересчета для клетки (3,4). Так как min(170,40)=40=Х31 ,то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком " + " и вычитая из значений в клетках со знаком " – ". В результате получаем таблицу 9. 11.

Таблица 9. 11

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru В1 В2 Вз В4 В5 аi Ui
А1 – 2 – + 4 *     –4
А2     + 6   – 10  
A3     –5
Тема 9. Математическое программирование. - student2.ru  
Тема 9. Математическое программирование. - student2.ru    

Полученному решению отвечают затраты:

Z3 = 90∙2+220∙l+140∙3+90∙6+130∙10+190∙2+40∙5=3240.

Аналогично предыдущему проверяем полученный план на оптимальность. Получаем, что S14 = – 2 < 0. Теперь для улучшения плана загрузим клетку (1,4). В итоге приходим к таблице 9.12.

Таблица 9.12

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru В1 В2 Вз В4 В5 аi Ui
А1   + 4 – 1         –6
А2     б – 10   + 5 *    
A3         –5
Тема 9. Математическое программирование. - student2.ru  
Тема 9. Математическое программирование. - student2.ru    

Z4 = 90∙4+220∙l+140∙3+180∙6+40∙10+190∙2+40∙5=3060.

Среди оценок свободных клеток имеем S25 = –2<0, следовательно, полученный план перевозок не является оптимальным, и для его улучшения необходимо загрузить клетку (2,5). В итоге вычислений приходим к таблице 9.13.

Таблица 9.13

Тема 9. Математическое программирование. - student2.ru Тема 9. Математическое программирование. - student2.ru В1 В2 Вз В4 В5 аi Ui
А1         –4
А2     б    
A3     –3
Тема 9. Математическое программирование. - student2.ru  
Тема 9. Математическое программирование. - student2.ru    

Z5 = 130∙4+180∙l+140∙3+180∙6+40∙5+190∙2+40∙5=2980.

Полученный план оказывается оптимальным, так как все оценки незагруженных клеток неотрицательны. По этому плану перевозок 1–й поставщик отправляет 130 ед. продукции потребителю В4 и 180 ед. – B5; 2–й поставщик – 140 ед. потребителю В1, 180 ед. потребителю B3 и 40 ед. потребителю В5; 3–й поставщик – 190 ед. потребителю B2 и 40 ед. потребителю В4.

Вопросы для подготовки к экзамену

Наши рекомендации