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

КУРСОВОЙ ПРОЕКТ ПО ДИСЦИПЛИНЕ.

«ЕКОНОМІЧНО-МАТЕМАТИЧНЕ МОДЕЛИРОВАНИЕ».

Тема. Лінійне програмування: постановка завдань і графічне решение.

Науковий руководитель:

Чернов.

Олександр Степанович.

Исполнитель:

Кудрявцева.

Олена Александровна.

Р. Мурманск.

1998 год.

ПЛАН.

Введение

1. Загальна завдання лінійного программирования.

1. Формулювання задачи.

2. Геометрична інтерпретація завдання лінійного програмування. 2. Графічний метод виконання завдання лінійного программирования.

1. Область применения.

2. Приклади завдань, розв’язуваних графічним методом.

3. Узагальнення графічного методу вирішення завдань лінійного програмування.

Литература

.

Лінійне програмування — це наука про методи дослідження та відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Отже, завдання лінійного програмування ставляться до завдань на умовний екстремум функції. Здається, що з дослідження лінійної функції багатьох змінних на умовний екстремум досить застосувати добре розроблені методи математичного аналізу, проте неможливість їх використання можна досить просто проиллюстрировать.

Справді, шлях необхідно досліджувати на екстремум лінійну функцію Z = С1×1+С2×2+… +СNxN при лінійних ограничениях.

a11×1 + a22×2 + … + a1NХN = b1 a21×1 + a22×2 + … + a2NХN = b2.

.. .. .. .. .. .. ... aМ1×1 + aМ2×2 + … + aМNХN = bМ.

Оскільки Z — лінійна функція, то = Сj (j = 1, 2, …, n), усі коефіцієнти лінійної функції неможливо знайти рівні нулю, отже, всередині області, освіченою системою обмежень, екстремальні точки не існують. Вони може бути за українсько-словацьким кордоном області, але досліджувати точки кордону неможливо, оскільки приватні похідні є константами.

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

1. Загальна завдання лінійного программирования.

1. Формулювання задачи.

Дани лінійна функція (1.1) Z = С1×1+С2×2+… +СNxN і системи лінійних обмежень a11×1 + a22×2 + … + a1NХN = b1 a21×1 + a22×2 + … + a2NХN = b2.

.. .. .. .. .. .. ... (1.2) ai1x1 + ai2x2 + … + aiNХN = bi.

.. .. .. .. .. .. ... aM1x1 + aM2x2 + … + aMNХN = bM.

(1.3) xj 0 (j = 1, 2, …, n) де аij, Ьj і Сj — задані постійні величины.

Знайти такі неотрицательные значення х1, х2, …, хn, які задовольняють системі обмежень (1.2) і доставляють лінійної функції (1.1)минимальное значение.

Загальна завдання має низку форм записи.

Векторна форма записи. Мінімізувати лінійну функцію Z = СХ при обмеженнях (1.4) А1×1 + А2×2 + … + АNxN = Ат, X 0 де З = (с1, с2, …, сN); Х = (х1, х2, …, хN); СХ — скалярне твір; векторы.

A1 =, A2 = ,…, AN =, A0 =.

складаються відповідно з коефіцієнтів при невідомих і вільних членах.

Матрична форма записи. Мінімізувати лінійну функцію, Z = СХ при обмеженнях АХ = А0, Х 0, де З = (с1, с2, …, сN) — матрица-cтрока; А = (аij) — матриця системы;

Х = - матрица-столбец, А0 = матрица-столбец.

Запис з допомогою знаків підсумовування. Мінімізувати лінійну функцію Z = Сjхj при ограничениях.

0пределение 1. Планом чи допустимим рішенням завдання лінійного програмування називається Х = (х1, х2, …, хN), зрозумілу умовам (1.2) і (1.3).

