Линейное программирование
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
ьное решение.
Правила преобразований симплексной таблицы.
При составлении новой симплекс-таблицы в ней происходят следующие изменения:
1)Вместо базисной переменной xk записываем xl; вместо небазисной переменной xlзаписываем xk.
2)ведущий элемент заменяется на обратную величину ak,l= 1/ak,l
3)все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l
4)все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l
5)оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j= ai,j- ai,lx ak,j/ ak,l
Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой прямоугольника.
Преобразуемый элемент 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)
БазисBx1x2x3x4x381210x436-101F(X0)0-1-100
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
БазисBx1x2x3x4minx3812104x436-101-F(X1)0-1-1000
Получаем новую симплекс-таблицу:
БазисBx1x2x3x4x241/211/20x4761/201/21F(Х1)4-1/201/20
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее, следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (61/2) и находится на пересечении ведущего столбца и ведущей строки.
БазисBx1x2x3x4minx241/211/208x4761/201/2111/13F(X2)4-1/201/200
Получаем новую симплекс-таблицу:
БазисBx1x2x3x4x236/13016/13-1/13x111/13101/132/13F(X2)47/13007/131/13
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
БазисBx1x2x3x4x236/13016/13-1/13x111/13101/132/13F(X3)47/13007/131/13
Оптимальный план можно записать так:= 36/13= 11/13(X) = 136/13 + 111/13 = 47/13.
Используя программу Симплекс-метод, получим аналогичный результат (Рисунок 4).
Рисунок 4 - результат вычисления полученный путём проверки в программе SIMPLEX.
2. Двойственная задача
Исходные данные (Рисунок 5):
Номер ВариантаВид КрасителейРазновидность рисунка. Расход красителей на окраску 1 м ткани (грамм)Запасы красителей (грамм)Р1Р2Р3Р41А13121025 000А24386120 000А32379155 000А4851211250 000А52341100 000Стоимость одного метра ткани (руб.)493376109Рисунок 5 - таблица исходных данных.
. Для определение плана выпуска ткани каждого вида рисунка, обеспечивающего максимальный доход от реализации тканей необхадимо составить экономико-математическую модель задачи. Для этого введём обозначения следующего вида:
- план выпуска ткани рисунка вида ;
- план выпу?/p>