Методические указания и контрольные задания для студентов экономических специальностей бнту
Скачать 0.66 Mb.
|
Z = x – 3y -x + y 4 5x + 4y 34 x + 8y 14 Решение. Построим допустимую область. Для этого в системе координат х0y строим прямую -x + y= 4 - границу первого ограничения. Затем определяем, в какой полуплоскости находятся точки (х, y), для которых -x + y < 4. Для этого выбираем любую точку, например (0, 0) , и проверяем, удовлетворяет ли она этому неравенству. Поскольку -0 + 0 = 0 < 4, то точки, для которых -x+y 4 лежат в той же полуплоскости, что и точка О(0, 0), т.е. справа (ниже) от границы -x + y = 4.  y   8,5 -x + y = 4L2 C L0 4 B L1  E1,75 A D    0 1 6,8 14 yx + 8y =14  -3  5x + 4y = 34Аналогично строятся остальные полуплоскости, соответствующие ограничениям 5х + 4у 34 и х + 8у 14 (ниже прямой 5х + 4у = 34 и выше прямой х + 8у = 14 ). Множество точек, удовлетворяющих всем трем неравенствам, образуют треугольник ECD. Учитывая ограничение х 0 и у 0, получаем допустимую область – четырехугольник ABCD. Проведем линию уровня L0, соответствующую значению Z =0, т.е. прямую х – 3у = 0 (для точек, лежащих на этой прямой, значение Z =0). Она будет проходить через точку О(0, 0) перпендикулярно вектору  . Перемещая линию уровня в направлении градиента  , т.е. в направлении возрастания ^ , находим последнюю точку допустимой области, которую линия уровня пересекает при этом движении (линия L1). Это будет точка максимума. В нашем случае – это точка D(6, 1), координаты которой можно найти, решив систему линейных уравнений 5х + 4у = 34 и х + 8у = 14. Аналогично, двигая линию уровня в противоположном направлении до линии L2, находим точку минимума – точку С(2, 6). Таким образом, Zmax= Z(6,1)= 6 - 31=3, Zmin=Z(2,6)=2-36=-16 .Задача решена полностью. ^ Задание 2. Геометрическим методом найти максимум и минимум функции Z для x, y 0 при заданных ограничениях: Варианты: 1. Z = 2x + y 2. Z = 3x + y  3x - 4y 4 y 1-x + 6y 8 x - 2y 3 x + y 1 2x + y 1 3. Z = 2x - y 4. Z = x + y  2x + y 3 y 2x + y 6 x + y 7 x - 3y 3 -x + 2y 2 5. Z = 4x + y 6. Z = 3x - y x - 2y 0 2x + 3y 134x - y 14 x 2 3x + y 7 5x - 3y 22 7. Z = 2x + y 8. Z = x + 5y x 2 3x - y 34x - y 8 x - y 4 x - y -1 x + y 6 9. Z = 5x + y 10. Z = 3x x - 4y -3 x + y 74x - 3y 14 2x - y 11 3x + y 4 4x + y 19 ^ . Решение задачи линейного программирования Симплекс-методом Задача линейного программирования (ЗЛП) (1) - (3) (см. задание 2) называется канонической, если все ограничения вида (2) являются уравнениями (равенствами), т.е. задачей линейного программирования в канонической форме называется задача: Z = c1 x1 + c2 x2 + . . .+ cn xn min (max) (1) при ограничениях :  a11 x1 + a12 x2 + . . .+ a1n xn = b1 a21 x1 + a22 x2 + . . .+ a2n xn = b2 (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . am1 x1 + am2 x2 + . . .+ amn xn = bm , xj 0 , j = 1, . . . , n (3) Симплекс-метод является вычислительной процедурой, которая позволяет решить любую каноническую ЗЛП алгебраическим методом. Теоретической основой метода являются следующие два утверждения: Теорема 1. Если ЗЛП имеет допустимые решения, то существует хотя бы одно базисное допустимое решение задачи. Теорема 2. Если ЗЛП имеет конечное оптимальное решение, то хотя бы одно из оптимальных решений является базисным. Напомним, что решение системы (2) называется допустимым, если оно удовлетворяет ограничениям (3). Таким образом, из теоремы 1 следует, что если не существует ни одного базисного допустимого решения системы (2), то эта система вообще не имеет допустимых решений, т.е. ограничения (2) – (3) являются несовместными. В случае если имеются допустимые решения системы 2, то теорема 2 утверждает, что оптимальное решение ЗЛП можно найти среди базисных допустимых решений этой системы, которых, как мы знаем, конечное число. Суть симплекс-метода и состоит в последовательном переборе базисных допустимых решений системы (2), начиная с некоторого начального, которое еще называют первоначальным опорным планом. Перебор осуществляется таким образом, чтобы каждое новое решение было лучше предыдущего (в смысле приближения к максимуму или минимуму целевой функции Z). Итак, для применения метода необходимо, чтобы задача была в канонической форме, и чтобы существовало начальное базисное допустимое решение (опорный план), наличие которого гарантирует непротиворечивость ограничений задачи. Чтобы преобразовать ЗЛП к каноническому виду к правой части каждого ограничения-неравенства прибавляют или вычитают неотрицательную дополнительную переменную, например, ограничение 3х1 + 5х2 – 2х3 7 преобразуется в уравнение 3х1 + 5х2 – 2х3 + х4 = 7 прибавлением дополнительной переменной х4 0, а неравенство вида х1 – 2х2 + х3 5 заменяется на уравнение х1 – 2х2 + х3 - х5 = 5, где х5 0. Заметим, что знак неравенства можно заменить на умножением всего неравенства на -1, например, неравенство х1 – 3х2 -6 эквивалентно неравенству -х1 + 3х2 6. Отметим также, что максимизацию целевой функции Z можно заменить на минимизацию функции –Z и наоборот, так как максимум функции Z = c1 x1 + c2 x2 + . . .+ cn xn достигается в тех же точках, что и минимум функции -Z = -c1 x1 - c2 x2 - . . .- cn xn . Мы приведем алгоритм симплекс-метода для минимизации целевой функции (1) Z = c1 x1 + c2 x2 + . . .+ cn xn . Поясним суть метода на следующем примере: Пусть требуется решить следующую ЗЛП: Найти максимум функции Z = 3x1 +4 x2 max при ограничениях:  3x1 + x2 9x1 + 2x2 8 x1 , x2 0. Приведем задачу к каноническому виду и заменим максимизацию целевой функции Z на минимизацию функции Z = -Z. Получим следующую задачу: Z = -3x1 - 4x2 + 0х3 + 0х4 min (4)  3x1 + x2 + x3 = 9x1 + 2x2 + x4 = 8 (5) x1 , x2 , x3 , x4 0. (6) Ясно, что переменные x3 и x4 являются базисными в системе (5) и соответствующее базисное решение Х0 = ( 0, 0, 9, 8) является допустимым, т.к. все xj 0. При этом Z0 = 0. Начнем с того, что проверим опорный план Х0 на оптимальность. Поскольку целевая функция Z = -3x1 - 4 x2 + 0х3 + 0х4 выражена через свободные переменные x1 и x2, коэффициенты при которых отрицательны, то, очевидно, увеличение этих переменных приведет к уменьшению значения целевой функции на 3 ед. при увеличении x1 на одну единицу и на 4 ед. при увеличении на одну единицу x2 (сейчас x1 и x2 равны 0 ). Поэтому делаем вывод, что опорный план Х0 не является оптимальным (т.к. введение в базис переменных x1 и x2 приведёт к уменьшению значения целевой функции). Итак, для того, чтобы получить лучшее базисное решение, мы должны включить в базис переменные x1 и x2 . Будем вводить их в базис по очереди. Поскольку увеличение переменной x2 быстрее уменьшает Z, то выбираем переменную x2 для включения ее в базис (это разумно, но не обязательно). Теперь надо выяснить в какой строке системы (5) переменная x2 будет базисной, чтобы полученное новое базисное решение было допустимым. Анализируя первое уравнение системы 3x1 + x2 + x3 = 9, замечаем, что поскольку x1 = 0, то увеличение x2 влечет уменьшение x3. Так как x3 0 ввиду (6), то увеличение x2 возможно лишь до тех пор, пока x3 не уменьшится до нуля, т.е. до значения 9/1 = 9. Поскольку переменная x2 есть также и во втором уравнении, то рассуждая аналогично, заключаем, что в этом случае переменную x2 можно увеличивать максимум до значения 8/2 = 4 при котором переменная x4 уменьшится до нуля. Новое базисное решение будет допустимым, если мы будем увеличивать переменную х2 до значения, равного min{9/1, 8/2} = 4, которое достигается во второй строке системы. Поэтому переменная x2 должна быть базисной во втором уравнении, элемент а22 = 4 системы будет разрешающим и, проводя преобразования Жордана-Гаусса, получаем новое (улучшенное) базисное допустимое решение:  X1 = ( 0, 4, 5, 0 ), Z1 = -30 - 4 4 + 05 + 00 = -16 < Z0 . Теперь повторим эту процедуру для нового опорного плана Х1 . Для того, чтобы проверить его на оптимальность, нужно выразить целевую функцию через свободные переменные x1 и x4 этого плана, поскольку их нужно будет изменять, чтобы получить другое (лучшее) базисное решение. Для этого из второго уравнения последней системы выражаем базисную переменную х2 = 4 – ½ x1 - ½ x4 и подставляем ее в целевую функцию Z = -3x1 - 4 x2 + 0х3 + 0х4 = -3x1 - 4 (4 – ½ x1 - ½ x4 ) + 0х3 + 0х4 = -16 – x1 + 0х2 + 0х3 + 2x4 . Проводимые вычисления удобно оформлять в виде так называемых симплекс-таблиц, которые являются, фактически, расширенными матрицами системы ограничений (5) с добавленной Z – строкой. Исходная симплекс-таблица.
Опорный план Х0 = ( 0, 0, 9, 8) , значение Z равно Z0 = 0. Таблица 1.
| |||||||||||||||||||||
х3 
3 1 1 0 
х3 
5/2 0 1 -½ Похожие:
 | Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также... | | Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также... |
| Немецкий язык : методические указания и контрольные задания для студентов 2 курса железнодорожных специальностей заочной формы обучения... | | Производственные технологии : программа, методические указания и контрольные задания для студентов специальностей 1-25 01 07 – Экономика... |
| Методические указания и контрольные задания по дисциплине Стандартизация норм точности для студентов специальности: 1- 38. 02. 01... | | Методические указания к изучению дисциплины “Логистика” составлены на основе требований Государственного общеобразовательного стандарта... |
| Статистика: методические указания и контрольные задания для студентов специальностей 1-26 02 02 «Менеджмент» и 1-26 02 03 «Маркетинг»... | | Методические указания и контрольные задания по дисциплине "Электротехника и электроника" для студентов спец. 37 01 06 "Техническая... |
| ... | | Методические указания предназначены для студентов экономических специальностей заочной формы обучения. Они составлены в соответствии... |