0пределение 2. План Х = (х1, х2, …, хN) називається опорним, якщо вектори, А (і = 1, 2, …, N), що входять до розкладання (1.4) з позитивними коефіцієнтами x, є лінійно независимыми.

Оскільки вектори, А N-мерными, те з визначення опорного плану слід, що кількість його позитивних компонент неспроможна перевищувати М.

0пределение 3. Опорний план називається невырожденным, коли він містить М позитивних компонент, інакше опорний план називається вырожденным.

0пределение 4. Оптимальним планом чи оптимальним розв’язанням завдання лінійного програмування називається план, яка доставляє найменше (найбільше) значення лінійної функции.

Надалі розглянуто вирішення завдань лінійного програмування, що з перебуванням мінімального значення лінійної функції. Там, де необхідно знайти максимальне значення лінійної функції, досить замінити на протилежний знак лінійної функції і знайти мінімальне значення останньої функції. Замінюючи на протилежний знак отриманого мінімального значення, визначаємо максимальне значення вихідної лінійної функции.

2. Геометрична інтерпретація завдання лінійного программирования.

Розглянемо завдання лінійного програмування, система обмежень якої задана як неравенств.

Знайти мінімальне значення лінійної функции.

(1.5) Z = С1×1+С2×2+… +СNxN при обмеженнях a11×1 + a22×2 + … + a1NХN b1 a21×1 + a22×2 + … + a2NХN b2.

(1.6). .. .. .. .. .. .. .. aM1x1 + aM2x2 + … + aMNХN bM.

(1.7) xj 0 (j = 1, 2, …, n).

Сукупність чисел х1, х2, …, хN, які відповідають обмеженням (1.6) і (1.7), називається рішенням. Якщо цю систему нерівностей (1.6) за умови (1.7) має хоча одне рішення, вона називається спільної, у протилежному разі - несовместной.

Розглянемо на площині х1Ох2 спільну систему лінійних неравенств.

a11×1 + a22×2 b1 a21×1 + a22×2 b2.

.. .. .. .. aM1x1 + aM2x2 bM.

x1 0, x2 0.

Це саме, що у системі (1.6) — (1.7) покласти N=2. Кожне нерівність цією системою геометрично визначає полуплоскость з граничной прямий ai1x1 + ai2x2 = bi ,(і = 1, 2, …, m). Умови неотрицательности визначають напівплощини за граничними прямими x = 0, x = 0. Система совместна, тому напівплощини, як опуклі безлічі, перетинаючись, утворюють загальну частина, що є опуклим безліччю і є сукупність точок, координати кожної у тому числі є розв’язання цієї системи (рис. 1.1).

Сукупність цих точок (рішень) назвемо многоугольником рішень. Він то, можливо точкою, відрізком, променем, много-угольником, неограничен-ной багатокутної облас-тью.

Якщо системі обмежень (1.6) — (1.7) n = 3, то кожне нера-венство геометрично представляє полупространство тривимірного простору, гранична площину якого ai1x1 + ai2x2 + ai3x3 = bi ,(і = 1, 2, …, n), а умови неотрицательности — полупрост-ранства з граничними площинами відповідно хj = 0 (j = 1, 2, 3). Якщо цю систему обмежень совместна, то ці полупространства, як опуклі безлічі, перетинаючись, утворюють в тривимірному просторі загальну частина, що називається багатогранником рішень. Багатогранник рішень то, можливо точкою, відрізком, променем, многоугольником, багатогранником, багатогранної необмеженої областю. нехай у системі обмежень (1.6) — (1.7) n 3; тоді кожне нерівність визначає полупространство n-мерного простору з граничной гиперплоскостью ai1x1 + ai2x2 + aiNxN = bi (і = 1, 2, …, m), а умови неотрицательности — полупространства з граничними гиперплоскостями хj 0 (j = 1, 2, …, n).

Якщо цю систему обмежень совместна, то аналогії з тривимірним простором вона утворює загальну частина n-мерного простору, звану багатогранником рішень, оскільки координати кожної його точки є решением.

