Линейное программирование
Министерство
образования и науки Российской Федерации
Государственное
образовательное учреждение
высшего
профессионального образования
«ОРЕНБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет
экономики и управления
Кафедра
математических методов и моделей в экономике
ОТЧЕТ
по
расчетно-графической работе
по курсу
«Математические методы и модели исследования операций»
Задачи
линейного программирования
Руководитель
___________ Яркова О.Н.
«___»____________2011 г.
Исполнитель
студентка гр. 10ММЭ
_______Абдрахимова Е.Г.
Оренбург 2011
МИНИСТЕРСТВО
ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ
АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное
образовательное учреждение
высшего
профессионального образования
"Оренбургский
государственный университет"
Кафедра математических
методов и моделей в экономике
Задание на
РГЗ
по дисциплине
«Математические методы и модели исследования операций»
на тему
«Линейное программирование»
Задание 1.
Поставлена задача линейного программирования:
.
1. Решить задачу ЛП геометрически.
2. Решить эту задачу с помощью симплекс-метода.
Задание 2.
На
фабрике с помощью 5 видов красителей (
)
создается 4 разновидности рисунков для тканей (
). При
известной отпускной стоимости 1м ткани каждого рисунка (руб.), известном
расходе каждого красителя на окраску 
ткани
(г) и известном запасе красителя (кг):
1. Определить план выпуска ткани каждого рисунка, обеспечивающий
максимальный доход от реализации тканей;
2. Составить двойственную задачу и найти ее решение;
. Определить теневые цены на каждый краситель; указать дефицитные
и недефицитные красители;
. Указать, на сколько недоиспользуются недефицитные красители;
. Показать доход и план выпуска тканей при увеличении запасов
дефицитных красителей на I ед.;
. Показать допустимые пределы изменения запасов красителей;
. Показать допустимые пределы изменения отпускной стоимости на
ткань каждого рисунка;
8. Оценить
целесообразность введения в план производства выпуск ткани с разновидностью
рисунка (
), если нормы затрат красителей на 1 ед. ткани
соответственно равны 6,2,1,4,4 г и доход, ожидаемый от реализации новой ткани,
равен 5000 руб.;
. Показать,
допустимо ли увеличение всех дефицитных красителей одновременно на 1 кг
каждого.
Задание 3.
Для транспортной задачи составить математическую модель. Методом
потенциалов найти оптимальные планы. Опорный план найти методом
северо-западного угла.
Задача 1. (Транспортная задача закрытого типа)
Три
предприятия: 
данного экономического района могут производить
некоторую однородную продукцию в количествах, указанных в столбце
«производство». Эта продукция должна быть поставлена четырем потребителям: 
в количествах, указанных в строке «потребности».
Затраты, связанные с производством и доставкой единицы продукции, заданы на
пересечении соответствующих поставщиков и потребителей в столбцах той же
таблицы. Составить такой план прикрепления потребителей к поставщикам, при
котором общие затраты являются минимальными.
Задача
2. (Транспортная задача открытого типа).
На
четырех хлебокомбинатах (поставщик): 
ежедневно
производится мука в количествах, указанных в столбце «производство». Эта мука
потребляется тремя хлебзаводами (потребитель): 
в
количествах, указанных в строке «потребности» - потребности, этой же таблицы.
Тарифы перевозок 1т. муки с хлебокомбинатов к каждому из хлебозаводов заданы на
пересечении соответствующих поставщиков и потребителей в столбцах этой же
таблицы. Составьте такой план доставки муки, при котором стоимость перевозок
является минимальной.
Задание
4.
Задача
о назначениях. Имеется 8 объектов, на которые назначаются 8 ресурсов. Стоимость
назначения ресурсов на места представлена в виде матрицы. Требуется найти такое
назначение ресурсов по местам, чтобы суммарная стоимость всех назначений была
минимальной.
Задание
5.
Задача
о коммивояжере. Дано 5 пунктов, которые должен посетить коммивояжер. Стоимости
переезда из одного города в другой заданы симметричной матрицей стоимости.
Требуется найти маршрут объезда всех городов, имеющий минимальную стоимость. В
маршруте каждый город должен содержаться только 1 раз.
Задание
6.
Разработать
программное обеспечение, реализующее решение задачи программирования с помощью
симплекс метода.
Содержание
1. Решение
задачи ЛП
.1
Гeометрическая интерпретация двумерной задачи ЛП и ее решение
.2 Решение
задачи ЛП симплекс-методом
.
Двойственная задача
.
Транспортная задача
.1
Транспортная задача (открытого типа)
.2
Транспортная задача (закрытого типа)
. Задача о
назначениях.
. Задача о
коммивояжере
6.Симплекс
метод
Введение
В настоящее время линейное программирование является одним из наиболее
употребительных аппаратов математической теории оптимального принятия решений,
в том числе и в финансовой математике. Для решения задач линейного
программирования разработано сложное программное обеспечение, дающее
возможность эффективно и надежно решать практические задачи больших объемов.
Эти программы и системы снабжены развитыми системами подготовки исходных
данных, средствами их анализа и представления полученных результатов. Владение
аппаратом линейного программирования необходимо каждому специалисту в области
прикладной математики.
Линейное программирование представляет собой наиболее часто используемый
метод оптимизации. К числу задач линейного программирования можно отнести
задачи:
· рационального использования сырья и материалов;
· задачи оптимального раскроя;
· оптимизации производственной программы предприятий;
· оптимального размещения и концентрации производства;
· составления оптимального плана перевозок, работы транспорта;
· управления производственными запасами;
· и многие другие, принадлежащие сфере оптимального
планирования.
Наиболее разработанным и широко применяемым разделом математического
программирования является линейное программирование, целью которого служит
отыскивание оптимума (max, min) заданной линейной функции при
наличии ограничений в виде линейных уравнений или неравенств в этом и заключается
актуальность данной работы.
Целью данного РГЗ является выполнение расчетно-графической работы,
закрепление знаний и навыков, необходимых для математического моделирования
социально-экономических процессов. А также, приобретение навыков работы с
программными пакетами «Линейное программирование» и «Дискретное
программирование».
Теоретическая часть
Табличный симплекс-метод
Для упрощения процесса решения исходные данные задачи линейного
программирования при решении ее симплекс методом записываются в специальные
симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название
табличный симплекс метод. Задача линейного программирования в каноническом
виде:
F=a01x1+a02x2+...a0nxn +b0 → max
Исходная
таблица для задачи имеет следующий вид:
|
x1
|
x2
|
...
|
xn-1
|
xn
|
b
|
|
F
|
- a0,1
|
-a0,2
|
...
|
-a0,n-1
|
- a0,n
|
-b0
|
|
xn+1
|
a1,1
|
a1,2
|
...
|
a1,n-1
|
a1,n
|
b1
|
|
xn+2
|
a2,1
|
a2,2
|
...
|
a2,n-1
|
a2,n
|
b2
|
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
|
xn+m
|
am,1
|
am,2
|
...
|
am,n-1
|
am,n
|
bm
|
, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные
переменные. Все дополнительные переменные мы приняли как базисные, а исходные
переменные как небазисные (дополнительные записаны в первый столбец
симплекс-таблицы а исходные в первую строку). При каждой итерации элементы
симплекс-таблицы пересчитывают по определенным правилам.
Алгоритм симплекс-метода.
Подготовительный этап
Приводим задачу ЛП к каноническому виду
F=a01x1+a02x2+...a0nxn +b0 → max
В
случае если в исходной задаче необходимо найти минимум - знаки коэффициентов
целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов
ограничивающих условий со знаком "≥" так же меняются на
противоположные. В случае если условие содержит знак "≤" -
коэффициенты запишутся без изменений.
Шаг
0. Составляем симплексную таблицу, соответствующую исходной задаче :
|
x1
|
x2
|
...
|
xn-1
|
xn
|
b
|
|
F
|
- a0,1
|
-a0,2
|
...
|
-a0,n-1
|
- a0,n
|
-b0
|
|
xn+1
|
a1,1
|
a1,2
|
...
|
a1,n-1
|
a1,n
|
b1
|
|
xn+2
|
a2,1
|
a2,2
|
...
|
a2,n-1
|
a2,n
|
b2
|
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
|
xn+m
|
am,1
|
am,2
|
...
|
am,n-1
|
am,n
|
bm
|
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены):
1. Если среди них нет отрицательных то найдено допустимое решение
(решение соответствующее одной из вершин многогранника условий) и мы переходим
к шагу 2.
2. Если в столбце свободных членов имеются отрицательные элементы то
выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой
строке так же находим максимальный по модулю отрицательный элемент ak,l - он
задает ведущий столбец - l и является ведущим элементом. Переменная,
соответствующая ведущей строке исключается из базиса, переменная
соответствующая ведущему столбцу включается в базис. Затем снова пересчитываем
симплекс-таблицу согласно правилам.
. Если же среди свободных членов есть отрицательные элементы - а в
соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
. Если после перерасчета в столбце свободных членов остались
отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко
второму.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на
оптимальность:
1. Если среди элементов симплексной таблицы, находщихся в строке F (не
беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных,
то найдено оптимальное решение.
2. Если в строке F есть отрицательные элементы то решение требует
улучшения. Выбираем среди отрицательных элементов строки F максимальный по
модулю (исключая значение функции b0) a0,l=min{a0,i }. Первый столбец в котором
он находится будет ведущим. Для того, что бы найти ведущую строку, находим
отношение соответствующего свободного члена и элемента из ведущего столбца, при
условии, что они неотрицательны.
/ak,l =min {bi/ai,l } при ai,l>0, bi>0
- cтрока, для которой это отношение минимально - ведущая. Элемент ak,l -
ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk)
исключается из базиса, переменная соответствующая ведущему столбцу (xl)
включается в базис.
Пересчитываем
симплекс-таблицу по формулам
<#"560138.files/image011.gif">
Преобразуемый элемент ai,j и соответствующие ему три сомножителя как раз
и являются вершинами ”прямоугольника”.
1. Решение задачи ЛП
1.1 Гeометрическая интерпретация двумерной
задачи ЛП и ее решение
Рассмотрим двумерную задачу:
(1)
Необходимо найти максимальное значение целевой функции F = x1+x2 →
max, при системе ограничений (1).Построим область допустимых решений, т.е.
решим графически систему неравенств. Для этого построим каждую прямую и
определим полуплоскости, заданные неравенствами (полуплоскости обозначены
штрихом) (Рисунок 1).
Рисунок 1-Границы области допустимых решений.
Пересечением полуплоскостей будет являться область, координаты точек
которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений (Рисунок 2).
Рисунок 2- границы области решений.
Рассмотрим целевую функцию задачи F = x1+x2 → max.
Построим прямую, отвечающую значению функции F = 0: F = x1+x2 = 0. Будем
двигать эту прямую параллельным образом. Поскольку нас интересует максимальное
решение, поэтому двигаем прямую до последнего касания обозначенной области. На
графике эта прямая обозначена пунктирной линией (Рисунок 3).
Рисунок 3- поиск максимального решения.
Область допустимых решений представляет собой многоугольник.
Прямая F(x) = const пересекает область в точке D. Так как точка D
получена в результате пересечения прямых (1) и (2), то ее координаты
удовлетворяют уравнениям этих прямых:
Решив
систему уравнений, получим: x1 = 1.0769, x2 = 3.4615.
Откуда
найдем максимальное значение целевой функции:(X) = 1*1.0769 + 1*3.4615 = 4.54.
.2 Решение задачи ЛП симплекс-методом
Решим прямую задачу линейного программирования симплексным методом, с
использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = x1 + x2 при
следующих условиях-ограничений:
(2)
Для
построения первого опорного плана систему неравенств приведем к системе
уравнений путем введения дополнительных переменных (переход к канонической
форме):
Матрица
коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим
систему уравнений относительно базисных переменных:, x4,
Полагая,
что свободные переменные равны 0, получим первый опорный план:= (0,0,8,3)
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
|
x3
|
8
|
1
|
2
|
1
|
0
|
|
x4
|
3
|
6
|
-1
|
0
|
1
|
|
F(X0)
|
0
|
-1
|
-1
|
0
|
0
|
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся
отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так
как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца
и ведущей строки.
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
min
|
|
x3
|
8
|
1
|
2
|
1
|
0
|
4
|
|
x4
|
3
|
6
|
-1
|
0
|
1
|
-
|
|
F(X1)
|
0
|
-1
|
-1
|
0
|
0
|
0
|
Получаем новую симплекс-таблицу:
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
|
x2
|
4
|
1/2
|
1
|
1/2
|
0
|
|
x4
|
7
|
61/2
|
0
|
1/2
|
1
|
|
F(Х1)
|
4
|
-1/2
|
0
|
1/2
|
0
|
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся
отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так
как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее, следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (61/2) и находится на пересечении ведущего
столбца и ведущей строки.
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
min
|
|
x2
|
4
|
1/2
|
1
|
1/2
|
0
|
8
|
|
x4
|
7
|
61/2
|
0
|
1/2
|
1
|
11/13
|
|
F(X2)
|
4
|
-1/2
|
0
|
1/2
|
0
|
0
|
Получаем новую симплекс-таблицу:
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
|
x2
|
36/13
|
0
|
1
|
6/13
|
-1/13
|
|
x1
|
11/13
|
1
|
0
|
1/13
|
|
F(X2)
|
47/13
|
0
|
0
|
7/13
|
1/13
|
Конец итераций: индексная строка не содержит отрицательных элементов -
найден оптимальный план
Окончательный вариант симплекс-таблицы:
|
БазисBx1x2x3x4
|
|
|
|
|
|
|
x2
|
36/13
|
0
|
1
|
6/13
|
-1/13
|
|
x1
|
11/13
|
1
|
0
|
1/13
|
2/13
|
|
F(X3)
|
47/13
|
0
|
0
|
7/13
|
1/13
|
Оптимальный план можно записать так:= 36/13= 11/13(X) = 1•36/13 + 1•11/13
= 47/13.
Используя программу «Симплекс-метод», получим аналогичный результат
(Рисунок 4).
Рисунок 4 - результат вычисления полученный путём проверки в программе
«SIMPLEX».
2.
Двойственная задача
Исходные данные (Рисунок 5):
|
Номер Варианта
|
Вид Красителей
|
Разновидность рисунка.
Расход красителей на окраску 1 м ткани (грамм)
|
Запасы красителей (грамм)
|
|
|
Р1
|
Р2
|
Р3
|
Р4
|
|
|
1
|
А1
|
3
|
1
|
2
|
10
|
25 000
|
|
А2
|
4
|
3
|
8
|
6
|
120 000
|
|
А3
|
2
|
3
|
7
|
9
|
155 000
|
|
А4
|
8
|
5
|
12
|
11
|
250 000
|
|
А5
|
2
|
3
|
4
|
1
|
100 000
|
|
Стоимость одного метра
ткани (руб.)
|
49
|
33
|
76
|
109
|
|
Рисунок 5 - таблица исходных данных.
. Для определение плана выпуска ткани каждого вида рисунка,
обеспечивающего максимальный доход от реализации тканей необхадимо составить
экономико-математическую модель задачи. Для этого введём обозначения следующего
вида:
- план
выпуска ткани рисунка вида 
;
- план
выпуска ткани рисунка вида 
;
- план
выпуска ткани рисунка вида 
;
- план
выпуска ткани рисунка вида 
;
Для
начала решим прямую задачу линейного программирования симплексным методом, с
использованием симплексной таблицы и определим максимальное значение целевой
функции:
(X)
= 49x1 + 33x2 + 76x3 + 109x4
при
следующих условиях-ограничений:
Для
построения первого опорного плана систему неравенств приведем к системе
уравнений путем введения дополнительных переменных (переход к канонической
форме):
x1
+ 1x2 + 2x3 + 10x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 25000
x1
+ 3x2 + 8x3 + 6x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 = 120000
x1
+ 3x2 + 7x3 + 9x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 155000
x1
+ 5x2 + 12x3 + 11x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 250000
x1
+ 3x2 + 4x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 = 100000
Матрица
коэффициентов A = a(ij) этой системы уравнений имеет вид:
|
3
|
1
|
2
|
10
|
1
|
0
|
0
|
0
|
0
|
|
4
|
3
|
8
|
6
|
0
|
1
|
0
|
0
|
0
|
|
2
|
3
|
7
|
9
|
0
|
0
|
1
|
0
|
0
|
|
8
|
5
|
12
|
11
|
0
|
0
|
0
|
1
|
0
|
|
2
|
3
|
4
|
1
|
0
|
0
|
0
|
0
|
1
|
Решим систему уравнений относительно базисных переменных: (x5, x6, x7,
x8, x9), полагая, что свободные переменные равны 0, получим первый опорный
план: X1 = (0,0,0,0,25000,120000,155000,250000,100000)
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
x9
|
|
x5
|
25000
|
3
|
1
|
2
|
10
|
1
|
0
|
0
|
0
|
0
|
|
x6
|
120000
|
4
|
3
|
8
|
6
|
0
|
1
|
0
|
0
|
0
|
|
x7
|
155000
|
2
|
3
|
7
|
9
|
0
|
0
|
1
|
0
|
0
|
|
x8
|
250000
|
8
|
5
|
12
|
11
|
0
|
0
|
0
|
1
|
0
|
|
x9
|
100000
|
2
|
3
|
4
|
1
|
0
|
0
|
0
|
0
|
1
|
|
F(X0)
|
0
|
-49
|
-33
|
-76
|
-109
|
0
|
0
|
0
|
0
|
0
|
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные
коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так
как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них
выберем наименьшее: следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца
и ведущей строки.
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
x9
|
min
|
|
x5
|
25000
|
3
|
1
|
2
|
10
|
1
|
0
|
0
|
0
|
0
|
2500
|
|
x6
|
120000
|
4
|
3
|
8
|
6
|
0
|
1
|
0
|
0
|
0
|
20000
|
|
x7
|
155000
|
2
|
3
|
7
|
9
|
0
|
0
|
1
|
0
|
0
|
172222/9
|
|
x8
|
250000
|
8
|
5
|
12
|
11
|
0
|
0
|
0
|
1
|
0
|
227273/11
|
|
x9
|
100000
|
2
|
3
|
4
|
1
|
0
|
0
|
0
|
0
|
1
|
100000
|
|
F(X1)
|
0
|
-49
|
-33
|
-76
|
-109
|
0
|
0
|
0
|
0
|
0
|
0
|
Получаем новую симплекс-таблицу:
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
x9
|
|
x4
|
2500
|
3/10
|
1/10
|
1/5
|
1
|
1/10
|
0
|
0
|
0
|
0
|
|
x6
|
105000
|
21/5
|
22/5
|
64/5
|
0
|
-3/5
|
1
|
0
|
0
|
0
|
|
x7
|
132500
|
-7/10
|
21/10
|
51/5
|
0
|
-9/10
|
0
|
1
|
0
|
|
x8
|
222500
|
47/10
|
39/10
|
94/5
|
0
|
-11/10
|
0
|
0
|
1
|
0
|
|
x9
|
97500
|
17/10
|
29/10
|
34/5
|
0
|
-1/10
|
0
|
0
|
0
|
1
|
|
F(X1)
|
272500
|
-163/10
|
-221/10
|
-541/5
|
0
|
109/10
|
0
|
0
|
0
|
0
|
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся
отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так
как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них
выберем наименьшее: следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1/5) и находится на пересечении ведущего
столбца и ведущей строки.
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
x9
|
min
|
|
x4
|
2500
|
3/10
|
1/10
|
1/5
|
1
|
1/10
|
0
|
0
|
0
|
0
|
12500
|
|
x6
|
105000
|
21/5
|
22/5
|
64/5
|
0
|
-3/5
|
1
|
0
|
0
|
0
|
154413/17
|
|
x7
|
132500
|
-7/10
|
21/10
|
51/5
|
0
|
-9/10
|
0
|
1
|
0
|
0
|
2548010/13
|
|
x8
|
222500
|
47/10
|
39/10
|
94/5
|
0
|
-11/10
|
0
|
0
|
1
|
0
|
227044/49
|
|
x9
|
97500
|
17/10
|
29/10
|
34/5
|
0
|
-1/10
|
0
|
0
|
0
|
1
|
2565717/19
|
|
F(X2)
|
272500
|
-163/10
|
-221/10
|
-541/5
|
0
|
109/10
|
0
|
0
|
0
|
0
|
0
|
Получаем новую симплекс-таблицу:
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
x9
|
|
x3
|
12500
|
11/2
|
1/2
|
1
|
5
|
1/2
|
0
|
0
|
0
|
0
|
|
x6
|
20000
|
-8
|
-1
|
0
|
-34
|
-4
|
1
|
0
|
0
|
0
|
|
x7
|
67500
|
-81/2
|
-1/2
|
0
|
-26
|
-31/2
|
0
|
1
|
0
|
0
|
|
x8
|
100000
|
-10
|
-1
|
0
|
-49
|
-6
|
0
|
0
|
1
|
0
|
|
x9
|
50000
|
-4
|
1
|
0
|
-19
|
-2
|
0
|
0
|
0
|
1
|
|
F(X2)
|
950000
|
65
|
5
|
0
|
271
|
38
|
0
|
0
|
0
|
0
|
Конец итераций: индексная строка не содержит отрицательных элементов -
найден оптимальный план
Окончательный вариант симплекс-таблицы:
|
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
x9
|
|
x3
|
12500
|
11/2
|
1/2
|
1
|
5
|
1/2
|
0
|
0
|
0
|
0
|
|
x6
|
20000
|
-8
|
-1
|
0
|
-34
|
-4
|
1
|
0
|
0
|
0
|
|
x7
|
67500
|
-81/2
|
-1/2
|
0
|
-26
|
-31/2
|
0
|
1
|
0
|
0
|
|
x8
|
100000
|
-10
|
-1
|
0
|
-49
|
-6
|
0
|
0
|
1
|
0
|
|
x9
|
50000
|
-4
|
1
|
0
|
-19
|
-2
|
0
|
0
|
0
|
1
|
|
F(X3)
|
950000
|
65
|
5
|
0
|
271
|
38
|
0
|
0
|
0
|
0
|
Оптимальный план можно записать так:= 12500= 20000= 67500= 100000=
50000(X) = 76•12500 = 950000
Xоптим
= ( 0; 0; 12500; 0; 0; 120000; 155000; 250000; 100000).
Для получения максимальной прибыли 950 000 руб. необхадимо выпустить
тканей рисунков вида Р3 в объеме 12500.
Ткани рисунков вида Р1 , Р2 , Р4 являются убыточными; их производство
нерентабельно.
Проверка при помощи программного продукта (Рисунок 5):
Рисунок 5 - проверка реализованная программным методом.
2.1
Составление и решение двойственной задачи
Обозначим :
y1 -
теневая цена красителя А1;
y2 -
теневая цена красителя А2;
y3 -
теневая цена красителя А3;
y4 -
теневая цена красителя А4;
y5 -
теневая цена красителя А5;
y1 + 120000y2 + 155000y3 + 250000y4 + 100000y5 → min
Решение
двойственной задачи дает оптимальную систему оценок ресурсов.
Используя
последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из
теоремы двойственности следует, что Y = C*A-1.
Составим
матрицу A из компонентов векторов, входящих в оптимальный базис.= (A3, A6, A7,
A8, A9, ) =
|
2
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
0
|
0
|
|
0
|
0
|
1
|
0
|
0
|
|
0
|
0
|
0
|
1
|
0
|
|
0
|
0
|
0
|
0
|
1
|
Определив обратную матрицу D = А-1 через алгебраические дополнения,
получим:
А-1 =
|
1/2
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
0
|
0
|
|
0
|
0
|
1
|
0
|
0
|
|
0
|
0
|
0
|
1
|
0
|
|
0
|
0
|
0
|
1
|
Как видно из последнего плана симплексной таблицы, обратная матрица A-1
расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
(76, 0, 0, 0, 0) x
|
1/2
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
0
|
0
|
|
0
|
0
|
1
|
0
|
0
|
|
0
|
0
|
0
|
1
|
0
|
|
0
|
0
|
0
|
0
|
1
|
= (38;0;0;0;0)
Оптимальный план двойственной задачи равен:= 38= 0= 0= 0= 0
Fmax =
25000*38+120000*0+155000*0+250000*0+100000*0 = 950000.
Таким образом дефицитным красителем является краситель А1 , а к не
дефицитным красителям относятся красители А2 , А3 , А4 , А5 . Недефицитные
красители недоиспользуются на :
¾ краситель А2 на 20 000 грамм;
¾ краситель А3 на 67 500 грамм;
¾ краситель А4 на 100 000 грамм;
¾ краситель А5 на 50 000 грамм;
При
увеличении запасов красителя краситель А1 на 1 ед. (25001 грамм) можно получить
увеличение прибыли на 38 руб., что составит 
950038
руб. При этом план выпуска ткани рисунка Р3 надо увеличить на 0,5 м, т.е
выпустить ткани 
12500,5 . В этом случае недефицитные красители будут
недоиспользоваться :
1. Краситель Р2 - 4 ; его недоиспользование составит 20 004 грамм;
2. Краситель Р3 - 3,5; его недоиспользование составит 67 503,5
грамм;
. Краситель Р4 - 6 ; его недоиспользование составит 100 006 грамм;
. Краситель Р5 - 2 ; его недоиспользование составит 50 002 грамм;
Для
вычисления допустимых пределов изменения запасов красителей составим матрицу 
и вектор-столбец 
:
Найдём
матрицу 
, обратную исходной матрице .
Найдём
допустимые пределы изменения запасов красителей из условий:
Необходимо
найти допустимые пределы изменения отпускной стоимости тканей каждого рисунка.
Для этого необходимо решить двойственную задачу с помощью симплекс метода*:
Запишем
двойственную задачу:
F*= 25000y1 +
120000y2 + 155000y3 + 250000y4 + 100000y5 → min
Приведём
задачу к каноническому виду и преобразуем целевую функцию для решения задачи на
F*= -25000y1
-120000y2 - 155000y3 -
250000y4 - 100000y5 → max
Окончательный
вариант симплекс-таблицы:
|
Базис
|
В
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x7
|
x8
|
x9
|
|
x2
|
18.17
|
1.67
|
1
|
1.5
|
1.83
|
0.83
|
0
|
0
|
0
|
-0.17
|
|
x8
|
69.33
|
11.33
|
0
|
5
|
2.67
|
2.67
|
0
|
0
|
1
|
-1.33
|
|
x6
|
23.67
|
3.67
|
0
|
4
|
-0.67
|
1.33
|
1
|
0
|
0
|
-0.67
|
|
x7
|
21.5
|
4
|
0
|
1.5
|
0.5
|
-0.5
|
0
|
1
|
0
|
-0.5
|
|
F(X9)
|
-227083.33
|
4166.67
|
0
|
136250
|
227083.33
|
89583.33
|
0
|
0
|
0
|
2083.33
|
= 18.17= 69.33= 23.67= 21.5(X) = -12500*18.17 = -227083.33
Составим
матрицу и вектор столбец 
Найдём
матрицу 
Допустимые
пределы изменения отпускной стоимости тканей каждого рисунка:
Оценим
целесообразность введения в план производства ткани с новым рисунком.
т.к.
- отрицательно, введение в план производства ткани с
новым рисунком целесообразно.
Определим
допустимо ли одновременное увеличение запасов дефицитных красителей на 10 000
грамм каждого. Как было выявлено ранее, пределы изменения запасов красителей
определяются из условия :
,
так
же исходя из того что краситель А1 является дефицитным красителем сделаем
вывод, что 
, а 
, тогда
Это
говорит о том что увеличение дефицитных красителей не приводит к изменению
плана производства тканей.
3.
Транспортная задача
.1
Транспортная задача (открытого типа)
Математическая модель транспортной задачи (открытого типа):
при
условиях:
Где
Исходные
данные:
|
1
|
2
|
3
|
Запасы
|
|
1
|
|
1
|
|
9
|
|
4
|
100
|
|
2
|
|
4
|
|
3
|
|
3
|
80
|
|
3
|
|
2
|
|
1
|
|
2
|
50
|
|
4
|
|
6
|
|
2
|
|
9
|
50
|
|
Потребности
|
90
|
100
|
80
|
|
Проверим необходимое и достаточное условие разрешимости задачи.
Так
как , то введем 4-го фиктивного потребителя, спрос
которого 
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
|
1
|
|
9
|
|
4
|
|
0
|
100
|
|
2
|
|
4
|
|
3
|
|
3
|
|
0
|
80
|
|
3
|
|
2
|
|
1
|
|
2
|
|
0
|
50
|
|
4
|
|
6
|
|
2
|
|
9
|
|
0
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
.2 Математическая модель транспортной задачи(закрытого типа)
, (1)
при
условиях:
Стоимость
доставки единицы груза из каждого пункта отправления в соответствующие пункты
назначения задана матрицей тарифов
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1
|
9
|
4
|
0
|
100
|
|
2
|
4
|
3
|
3
|
0
|
80
|
|
3
|
2
|
1
|
2
|
0
|
50
|
|
4
|
6
|
2
|
9
|
0
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 100 + 80 + 50 + 50 = 280
∑b = 90 + 100 + 80 + 10 = 280
Занесем исходные данные в распределительную таблицу.
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1
|
9
|
4
|
0
|
10
|
|
2
|
4
|
3
|
3
|
0
|
80
|
|
3
|
2
|
1
|
2
|
0
|
50
|
|
4
|
6
|
2
|
9
|
0
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Этап I. Поиск первого опорного плана.
Построим первый опорный план транспортной задачи.
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 =
0.
|
v1=1
|
v2=9
|
v3=10
|
v4=1
|
|
u1=0
|
[90]
|
9[10]
|
4
|
0
|
|
u2=-6
|
4
|
3[80]
|
3
|
0
|
|
u3=-8
|
2
|
1[10]
|
2[40]
|
0
|
|
U4=-1
|
6
|
2
|
9[40]
|
0[10]
|
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;3): 4
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1
|
2
|
3
|
|
Запасы
|
|
1
|
1[90]
|
9[10][-]
|
4[+]
|
0
|
100
|
|
2
|
4
|
3[80]
|
3
|
0
|
80
|
|
3
|
2
|
1[10][+]
|
2[40][-]
|
0
|
50
|
|
4
|
6
|
2
|
9[40]
|
0[10]
|
50
|
|
Потребности
|
100
|
80
|
10
|
|
Цикл приведен в таблице (1,3; 1,2; 3,2; 3,3; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у =
min (1, 2) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и
вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый
опорный план.
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[10]
|
0
|
100
|
|
2
|
4
|
3[80]
|
3
|
0
|
80
|
|
3
|
2
|
1[20]
|
2[30]
|
0
|
50
|
|
4
|
6
|
2
|
9[40]
|
0[10]
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 =
0.
|
v1=1
|
v2=3
|
v3=4
|
v4=-5
|
|
u1=0
|
1[90]
|
9
|
4[10]
|
0
|
|
u2=0
|
4
|
3[80]
|
3
|
0
|
|
u3=-2
|
2
|
1[20]
|
2[30]
|
0
|
|
u4=5
|
6
|
2
|
9[40]
|
0[10]
|
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (4;2): 2
Для этого в перспективную клетку (4;2) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[10]
|
0
|
100
|
|
2
|
4
|
3[80]
|
3
|
0
|
80
|
|
3
|
2
|
1[20][-]
|
2[30][+]
|
0
|
50
|
|
4
|
6
|
2[+]
|
9[40][-]
|
0[10]
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Цикл приведен в таблице (4,2; 4,3; 3,3; 3,2; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у =
min (3, 2) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и
вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый
опорный план.
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[10]
|
0
|
100
|
|
2
|
4
|
3[80]
|
3
|
0
|
80
|
|
3
|
2
|
1
|
2[50]
|
0
|
50
|
|
4
|
6
|
2[20]
|
9[20]
|
0[10]
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 =
0.
|
v1=1
|
v2=-3
|
v3=4
|
v4=-5
|
|
u1=0
|
1[90]
|
9
|
4[10]
|
0
|
|
u2=6
|
4
|
3[80]
|
3
|
0
|
|
u3=-2
|
2
|
1
|
2[50]
|
0
|
|
u4=5
|
6
|
2[20]
|
9[20]
|
0[10]
|
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (2;3): 3
Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[10]
|
0
|
100
|
|
2
|
4
|
3[80][-]
|
3[+]
|
0
|
80
|
|
3
|
2
|
1
|
2[50]
|
0
|
50
|
|
4
|
6
|
2[20][+]
|
9[20][-]
|
0[10]
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Цикл приведен в таблице (2,3; 2,2; 4,2; 4,3; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у =
min (4, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и
вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый
опорный план.
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[10]
|
0
|
100
|
|
2
|
4
|
3[60]
|
3[20]
|
0
|
80
|
|
3
|
2
|
1
|
2[50]
|
0
|
50
|
|
4
|
6
|
2[40]
|
9
|
0[10]
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 =
0.
|
v1=1
|
v2=4
|
v3=4
|
v4=2
|
|
u1=0
|
1[90]
|
9
|
4[10]
|
0
|
|
u2=-1
|
4
|
3[60]
|
3[20]
|
0
|
|
u3=-2
|
2
|
1
|
2[50]
|
0
|
|
u4=-2
|
6
|
2[40]
|
9
|
0[10]
|
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;4): 0
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[10][-]
|
0[+]
|
100
|
|
2
|
4
|
3[60][-]
|
3[20][+]
|
0
|
80
|
|
3
|
2
|
1
|
2[50]
|
0
|
50
|
|
4
|
6
|
2[40][+]
|
9
|
0[10][-]
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Цикл приведен в таблице (1,4; 1,3; 2,3; 2,2; 4,2; 4,4; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у =
min (4, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и
вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый
опорный план.
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[0]
|
0[10]
|
100
|
|
2
|
4
|
3[50]
|
3[30]
|
0
|
80
|
|
3
|
2
|
1
|
2[50]
|
0
|
50
|
|
4
|
6
|
2[50]
|
9
|
0
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 =
0.
|
v1=1
|
v2=4
|
v3=4
|
v4=0
|
|
u1=0
|
1[90]
|
9
|
4[0]
|
0[10]
|
|
u2=-1
|
4
|
3[50]
|
3[30]
|
0
|
|
u3=-2
|
2
|
2[50]
|
0
|
|
u4=-2
|
6
|
2[50]
|
9
|
0
|
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (3;2): 1
Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1
|
2
|
3
|
4
|
Запасы
|
|
1
|
1[90]
|
9
|
4[0]
|
0[10]
|
100
|
|
2
|
4
|
3[50][-]
|
3[30][+]
|
0
|
80
|
|
3
|
2
|
1[+]
|
2[50][-]
|
0
|
50
|
|
4
|
6
|
2[0]
|
9
|
0
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Цикл приведен в таблице (3,2; 3,3; 2,3; 2,2; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у =
min (3, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и
вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый
опорный план.
|
1
|
2
|
3
|
4
|
Запаы
|
|
1
|
1[90]
|
9
|
4[0]
|
0[10]
|
100
|
|
2
|
4
|
3[0]
|
3[80]
|
0
|
80
|
|
3
|
2
|
1[50]
|
2
|
0
|
50
|
|
4
|
6
|
2[50]
|
9
|
0
|
50
|
|
Потребности
|
90
|
100
|
80
|
10
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 =
0.
|
v1=1
|
v2=4
|
v3=4
|
v4=0
|
|
u1=0
|
1[90]
|
9
|
4[0]
|
0[10]
|
|
u2=-1
|
4
|
3[0]
|
3[80]
|
0
|
|
u3=-3
|
2
|
1[50]
|
2
|
0
|
|
u4=-2
|
6
|
2[50]
|
9
|
0
|
симплекс метод линейный программирование
Опорный план является оптимальным, так все оценки свободных клеток
удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:(x) = 1*90 + 0*10 + 3*80 + 1*50 + 2*50 = 480
Заключение
В своей работе
я исследовала необходимость использования симплекс метода при расчёте
оптимального плана производства продукции на предприятии (в частности на
производстве тканей и красок). С помощью симплекс метода и действенной задачи
был проведён анализ целесообразности производства продукции, а так же выявлены
дефицитные и недефицитные виды красок. Так же были проведены аналитические
расчёты позволяющие сделать вывод об изменение доходности при увеличение
используемых ресурсов на производстве.
Реализованный в среде программирования Delphi метод обеспечивает его доступность использования при
необходимости.