Отже, геометрично завдання лінійного програмування є пошук такий точки багатогранника рішень, координати якої доставляють лінійної функції мінімальне значення, причому припустимими рішеннями служать всі крапки багатогранника решений.

2. Графічний метод виконання завдання лінійного программирования.

1. Область применения.

Графічний метод грунтується на геометричній інтерпретації завдання лінійного програмування використовується переважно під час вирішення завдань двумерного простору й лише окремих завдань тривимірного простран6тва, оскільки досить складно побудувати багатогранник рішень, що утворюється внаслідок перетину полупространств. Завдання простору розмірності більше трьох намалювати графік взагалі невозможно.

Нехай завдання лінійного програмування задана в двовимірному просторі, т. е. обмеження містять дві переменные.

Знайти мінімальне значення функции.

(2.1) Z = С1×1+С2×2 при a11×1 + a22×2 b1 (2.2) a21×1 + a22×2 b2.

.. .. .. .. aM1x1 + aM2x2 bM.

(2.3) х1 0, х2 0.

Допустим, що систему (2.2) за умови (2.3) совместна і його багатокутник рішень обмежений. І з нерівностей (2.2) і (2.3), як вище, визначає полуплоскость з граничними прямими: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, …, n), х1=0, х2=0. Лінійна функція (2.1) при фіксованих значеннях Z є рівнянням прямий лінії: С1×1 + С2×2 = const. Побудуємо багатокутник рішень системи обмежень (2.2) і графік лінійної функції (2.1) при Z = 0 (рис. 2.1). Тоді поставленому завданню лінійного прграммирования можна надати таку інтерпретацію. Знайти точку багатокутника рішень, у якій пряма С1×1 + С2×2 = const опорна і функція Z у своїй сягає минимума.

Значення Z = С1×1 + С2×2 зростають у напрямі вектора N =(С1, С2), тому пряму Z = 0 передвигаем паралельно сама собі у бік вектора Х. З рис. 2.1 слід, що пряма двічі стає опорною по відношення до многоугольнику рішень (в точках Проте й З), причому мінімальне значення приймає у точці А. Координати точки, А (х1, х2) знаходимо, вирішуючи систему рівнянь прямих АВ і АЕ.

Якщо багатокутник рішень є необмежену многоуголь-ную область, можливі два случая.

Випадок 1. Пряма С1×1 + С2×2 = const, пересуваючись у бік вектора N чи протилежно йому, постійно перетинає багатокутник прийняття рішень та у жодній точці перестав бути опорною щодо нього. І тут лінійна функція не обмежена на многоугольнике рішень як згори, і знизу (рис. 2.2).

Випадок 2. Пряма, пере-двигаясь, все-таки стає опорною щодо многоу-гольника рішень (рис. 2.2, а — 2.2, в). Тоді, у зави-симости від виду області ли-нейная функція то, можливо обмеженою зверху і необмеженої знизу (рис. 2.2, а), обмеженою знизу і необмеженої згори (рис. 2.2, б), або обмеженою як знизу, і згори (рис. 2.2, в).

2.1. Приклади завдань, розв’язуваних графічним методом.

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

Завдання використання сировини. Для виготовлення два види продукції Р1 і Р2 використовують три виду сировини: S1, S2, S3. Запаси сировини, кількість одиниць сировини, витрачених на виготовлення одиниці продукци, а як і величина прибутку, отримувана від одиниці виробленої продукції, наведені у таблиці 2.1.

Таблиця 2.1. |Вигляд сировини |Запас сировини |Кількість одиниць сировини, які йдуть | | | |на виготовлення одиниці виробленої продукції| | | |Р1 |Р2 | |S1 |20 |2 |5 | |S2 |40 |8 |5 | |S3 |30 |5 |6 | |Прибуток від одиниці виробленої продукції, крб. |50 |40 |.

Необхідно скласти такий план випуску продукції, щоб за її реалізації забезпечити максимальну прибыль.

Решение.

Означимо через х1 кількість одиниць продукції Р1, а ще через х2 — кількість одиниць продукції Р2. Тоді, якщо врахувати чисельність одиниць сировини, расходуемое на виготовлення продукції, а як і запаси сировини, одержимо систему ограничений:

2х1 + 5×2 20.

8х1 + 5×2 40.

5х1 + 6×2 30.

которая показує, що його сировини, расходуемое на виготовлення продукції, неспроможна перевищить наявних запасів. Якщо продукція Р1 не випускається, то х1=0; інакше x1 0. Це ж отримуємо й у продукції Р2. Отже, на невідомі х1 і х2 має бути накладено обмеження неотрицательности: х1 0, х2 0.

Кінцеву мета розв’язуваної завдання — отримання максимального прибылипри реалізації продукції - висловимо як функцію двох змінних х1 і х2. Реалізація х1 одиниць продукції Р1 і х2 одиниць продукції Р2 дає відповідно 50×1 і 40×2 крб. прибутку, сумарна прибуток Z = 50×1 + 40×2 (руб.).

Умовами не обумовлено неподільність одиниця продукції, тому х1 і х2 (план випуску продукції) можуть і дробовими числами.

Потрібна знайти такі х1 і х2, у яких функція Z достинает максимум, тобто. знайти максимальне значення лінійної функції Z = 50×1 + 40×2 при ограничениях.

2х1 + 5×2 20.

8х1 + 5×2 40.

5х1 + 6×2 30.

х1 0, х2 0.

Побудуємо багатокутник рішень (рис. 2.3).

І тому у системі координат х1Ох2 на площині на площині зобразимо граничні прямые.

2х1 + 5×2 = 20 (L1).

8х1 + 5×2 = 40 (L2).

5х1 + 6×2 = 30 (L3).

х1 = 0, х2 = 0.

Взяв якусь точку, наприклад, початок координат, встановимо, яку полуплоскость визначає відповідне нерівність (ці напівплощини на рис. 2.3 показані стрілками). Многоугольником варіантів розв’язання завдання є обмежений п’ятикутник ОАВСD.

Для побудови прямий 50×1 + 40×2 = 0 будуємо радиус-вектор N = (50;40) = 10(5;4) і крізь точку O проводимо пряму, перпендикулярну йому. Побудовану пряму Z = 0 перемещаем паралельно сама собі у бік вектора N. З риc. 2.3 слід, що опорною стосовно многоугольнику рішень ця пряма стає у точці З, де функція Z приймає максимальне значення. Крапка З лежить на жіночих перетині прямих L1 і L2. Для визначення її координат вирішимо систему уравнений.

8x1 + 5×2 = 40.

5х1 + 6×2 = 30.

Оптимальний план завдання: х1 = 90/23 = 3,9; х2 = 40/23 = 1,7. Підставляючи значення х1 і х2 в лінійну функцію, отримуємо Zmax = 50 3,9 + 40 1,7 = 260,3.

Отже, щоб забезпечити максимальну прибуток у розмірі 260,3 крб., необхідно запланувати виробництво 3,9 од. продукції Р1 і 1,7 од. продукції Р2.

Завдання складання раціону. При відгодівлі кожну особину щодня має отримувати щонайменше 9 од. живильного речовини S1, щонайменше 8 од. речовини S2 і проінвестували щонайменше 12 од. речовини S3. Для складання раціону використовують два виду корми. Зміст кількості елиниц поживних речовин один кг кожного виду корми й вартість кг корми наведені у таблиці 2.2.

Таблиця 2.2. |Живильні речовини |Кількість одиниць поживних | | |речовин | | |один кг корми. | | |Корм 1 |Корм 2 | |S1 |3 |1 | |S2 |1 |2 | |S3 |1 |6 | |Вартість 1 кг корми, коп. |4 |6 |.

Необхідно скласти денний раціон потрібної поживністю, причому на нього би мало бути минимальными.

Решение.

Для складання математичну модель позначимо через х1 і х2 відповідно кількість кілограмів корми 1 і 2 в денному раціоні. Беручи до уваги значення, наведені у таблиці 2.2, і умова, що денний раціон задовольняє необхідної поживністю лише тоді, якщо кількість одиниць поживних речовин незгірш від передбаченого, отримуємо систему ограничений.

3х1 + х2 9×1 + 2×2 8×1 + 6×2 12.

х1 0, х2 0.

Якщо корм 1 немає в раціоні, то х1=0; інакше x1 0. Аналогічно маємо х2 0. Тобто мало виконуватися умова неотрицательности змінних: х1 0, х2 0.

Мета цієї завдання — домогтися мінімальних витрат за денний раціон, тому загальну вартість раціону можна сформулювати як лінійної функції Z = 4×1 + 6×2 (коп.).

Потрібна знайти такі х1 і х2, у яких функція Z приймає мінімальне. Отже, необхідно знайти мінімальне значення лінійної функції Z = 4×1 + 6×2 при ограничениях.

3х1 + х2 9×1 + 2×2 8×1 + 6×2 12.

х1 0, х2 0.

Побудуємо багатокутник рішень (рис. 2.4). І тому у системі координат х1Ох2 на площині зобразимо граничні прямые.

3х1 + х2 = 9 (L1) х1 + 2×2 = 8 (L2) х1 + 6×2 = 12 (L3).

х1 = 0, х2 = 0.

Узявши якусь точку, наприклад, початок координат, встановимо, яку полуплоскость визначає відповідне нерівність (ці напівплощини на рис. 2.4 показані стрілками). Через війну одержимо необмежену багатокутну область з кутовими точками А, У, З, D.

Для побудови прямий 4×1 + 6×2 = 0 будуємо радиус-вектор N = (4;6) і через точку O проводимо пряму, перпендикулярну йому. Побудовану пряму Z = 0 перемещаем паралельно сама собі у бік вектора N. З риc. 2.4 слід, вона вперше торкнеться багатогранника прийняття рішень та стане опорною по відношення до йому у кутовий точе У. Якщо пряму переміщати далі в напрямі вектора N, то значення лінійної функції на многограннике рішень зростуть, отже, у точці У лінійна функція Z приймає мінімальне значение.

Крапка У лежить на жіночих перетині прямих L1 і L2. Для визначення її координат вирішимо систему уравнений.

3x1 + х2 = 9×1 + 2×2 = 8.

Маємо: х1 = 2; х2 = 3. Підставляючи значення х1 і х2 в лінійну функцію, отримуємо Zmin = 4 2 + 6 3 = 26.

Отже, у тому, щоб забезпечити мінімум витрат (26 коп. в день), необхідно денний раціон скласти з 2 кг корми 1 і трьох кг корми 2.

2. Узагальнення графічного методу вирішення завдань лінійного программирования.

Взагалі, з допомогою графічного методу то, можливо ре-шена завдання лінійного програмування, система ограниче-ний якої містить n невідомих і m лінійно независи-мых рівнянь, якщо N і M пов’язані співвідношенням N — M = 2.

Справді, нехай поставили завдання лінійного программирования.

Знайти мінімальне значення лінійної функції Z = С1×1+С2×2+… +СNxN при ограничениях.

a11×1 + a22×2 + … + a1NХN = b1 (2.3) a21×1 + a22×2 + … + a2NХN = b2.

.. .. .. .. .. .. ... aМ1×1 + aМ2×2 + … + aМNХN = bМ.

xj 0 (j = 1, 2, …, N).

где все рівняння лінійно незалежні і виконується cоотношение N — M = 2.

Використовуючи метод Жордана-Гаусса, виробляємо M винятків, внаслідок яких засадничими невідомими виявилися, наприклад, M перших невідомих х1, х2, …, хM, а вільними — останні двоє: хМ+1, і хN, т. е. система обмежень прийняла вид.

x1 + a1, М+1xМ+1 + a1NХN = b1 (2.4) x2 + a2, М+1xМ+1 + a2NХN = b2.

.. .. .. .. .. .. xМ + aМ, М+1×2 + aМNХN = bМ.

xj 0 (j = 1, 2, …, N).

З допомогою рівнянь реформованій системи висловлюємо лінійну функцію лише крізь вільні невідомі та враховуючи, що це базисні невідомі - неотрицательные: хj 0 (j = 1, 2, …, M), відкидаємо їх, переходячи до системи обмежень, виражених у вигляді нерівностей. Таким чином, остаточно отримуємо таку задачу.

Знайти мінімальне значення лінійної функції Z = СМ+1хМ+1+СNxN при ограничениях.

a1,М+1xМ+1 + a1NХN b1 a2, М+1xМ+1 + a2NХN b2.

.. .. .. .. .. aМ, М+1xМ+1 + aМNХN bМ.

xМ+1 0, хN 0.

Перетворена завдання містить два невідомих; вирішуючи її графічним методом, знаходимо оптимальні значення xМ+1 і хN, та був, підставляючи в (2.4), знаходимо оптимальні значення х1, х2, …, хM.

Пример.

Графічним методом знайти оптимальний план завдання ли-нейного програмування, у якому лінійна функція Z = 2×1 — х2 + х3 — 3×4 + 4×5 сягає максимального значення при ограничениях.

х1 — х2 + 3×3 — 18×4 + 2×5 = -4.

2х1 — х2 + 4×3 — 21×4 + 4×5 = 2.

3х1 — 2×2 + 8×3 — 43×4 + 11×5 = 38.

xj 0 (j = 1, 2, …, 5).

Решение.

Використовуючи метод Жордана-Гаусса, зробимо три повних винятку невідомих х1, х2, х3. Через війну дійшли системі х1 + х4 — 3×5 = 6×2 + 7×4 + 10×5 = 70×3 — 4×4 + 5ґ5 = 20.

Звідки x1 = 6 — х4 + 3×5, х2 = 70 — 7×4−10×5, х3 = 20 + 4×4 -5×5.

Підставляючи цих значень до функцій і відкидаючи у системі базисні перемінні, отримуємо завдання, виражену лише крізь вільні перемінні х4 і х5: знайти максимальне значення лінійної функції Z = 6×4 + 15×5 — 38 при обмеженнях х4 — х5 6.

7х4 + 10×5 70.

— 4×4 + 5ґ5 20.

х4 0, х5 0.

Побудуємо багатогранник прийняття рішень та лінійну функцію у системі координат х4Ох5 (рис. 2.5). З рис. 2.5 укладаємо, що лінійна функція приймає максимальне значення в кутовий точці У, що лежить на перетині прямих 2 і трьох. Через війну рішення системы.

7х4 + 10×5 = 70.

— 4×4 + 5ґ5 = 20.

— знаходимо: х4 = 2, х5 = 28/5. Максимальне значення функції Zmax = -38 + 12 + 84 = 58.

Для відшукання оптимального плану вихідної завдання підставляємо знайдені значення х4 і х5. Остаточно отримуємо: х1 = 104/5, х2 = 0, х3 = 0, х4 = 2, х5 = 28/5.

1. Математичні методи аналізу економіки /під ред. А. Я. Боярского. М., Изду Моск. Ун-ту, 1983 2. А. И. Ларионов, Т. И. Юрченко «Економіко-математичні методи в плануванні: Підручник — М.: Высш. школа, 1984 3. Ашманов С. А. «Лінійне програмування», — М.: 1961.