otvety_na_praktiku


БИЛЕТ№1
ЗАДАЧА №1
Розв’язати наступну задачу: компанія контролює три фабрики А1, А2, А3, здатні виготовляти 150, 60 та 80 тис.од. продукції щотижня. Компанія уклала договір з чотирма замовниками В1, В2, В3, В4, яким потрібно щотижня відповідно 110, 40, 60 та 80 тис.од. продукції. Вартість виробництва та транспортування 1000 од. продукції замовниками з кожної фабрики наведено в таблиці.
Фабрика Вартість виробництва і транспортування 1000 од. продукції за замовниками
В1 В2 В3 В4
А1 4 4 2 5
А2 5 3 1 2
А3 2 1 4 2
Визначити для кожної фабрики оптимальний план перевезення продукції до замовників, що мінімізує загальну вартість виробництва і транспортних послуг.
Відповідь: Z3 = 720 (ум. од.), .
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-ї фабрики до j-го замовника . Оскільки транспортна задача за умовою є збалансованою, закритою , то математична модель задачі матиме вигляд
Економічний зміст записаних обмежень полягає ось у чому: уся вироблена на фабриках продукція має вивозитися до замовників повністю.Аналогічні обмеження можна записати відносно замовників: продукція, що надходить до споживача, має повністю задовольняти його попит. Математично це записується так:Загальні витрати, пов’язані з виробництвом і транспортуванням продукції, складаються як добуток обсягу перевезеної продукції та питомої вартості перевезень за відповідним маршрутом і за умовою задачі мають бути мінімальними. ТомуZ = 4 ? x11 + 4 ? x12 + 2 ? x13 + 5 ? x14 + 5 ? x21 + 3 ? x22 + x23 + + 2 ? x24 + 2 ? x31 + x32 +4 ? x33 +2 ? x34 ® min.У цілому математичну модель поставленої задачі можна записати так:Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + + 2x31 + x32 +4x33 +2x34 ® min Розв’язування.Розв’язування задачі подамо в таблицях, які назвемо транспортними. Перший опорний план задачі побудуємо методом мінімальної вартості.
Aj Bj ui
B1= 110 B2= 40 B3= 60 B4= 80 A1= 150 4110 4 22     + 540– u1= 5
A2= 60 5 3 1–60 20+ u2= 2
A3= 80 2 140 4 240 u3= 2
vj v1= –1 v2= –1 v3= –1 v4= 0  
Тому Z = 4 ? 110 + 5 ? 40 + 1 ? 60 + 1 ? 40 + 2 ? 40 = 820 ум. од.Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п’яти, а (m + n – 1) = 3 + 4 – 1 = 6. Для подальшого розв’язування задачі необхідно в одну з порожніх клітинок записати «нульове перевезення» так, щоб не порушити опорності плану, тобто можна зайняти будь-яку вільну клітинку, яка не утворює замкненого циклу. Наприклад, заповнимо клітинку А2В4. Тепер перший план транспортної задачі є невиродженим, і його можна перевірити на оптимальність за допомогою методу потенціалів.На основі першої умови оптимальності ui + vj = cij складемо систему рівнянь для визначення потенціалів плану:Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, якщо, наприклад, v4 = 0. Тоді всі інші потенціали однозначно визначаються: u1 = 5, u2 = 2, u3 = 2, v1 = –1, v2 = –1, v3 = –1.Далі згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ? cij (для порожніх клітинок таблиці):А1B2: u1 + v2 = 5 + (–1) = 4 = 4;А1B3: u1 + v3 = 5 + (–1) = 4 > 2;А2B1: u2 + v1 = 2 + (–1) = 1 < 5;А2B2: u2 + v2 = 2 + (–1) = 1 < 3;А3B1: u3 + v1 = 2 + (–1) = 1 < 2;А3B3: u3 + v3 = 2 + (–1) = 1 < 4.Умова оптимальності не виконується для клітинки А1B3. Порушення D13 = (u1 + v3) – c13 = 4 – 2 = 2 записуємо в лівому нижньому кутку відповідної клітинки.Перший опорний план транспортної задачі є неоптимальним. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці.Потрібно заповнити клітинку А1B3, в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B3, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у вільну клітинку А1B3 переносимо менше з чисел хij, які розміщуються в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщуються в клітинках зі знаком «+», та віднімаємо від чисел, що розміщуються в клітинках, позначених знаком «–».У даному випадку , тобто . Виконавши перерозподіл продукції згідно із записаними правилами, дістанемо такі нові значення: клітинка А1B3 — 40 од. продукції, А2B3 – (60 – 40) = 20 од., А2B4 – (0 + 40) = 40 од. Клітинка А1B4, звільняється і в новій таблиці буде порожньою. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписують у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості, тобто дорівнювати (n + m – 1).Отже, другий опорний план транспортної задачі матиме такий вигляд:
Aj Bj ui
B1= 110 B2= 40 B3= 60 B4= 80 A1= 150 4–110 4 240+ 5 u1= 0
A2= 60 5 3 1–20 240+ u2= –1
A3= 80 21   + 140 4 240– u3= –1
vj v1= 4 v2= –2 v3= 2 v4= 3  
Тому Z2 = 4 ? 110 + 2 ? 40 + 1 ? 20 + 2 ? 40 + 1 ? 40 + 2 ? 40 =740 ум. од.Новий план знову перевіряємо на оптимальність, тобто повторюємо описані раніше дії. Другий план транспортної задачі також неоптимальний (порушення для клітинки А3B1). За допомогою побудованого циклу виконаємо перехід до третього опорного плану транспортної задачі і дістанемо таку таблицю:
Aj Bj ui
B1= 110 B2= 40 B3= 60 B4= 80 A1= 150 490 4 260 5 u1= 2
A2= 60 5 3 1 260 u2= 0
A3= 80 220 140 4 220 u3= 0
vj v1= 2 v2= 1 v3= 0 v4= 2  
Тому Z3 = 4 ? 90 + 2 ? 60 + 2 ? 60 + 2 ? 20 + 1 ? 40 + 2 ? 20 =720 ум. од.Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний. Тому;За оптимальним планом перевезень перший замовник отримує 90 тис. од. продукції з першої фабрики та 20 тис. од. — з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис. од. продукції з третьої фабрики і т. д. При цьому загальна вартість виробництва та перевезення всієї продукції є найменшою і становить 720 ум. од
ЗАДАЧА №2
Побудувати двоїсту задачу до заданої задачі лінійного програмування.


Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція Z мінімізується і в системі обмежень є нерівності, то вони мають бути виду «». Тому друге обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

Двоїста задача:



Оскільки третє обмеження початкової задачі є рівнянням, то відповідна йому змінна двоїстої задачі може набувати як додатного, так і від’ємного значення.
БИЛЕТ№2
ЗАДАЧА №1
Фірмаспеціалізується на виробництвіофіснихмеблів, зокрема вона випускає два видизбірнихкнижковихполиць — А та В. Полиціобохвидіввиготовляють на верстатах 1 та 2. Тривалістьобробки деталей однієїполицікожноїмоделі подано в табл. (2.4).
Таблиця 2.4
ТРИВАЛІСТЬ ВИГОТОВЛЕННЯ КНИЖКОВИХ ПОЛИЦЬ
Верстат Тривалістьобробкиполицімоделі, хв. Ресурс робочого часу верстатів, год.на тиждень
А В 1 30 15 40
2 12 26 36
Прибутокфірмивідреалізаціїоднієїполицімоделі Адорівнює 50 у. о., а моделі В — 30 у. о. Вивчення ринку збуту показало, щотижневий попит на книжковіполицімоделі А ніколи не перевищуєпопиту на модель В більш як на 30 одиниць, а продаж полицьмоделі В не перевищує 80 одиниць на тиждень.
Необхідновизначитиобсягивиробництвакнижковихполицьцихдвох моделей, щомаксимізуютьприбутокфірми. Для цьогослідпобудуватиекономіко-математичну модель поставленоїзадачі та розв’язатиїїграфічно.
Побудоваматематичноїмоделі. Змінними в моделі є тижневіобсягивиробництвакнижковихполиць моделей А та В. Нехай х1 — кількістьполицьмоделі А, виготовленихфірмою за тиждень, а х2 — кількістьполицьмоделі В. Цільовафункціязадачі — максимум прибуткуфірмивідреалізаціїпродукції. Математично вона подається так:
.
Обмеженнязадачівраховуютьтривалістьроботиверстатів 1 та 2 для виготовленняпродукції та попит на полицірізних моделей.
Обмеження на тривалістьроботиверстатів 1 та 2 мають вид:
для верстата 1:
30х1 + 15х2 ≤ 2400 (хв);
для верстата 2:
12х1 + 26х2 ≤ 2160 (хв).
Обмеження на попит записуються так:
х1 – х2 ≤ 30 та х2 ≤ 80.
Загаломекономіко-математичну модель цієїзадачіможназаписати так:
maxZ = 50Х1 + 30Х2 (2.20)
за умов:

Цяекономіко-математична модель є моделлюзадачілінійногопрограмування, щоміститьлишедвізмінні, і тому може бути розв’язанаграфічно.
Розв’язання. Перший крокзгідно з графічним методом полягає в геометричномузображеннідопустимихпланівзадачі, тобто у визначеннітакоїобласті, де водночасвиконуютьсявсіобмеженнямоделі. Замінимо знаки нерівностей на знаки строгих рівностей і побудуємографікивідповіднихпрямих (рис. 2.14). Кожна з побудованихпрямихподіляєплощинусистеми координат на двіпівплощини. Координатиточокоднієї з півплощинзадовольняютьрозглядуванунерівність, а іншої — ні. Щобвизначитинеобхіднупівплощину (на рис. 2.14 їїнапрямпозначенострілкою), потрібновзяти будь-яку точку і перевірити, чизадовольняютьїїкоординатизазначенеобмеження. Якщозадовольняють, то півплощина, в якійміститьсявибрана точка, є геометричнимзображеннямнерівності. Інакше таким зображенням є іншапівплощина.

Рис. 2.14
Умованевід’ємностізміннихх1 ≥ 0, х2 ≥ 0 обмежує область допустимихпланівзадачі першим квадрантом системи координат. Перерізусіхпівплощинвизначає область допустимихпланівзадачі — шестикутникOABCDE. Координатибудь-якоїйого точки задовольняють систему обмеженьзадачі та умовуневід’ємностізмінних. Тому поставлену задачу буде розв’язано, якщо ми зможемовідшукатитаку точку багатокутникаOABCDE, вякійцільовафункціяZнабираєнайбільшогозначення.
Для цьогопобудуємо вектор , координатами якого є коефіцієнти при змінних у цільовійфункціїзадачі. Вектор завждивиходитьіз початку координат і напрямлений до точки з координатами (х1 = с1; х2 = с2). Унашійзадачі вектор . ВінзадаєнапрямзбільшеннязначеньцільовоїфункціїZ, а вектор, протилежниййому, — напрямїхзменшення.
Побудуємолінію, щовідповідає,наприклад, значеннюZ = 0. Це буде пряма 50х1 + 30х2 = 0, яка перпендикулярна до вектора і проходить через початок координат. Оскільки в даномуприкладінеобхідновизначитинайбільшезначенняцільовоїфункції, то пересуватимемопряму 50х1 + 30х2 = 0 паралельносамійсобізгідно з напрямом вектора доти, доки не визначимо вершину багатокутника, яка відповідає оптимальному плану задачі.
Із рис. 2.14 видно, щоостанньоюспільною точкою прямоїцільовоїфункції та багатокутникаOABCDE є точка С. Координатицієї точки є оптимальним планом задачі, тобтотакимиобсягамивиробництвакнижковихполицьвидів А та В, щозабезпечують максимум прибуткувідїхреалізації за даних умов.
Координати точки С є розв’язкомсистемирівнянь (2.17) і (2.18):

звідсимаємо: х1 = 50; х2 = 60.
Отже, Х* = (50; 60);
Цеозначає, що коли фірмащотижнявиготовлятиме 50 збірнихкнижковихполицьмоделі А та 60 — моделі В, то вона отримаємаксимальнийприбуток — 4300 у. о. Цепотребуватимеповноговикористаннятижневихресурсівробочого часу верстатів 1 та 2.
ЗАДАЧА №2
Однорідний вантаж, зосереджений у m постачальників в обсягах ai () необхідно поставити n споживачам в обсягах bj (). Відомі сij ;) – вартості перевезення одиниці вантажу від кожного i-го постачальника до кожного j-го споживача. Необхідно скласти такий план перевезень, при якому запаси усіх постачальників вивозяться повністю й сумарні витрати на перевезення усього вантажу мінімальні. Побудувати опорний план транспортної задачі методами мінімальної вартості, північно-західного кута.
a = (30; 50; 20);
b = (15; 15; 40; 30);

Розв’язування.Розв’язування задачі подамо в таблицях, які назвемо транспортними. Опорний план задачі побудуємо методом мінімальної вартості.
Aj Bj
B1= 15 B2= 15 B3=40 B4= 30
A1= 30 115 8 215 3
A2= 50 4
7 5
20 130
A3= 20 5 315 4
5 4
Опорний план задачі побудуємо методом північно-західного кута.
Aj Bj
B1= 15 B2= 15 B3=40 B4= 30
A1= 30 115
8
15 2 3
A2= 50 4
7 5
40 110
A3= 20 5
3 4
420
БИЛЕТ№3
ЗАДАЧА №1
Однорідний вантаж, зосереджений у m постачальників в обсягах ai () необхідно поставити n споживачам в обсягах bj (). Відомі сij ;) – вартості перевезення одиниці вантажу від кожного i-го постачальника до кожного j-го споживача. Необхідно скласти такий план перевезень, при якому запаси усіх постачальників вивозяться повністю й сумарні витрати на перевезення усього вантажу мінімальні. Побудувати опорний план транспортної задачі методами мінімальної вартості, північно-західного кута.
a = (40; 30; 35); b = (20; 34; 16; 10; 25);

Розв’язування.Розв’язування задачі подамо в таблицях, які назвемо транспортними. Опорний план задачі побудуємо методом мінімальної вартості.
Aj Bj
B1= 20 B2= 34 B3=16 B4= 10 B5= 25
A1= 40 2
6
5 3 4
10 8
25
A2= 30 1
20 5
10 6 9 7
A3= 35 3
4
19 1
16 6 10
Опорний план задачі побудуємо методом північно-західного кута.
Aj Bj
B1= 20 B2= 34 B3=16 B4= 10 B5= 25
A1= 40 2
20 6
20 3 4 8
A2= 30 1
5
14 6
16 9 7
A3= 35 3
4 1 6
10 10
25
ЗАДАЧА №2
Побудувати двоїсту задачу до заданої задачі лінійного програмування. Визначити оптимальні плани прямої та двоїстої задач.


Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція Z мінімізується і в системі обмежень є нерівності, то вони мають бути виду «». Тому перше обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

Двоїста задача:



Двойственная задача линейного программирования.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = 2x1 + 3x2 при следующих условиях-ограничений.
2x1 + 3x2≤30
x1 + 2x2≥10
x1 - x2≥0
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.
2x1 + 3x2 + 1x3 + 0x4 + 0x5 = 30
1x1 + 2x2 + 0x3-1x4 + 0x5 = 10
1x1-1x2 + 0x3 + 0x4-1x5 = 0
Введем искусственные переменные x: в 2-м равенстве вводим переменную x6; в 3-м равенстве вводим переменную x7;
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 30
1x1 + 2x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 10
1x1-1x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 0
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = 2x1+3x2+Mx6+Mx7 → min
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 10-x1-2x2+x4
x7 = 0-x1+x2+x5
которые подставим в целевую функцию:
F(X) = 2x1 + 3x2 + M(10-x1-2x2+x4) + M(0-x1+x2+x5) → min
или
F(X) = (2-2M)x1+(3-1M)x2+(1M)x4+(1M)x5+(10M) → min
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
2 3 1 0 0 0 0
1 2 0 -1 0 1 0
1 -1 0 0 -1 0 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x6, x7,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,30,0,0,10,0)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7
x3 30 2 3 1 0 0 0 0
x6 10 1 2 0 -1 0 1 0
x7 0 1 -1 0 0 -1 0 1
F(X0) 10M -2+2M -3+1M 0 -1M -1M 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (30 : 2 , 10 : 1 , 0 : 1 ) = 0
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x3 30 2 3 1 0 0 0 0 15
x6 10 1 2 0 -1 0 1 0 10
x7 0 1 -1 0 0 -1 0 1 0
F(X1) 10M -2+2M -3+1M 0 -1M -1M 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x1 .
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x 1 x 2 x 3 x 4 x 5 x 6 x 7
30-(0 • 2):1 2-(1 • 2):1 3-(-1 • 2):1 1-(0 • 2):1 0-(0 • 2):1 0-(-1 • 2):1 0-(0 • 2):1 0-(1 • 2):1
10-(0 • 1):1 1-(1 • 1):1 2-(-1 • 1):1 0-(0 • 1):1 -1-(0 • 1):1 0-(-1 • 1):1 1-(0 • 1):1 0-(1 • 1):1
0 : 1 1 : 1 -1 : 1 0 : 1 0 : 1 -1 : 1 0 : 1 1 : 1
(0)-(0 • (-2+2M)):1 (-2+2M)-(1 • (-2+2M)):1 (-3+1M)-(-1 • (-2+2M)):1 (0)-(0 • (-2+2M)):1 (-1M)-(0 • (-2+2M)):1 (-1M)-(-1 • (-2+2M)):1 (0)-(0 • (-2+2M)):1 (0)-(1 • (-2+2M)):1

Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7
x3 30 0 5 1 0 2 0 -2
x6 10 0 3 0 -1 1 1 -1
x1 0 1 -1 0 0 -1 0 1
F(X1) 10M 0 -5+3M 0 -1M -2+1M 0 2-2M
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (30 : 5 , 10 : 3 , - ) = 31/3
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 min
x3 30 0 5 1 0 2 0 -2 6
x6 10 0 3 0 -1 1 1 -1 31/3
x1 0 1 -1 0 0 -1 0 1 -
F(X2) 10M 0 -5+3M 0 -1M -2+1M 0 2-2M 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x2 .
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B x 1 x 2 x 3 x 4 x 5 x 6 x 7
30-(10 • 5):3 0-(0 • 5):3 5-(3 • 5):3 1-(0 • 5):3 0-(-1 • 5):3 2-(1 • 5):3 0-(1 • 5):3 -2-(-1 • 5):3
10 : 3 0 : 3 3 : 3 0 : 3 -1 : 3 1 : 3 1 : 3 -1 : 3
0-(10 • -1):3 1-(0 • -1):3 -1-(3 • -1):3 0-(0 • -1):3 0-(-1 • -1):3 -1-(1 • -1):3 0-(1 • -1):3 1-(-1 • -1):3
(2-2M)-(10 • (-5+3M)):3 (0)-(0 • (-5+3M)):3 (-5+3M)-(3 • (-5+3M)):3 (0)-(0 • (-5+3M)):3 (-1M)-(-1 • (-5+3M)):3 (-2+1M)-(1 • (-5+3M)):3 (0)-(1 • (-5+3M)):3 (2-2M)-(-1 • (-5+3M)):3

Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7
x3 131/3 0 0 1 12/3 1/3 -12/3 -1/3
x2 31/3 0 1 0 -1/3 1/3 1/3 -1/3
x1 31/3 1 0 0 -1/3 -2/3 1/3 2/3
F(X2) 162/3 0 0 0 -12/3 -1/3 12/3-1M 1/3-1M
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5 x6 x7
x3 131/3 0 0 1 12/3 1/3 -12/3 -1/3
x2 31/3 0 1 0 -1/3 1/3 1/3 -1/3
x1 31/3 1 0 0 -1/3 -2/3 1/3 2/3
F(X3) 162/3 0 0 0 -12/3 -1/3 12/3-1M 1/3-1M
Оптимальный план можно записать так:
x3 = 131/3
x2 = 31/3
x1 = 31/3
F(X) = 3•31/3 + 2•31/3 = 162/3
Составим двойственную задачу к прямой задаче.
2y1 + y2 + y3≤2
3y1 + 2y2 - y3≤3
30y1 + 10y2 → max
y1 ≤ 0
y2 ≥ 0
y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
EQ A = (A3, A2, A1, ) = \b\bc\| (\a \al \co3 \hs3 (1;3;2;0;2;1;0;-1;1))
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
EQ D = A\s\up5(-1) = \b\bc\| (\a \al \co3 \hs3 (1;-5/3;-1/3;0;1/3;-1/3;0;1/3;2/3))
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
EQ (0, 3, 2) x \b\bc\| (\a \al \co3 \hs3 (1;-5/3;-1/3;0;1/3;-1/3;0;1/3;2/3)) = (0;5/3;1/3)
Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 12/3
y3 = 1/3
Z(Y) = 30*0+10*12/3+0*1/3 = 162/3
БИЛЕТ№4
ЗАДАЧА №1
Фирма имеет возможность рекламировать свою продукцию, используя местные радио- и телевизионную сети. Затраты на рекламу в бюджете фирмы ограничены величиной 1000$ в месяц. Каждая минута радиорекламы обходится в 5$, а каждая минута телерекламы - в 100$. Фирма хотела бы использовать радиосеть, по крайней мере, в два раза чаще, чем сеть телевидения, но при этом фирма решила, что время радиорекламы не должно превышать двух часов. Опыт прошлых лет показал, что объем сбыта, который обеспечивает каждая минута телерекламы, в 25 раз больше сбыта, обеспечиваемого одной минутой радиорекламы. Определите оптимальное распределение финансовых средств, ежемесячно отпускаемых на рекламу, между радио- и телерекламой. Решение: Обозначим за хТ - количество финансовых средств, отпускаемых на телерекламу, а за хР - количество финансовых средств, отпускаемых на радиорекламу. Сразу же можем записать одно ограничение на общее количество средств, отпускаемых на рекламу: Количество минут, используемых для рекламы на радио, будет вычисляться следующим обра зом: , а количество минут, используемых для рекламы на телевидении : Для простоты будем считать, что время на рекламу можно покупать посекундно. Условие использования радиосети по крайней мере в два раза чаще, чем сеть телевидения, запишется следующим ограничением: Решение о том, что время радиорекламы не должно превышать двух часов, запишется в виде: А теперь запишем целевую функцию. По условию задачи мы должны найти оптимальное значение распределения финансовых средств, чтобы эффективность от рекламы была максимальной. Если эффективность одной минуты радиорекламы обозначить за единицу, то эффективность одной минуты телерекламы будет равна двадцатипяти. Получим следующую функцию: Из условия задачи естественно вытекают ещё два ограничения: Сведем все ограничения и целевую функцию в одну систему: Приведем систему к стандартному виду и учтем тот факт, что симплекс-метод используется для системы, которую надо минимизировать. Возьмем в качестве свободных переменных хТ и хР, а в качестве базисных примем z1, z2 и z3, умножив при этом второе ограничение на -1. Составим начальную симплекс-таблицу и решим систему. Таким образом, получили, что на радиорекламу надо тратить 90,90$, а на телерекламу - 909,09$, что в минутах составляет на радио - 18,18 минуты, а на телевидении - 9,9 минуты. Тот же результат можно получить и графически. Точка А соответствует оптимуму системы уравнений. Теперь перейдем от прямой задачи к двойственной. Обозначим переменные двойственной задачи за y1, y2, y3, т. е. количество переменных равно количеству ограничений в прямой задаче. При этом переменные двойственной задачи считаются неограниченными по знаку. Поставим каждому ограничению прямой задачи переменную из двойственной. Теперь составим целевую функцию двойственной задачи. Значения при переменных в целевой функции берутся из правых частей ограничений прямой задачи, при этом рядом каким-либо значением ставится та переменная, которая соответствует данному ограничению. Направление улучшения целевой функции двойственной задачи противоположно направлению улучшения целевой функции прямой задачи. Получим: Теперь каждому ограничению двойственной задачи поставим в соответствие переменную прямой задачи. Т. е. будем считать, что первому ограничению двойственной задачи соответствует, например, переменная хР из прямой задачи. Получим следующее ограничение: Обратим внимание на то обстоятельство, что в правой части ограничения стоит значение при хР из целевой функции прямой задачи. Таким же образом составим остальные ограничения для двойственной задачи, которым будут соответствовать переменные хТ, z1, z2, z3 из прямой задачи. Необходимо отметить тот факт, что порядок выбора переменных прямой задачи для составления ограничений двойственной произволен и не влияет на решение задачи, а будет влиять лишь на расположения ограничений в задаче. Собрав все полученные ограничения, мы можем записать: Из третьего, четвертого и пятого ограничения видно, что последнее ограничение избыточно. Избавившись от избыточности, получим следующий вид двойственной задачи: Теперь эту задачу можно решать как прямую, т.е. сначала ее необходимо перевести в задачу стандартного вида, затем построить начальную симплекс-таблицу и решить задачу симплекс-методом. Решение: Приведем задачу к стандартному виду: Решим систему симплекс-методом. Возьмем в качестве базисных переменных переменные y3 и -y2. Выведем y3 из целевой функции и y2 из первого ограничения. Для этого выразим y2 из второго ограничения, подставим его в первое. Затем из первого уравнения выразим y3, и подставим в целевую функцию. В итоге получим: Получаем следующее оптимальное решение двойственной задачи: Далее будет показано, что между прямой и двойственной задачами существует тесная взаимосвязь. Фактически, имея оптимальную симплекс-таблицу одной задачи, можно получить оптимальное решение другой, не производя громоздких вычислений и не используя симплекс-метод. Заинтересованность в определении оптимального решения прямой задачи путем решения двойственной к ней задачи обусловлена тем, что вычисления, необходимые для решения двойственной задачи, могут оказаться менее сложными, чем для прямой задачи. Напомним, что трудоемкость вычислений при решении задач ЛП в большей степени зависит от числа ограничений, чем от количества переменных. Поэтому, если в двойственной задаче ограничений меньше, чем в прямой, как правило, целесообразнее решать двойственную задачу и полученный результат использовать для нахождения оптимального решения прямой задачи. Оптимальное решение прямой задачи можно получить непосредственно из симплекс-таблицы для двойственной задачи, если воспользоваться следующим уравнением: Покажем, что оптимальное решение прямой задачи в свою очередь так же непосредственно определяется из симплекс-таблицы для оптимального решения двойственной задачи. Заметим, что переменные xP и хТ связаны с первым и вторым ограничениями двойственной задачи соответственно и, следовательно, с искусственными переменными u1 и u2. (**) Следовательно, Таким образом, получим тот же результат, который приведен в симплекс-таблице для оптимального решения прямой задачи. Анализ сопоставления результатов, полученных при решении прямой и двойственной задачи, позволяет сформулировать интересный вывод. На итерации, приводящей к оптимуму, Это равенство справедливо всегда и фактически соответствует оптимальным значениям переменных обеих задач.
ЗАДАЧА №2
Для плану визначити, чи він є оптимальним для наступної задачі (застосовуючи теореми двоїстості й не розв’язуючи задачі симплексним методом):


Розв’язання. Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках:
1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.
2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.
3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості.
Запишемо двоїсту задачу до прямої задачі лінійного програмування:
;

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

Три обмеження виконуються, і тому є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = -2*3-0+1+3 = -2.
Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 3 > 0; x3 = 1 > 0; x4 = 3 > 0 то згідно з другою частиною другої теореми двоїстості можна записати обмеження як рівняння і визначити у1 у2 у3:

Підставимо ці значення в друге обмеження системи двоїстої задачі:
-;
.
F = 2*-0,66+6*-0,33+2*0,66 = -2 =Z
Для визначених значень це обмеження виконується, і тому відповідний план у = (-0,66; -0,33;0,66) є допустимим планом двоїстої задачі. Внаслідок цього наше допущення, що є оптимальним планом прямої задачі, виявилося вірним.
БИЛЕТ№5
ЗАДАЧА №1
ЗАДАЧА №2
Для плану визначити, чи він є оптимальним для наступної задачі (застосовуючи теореми двоїстості й не розв’язуючи задачі симплексним методом):


Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках:
1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.
2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.
3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості.
Запишемо двоїсту задачу до прямої задачі лінійного програмування:
;

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

Три обмеження виконуються, і тому є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 2*3-0+1*4-6*3 = -8.
Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 3 > 0; x3 = 1 > 0; x4 = 3 > 0 то згідно з другою частиною другої теореми двоїстості можна записати обмеження як рівняння і визначити у1 у2 у3:

Підставимо ці значення в друге обмеження системи двоїстої задачі:
-;
.
План опт.
F = 15*0-4*2=-8 =Z
Для визначених значень це обмеження виконується, і тому відповідний план у = (2; 0; 2) є допустимим планом двоїстої задачі. Внаслідок цього наше допущення, що є оптимальним планом прямої задачі, виявилося вірним.
БИЛЕТ№6
ЗАДАЧА №1
ЗАДАЧА №2
Підприємство виготовляє продукцію видів А, В і С, для чого використовує три види ресурсів І, II, III. Норми витрат усіх ресурсів на одиницю кожної продукції та обсяги ресурсів на підприємстві наведено в табл.1. Відома ціна одиниці продукції кожного виду: А - 10 ум.од., В -14 ум.од. і С - 12 ум.од. Визначити план виробництва продукції, що забезпечує підприємству найбільший доход.
Вид ресурсу Норма витрат на одиницю продукції за видами Запас ресурсу
А В С І
II
III 4
3
1 2
1
2 1
3
5 180
210
244
Остання симплекс-таблиця, що містить оптимальний план задачі, має такий вигляд
Базис Сб А0 9 10 16 0 0 0
X1 X2 X3 X4 X5 X6
X2
X5
X3 14
0
12 82
80
16 19/8
23/8
-3/4 1
0
0 0
0
1 5/8
1/8
-1/4 0
1
0 -1/8
-5/8
1/4
1340 57/4 0 0 23/4 0 5/4
З наведеної останньої симплексної таблиці початкової задачі запишіть оптимальні планиі ; визначте дефіцитні й недефіцитні ресурси, рентабельну та збиткову продукцію.
Розв’язання
Мат. Модель має вигляд:


Оптимальный план можно записать так:
x2 = 82
x5 = 80
x3 = 16
Х0 =(0;82;16;0;80)
F(X) = 14•82 + 12•16 = 1340
Составим двойственную задачу к прямой задаче.
4y1 + 3y2 + y3≥10
2y1 + y2 + 2y3≥14
y1 + 3y2 + 5y3≥12
180y1 + 210y2 + 244y3 → min
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
EQ A = (A2, A5, A3, ) = \b\bc\| (\a \al \co3 \hs3 (2;0;1;1;1;3;2;0;5))
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
EQ D = A\s\up5(-1) = \b\bc\| (\a \al \co3 \hs3 (5/8;0;-1/8;1/8;1;-5/8;-1/4;0;1/4))
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
EQ (14, 0, 12) x \b\bc\| (\a \al \co3 \hs3 (5/8;0;-1/8;1/8;1;-5/8;-1/4;0;1/4)) = (23/4;0;5/4)
Оптимальный план двойственной задачи равен:
y1 = 53/4
y2 = 0
y3 = 11/4
Y0 = ( 23/4 ; 0 ; 5/4)
Z(Y) = 180*53/4+210*0+244*11/4 = 1340
Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
4*0 + 2*82 + 1*16 = 180 = 180
3*0 + 1*82 + 3*16 = 130 < 210
1*0 + 2*82 + 5*16 = 244 = 244
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y2 = 0.
Неиспользованный экономический резерв ресурса 2 составляет 80 (210-130).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3>0).
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
Обоснование эффективности оптимального плана. ( рентабельность)
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
4*53/4 + 3*0 + 1*11/4 = 241/4 > 10
2*53/4 + 1*0 + 2*11/4 = 14 = 14
1*53/4 + 3*0 + 5*11/4 = 12 = 12
1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x1 = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (241/4 - 10 = 141/4) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).
3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x3>0).
БИЛЕТ№7
ЗАДАЧА №1
ЗАДАЧА №2
Визначити точку та характер умовного екстремуму функції за методом множників Лагранжа.
,
.
Z = 2x1^2 -4x1 +2 + 3x2^2 -18x2 + 27
Запишемо функцію Лаграyжа:

Візьмемо частинні похідні і прирівняємо їх до нуля:

З цієї системи рівнянь визначаємо координати сідлових точок.
Тобто отримали сідловy точкy:

Перевіримо за допомогою достатньої умови існування екстремуму сідлову точку .
Матриця Гессе має такий вигляд:

= - ( 0 + 0 + 0 - 4 – 0 – 6) = 10
10 > 0 => Сідлова точка, точка min
БИЛЕТ№8
ЗАДАЧА №1
ЗАДАЧА №2
Визначити точку та характер умовного екстремуму функції за методом множників Лагранжа.
,

Запишемо функцію Лаграyжа:

Візьмемо частинні похідні і прирівняємо їх до нуля:

З цієї системи рівнянь визначаємо координати сідлових точок.
Тобто отримали сідловy точкy:

Перевіримо за допомогою достатньої умови існування екстремуму сідлову точку .
Матриця Гессе має такий вигляд:

= - ( 0 +0+0+64-0 – 0 ) = -64
-64 < 0 => Сідлова точка, точка max

= - ( 0 +0+0+16-0 – 0 ) = -16
-16 < 0 => Сідлова точка, точка max
Ответ: Сідлова точка , точка max
БИЛЕТ№9
ЗАДАЧА №1
Сільськогосподарське підприємство задумало створити сушильний цех на виробничій площі 190м2, маючи для цього 100 тис.грн. і можливість придбати устаткування двох типів А і В. Техніко-економічну інформацію про ці два види устаткування подано в таблиці:
Техніко-економічний показник Устаткування Ресурс
А В Вартість, тис. грн. 25 10 100
Необхідна виробнича площа, м2 40 20 190
Потужність, тис. грн./рік 350 150
Розв'язування. Нехай і — кількість комплектів устатку вання відповідно типу А і В.
Запишемо економіко-математичну модель:

і цілі.
Розв'язуємо задачу, нехтуючи умовою цілочисловості. Остання симплексна таблиця набере вигляду:
План 350 150 0 0

350 1 1 0
150 0 1
1475 0 0 10
Значення другої змінної є дробовим числом, що не задовольняє початкові умови задачі. Побудуємо для другого рядка наведеної симплексної таблиці додаткове обмеження виду


Оскільки то додаткове обмеження набирає вигляду

Зведемо його до канонічної форми та введемо штучну змінну:

Приєднавши здобуте обмеження до останньої симплексної таблиці з умовно-оптимальним планом, дістанемо:
План 350 150 0 0 0 М

350 1 1 0 0 0
150 0 1 0 0
М 0 0 1 1
1475 0 0 10 0 0
М 0 0 М М М 0
Розв'язуючи наведену задачу, остаточно знаходимо цілочисловий оптимальний план:
.
ЗАДАЧА №2
Визначити точку та характер умовного екстремуму функції за методом множників Лагранжа.
,
.
Запишемо функцію Лаграyжа:

Візьмемо частинні похідні і прирівняємо їх до нуля:

З цієї системи рівнянь визначаємо координати сідлових точок.
Тобто отримали сідловy точкy:

Перевіримо за допомогою достатньої умови існування екстремуму сідлову точку .
Матриця Гессе має такий вигляд:

= - ( 0 + 0 + 0 - 36 – 0 – 8) = 44
44 > 0 => Сідлова точка, точка min
БИЛЕТ№10
ЗАДАЧА №1
Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.
Розв’язання. Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними та . Маємо модель цієї задачі:

;
, — цілі числа.
У результаті розв’язування задачі будь-яким з вищенаведених методів отримаємо оптимальний план: , . Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох вагою по 24 кг.
ЗАДАЧА №2
До заданоїзадачілінійногопрограмуваннязаписатидвоїсту задачу. Розв’язавшидвоїсту задачу графічно, визначитиоптимальний план прямоїзадачі.
minZ = x1 + 2x2 + 2x3;

Розв’язання. За відповідними правилами побудуємодвоїсту задачу:
mахF = y1 + 4y2;

Зауважимо, щозадачінесиметричні, і тому змінна у1, щовідповідаєпершомурівнянню в системіобмеженьпрямоїзадачі, можемати будь-який знак, а змінна у2 — лишеневід’ємна.
Двоїста задача маєдвізмінні, а отже, їїможнарозв’язатиграфічно (рис. 3.2).

Рис. 3.2
НайбільшогозначенняцільовафункціядвоїстоїзадачіFдосягає в точціВбагатокутникаABCD. Їїкоординативизначиморозв’язаннямсистемирівнянь:

Отже, Y* = (– 2/3; 4/3); mахF = 1 х (– 2/3) + 4 х 4/3 = 14/3.
Оптимальний план прямоїзадачівизначимо за допомогоюспіввідношеньдругоїтеоремидвоїстості.
ПідставимоY* у систему обмеженьдвоїстоїзадачі і з’ясуємо, як виконуютьсяобмеженняцієїзадачі:

Оскільки перше обмеження для оптимального плану двоїстоїзадачівиконується як строга нерівність, то висновуємо, що перша зміннапрямоїзадачідорівнюватиме нулю х1 = 0 (перша частинадругоїтеоремидвоїстості).
Теперпроаналізуємооптимальний план двоїстоїзадачі. Оскільки друга компонента плану у2 = 4/3 додатна, то друге обмеженняпрямоїзадачі для Х*виконуватиметься як строгерівняння (друга частинадругоїтеоремидвоїстості).
Об’єднуючиздобутуінформацію, можназаписати систему обмеженьпрямоїзадачі як систему двохрівнянь, в якійх1 = 0, та визначитирештузмінних:

тобтоХ* = (0; 5/3; 2/3), minZ = 1 х 0 + 2 х 5/3 + 2 х 2/3 = 14/3.
УмоваminZ = maxF = 14/3 виконується, і тому Х* = (0; 5/3; 2/3); Y* = (– 2/3; 4/3) є оптимальними планами відповіднопрямої та двоїстої задач.
БИЛЕТ№11
ЗАДАЧА №1
На основі умовно-оптимального плану цілочисельної задачі побудувати допоміжне обмеження Гоморі, приєднати його до умовно-оптимального плану, показаного у наведений нижче таблиці, і знайти цілі значення змінних задачі лінійного програмування
І Базис Сб А0 1 -1 3 4 2
А1 А2 А3 А4 А5
1 Х1 1 14/3 1 -2/3 0 5/3 1/3
2 Х3 3 11/3 0 1/3 1 7/3 1
47/3 0 4/3 0 14/3 11/3
Значення першої та третьої змінних є дробовими числами, що не задовольняє початкові умови задачі. Побудуємо для першого рядка наведеної симплексної таблиці додаткове обмеження виду :
.
Оскільки , , , і ,то додаткове обмеження набуває вигляду:
.

І Базис Сб А0 1 -1 3 4 2 0 А1 А2 А3 А4 А5 А6 1 Х1 1 14/3 1 -2/3 0 5/3 1/3 0 14/5
2 Х3 3 11/3 0 1/3 1 7/3 1 0 11/7
3 Х6 0 2/3 0 1/3 0 2/3 1/3 1 2
47/3 0 4/3 0 14/3 11/3 0 0 - 4 - 7 11 - І Базис Сб А0 1 -1 3 4 2 0 А1 А2 А3 А4 А5 А6 1 Х1 1 6 1 0 0 3 1 2 2 Х3 3 3 0 0 0 5/3 1/3 -1 3 Х2 -1 2 0 1 0 2 1 3 -8 0 0 0 2 7/3 -4 Розв’язавши наведену задачу, знаходимо цілочисловий оптимальний план:
ЗАДАЧА №2
Побудувати двоїсту задачу до заданої задачі лінійного програмування.


Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція Z максимізується і в системі обмежень є нерівності, то вони мають бути виду «». Тому перше обмеження задачі необхідно помножити на (–1). При цьому знак нерівності зміниться на протилежний. Отримаємо:

Двоїста задача:



Оскільки третє обмеження початкової задачі є рівнянням, то відповідна йому змінна двоїстої задачі може набувати як додатного, так і від’ємного значення.
БИЛЕТ№12
ЗАДАЧА №1
На основі умовно-оптимального плану цілочисельної задачі побудувати допоміжне обмеження Гоморі, приєднати його до умовно-оптимального плану, показаного у наведений нижче таблиці, і знайти цілі значення змінних задачі лінійного програмування
І Базис Сб А0 -4 1 2 0 3
А1 А2 А3 А4 А5
1 Х1 -4 7/2 1 -5/2 0 5/2 -3/2
2 Х3 2 5/2 0 1/2 1 31/2 11/2
-9 0 10 0 21 14
Значення першої та третьої змінних є дробовими числами, що не задовольняє початкові умови задачі. Побудуємо для першого рядка наведеної симплексної таблиці додаткове обмеження виду :
Наприклад, для ,;
для , .
.
Оскільки , , , і ,то додаткове обмеження набуває вигляду:
.

І Базис Сб А0 -4 1 2 0 3 0 А1 А2 А3 А4 А5 А6 1 Х1 -4 7/2 1 -5/2 0 5/2 -3/2 0 2 Х3 2 5/2 0 1/2 1 31/2 11/2 0 3 Х6 0 1/2 0 1/2 0 1/2 1/2 1 -9 0 10 0 21 14 0 0 - 5 - 10,5 7 - І Базис Сб А0 1 -1 3 4 2 0 А1 А2 А3 А4 А5 А6 1 Х1 -4 6 1 0 0 5 1 5 2 Х3 2 2 0 0 1 15 5 -1 3 Х2 1 1 0 1 0 1 1 1 -19 0 0 0 11 4 -5 Розв’язавши наведену задачу, знаходимо цілочисловий оптимальний план:
ЗАДАЧА №2
Побудувати двоїсту задачу до заданої задачі лінійного програмування.


Розв’язання. Пряму задачу зведемо до стандартного вигляду. Оскільки цільова функція Z максимізується і в системі обмежень є нерівності, то вони мають бути виду «».
Двоїста задача:



Оскільки третє обмеження початкової задачі є рівнянням, то відповідна йому змінна двоїстої задачі може набувати як додатного, так і від’ємного значення.
БИЛЕТ №14
Задача 1
Фірма має 1 млн грн обігових коштів. Відомі витрати грошей у кожному місяці, а також обов’язкові залишки обігових коштів на кінець кожного місяця. Також передбачається, що для успішного функціонування фірма витрачатиме значно меншу суму, ніж 1 млн грн. Отже, решту коштів можна надавати у кредит. Необхідно визначити оптимальний розподіл обігових коштів протягом кварталу для досягнення максимального прибутку за процентними ставками, якщо відомі витрати та потреби в резервах:
1.01 —31.01: витрати — 80 000 грн; необхідний запас на 31.01 — 300 000 грн;
1.02 —28.02: витрати — 30 000 грн; необхідний запас на 28.02 — 200 000 грн;
1.03 —31.03: витрати — 50 000 грн; необхідний запас на 31.03 — 190 000 грн.
Кредит терміном на 1 місяць дає 2 % прибутку, терміном на 2 місяці — 5 %, а терміном на 3 місяці — 8 %.
Вважатимемо, що кредити надаються першого числа кожного місяця і погашаються також першого числа відповідного місяця.
Побудова економіко-математичної моделі.
Кредити терміном на один місяць можна надавати кожного місяця протягом кварталу, тому позначимо через х11 суму кредиту, що надано на один місяць з 1.01, аналогічно х12,х13 — суми одномісячних кредитів, що надані відповідно в другому та у третьому місяцях.
Кредити терміном на два місяці протягом першого кварталу можна надавати лише в першому і другому місяцях, тому позначимо через х21 суму кредиту, що надано на два місяці в січні, х22 — суму кредиту, що надана в лютому на два місяці. Нарешті, кредит на три місяці можна надати лише один раз із 1.01, його позначимо через х31.
Розглянемо ситуацію на початку першого місяця кварталу: початкова сума 1 млн грн витрачатиметься на вкладення коштів у всі види кредитів, потреби в обігових коштах для господарської діяльності фірми становитимуть 80 000 грн, а на кінець місяця фірма бажає мати резерв обсягом 300 000 грн. Отже, використання коштів у січні можна описати у моделі так:
.
Наявні кошти в кінці місяця (окрім резерву) визначаються за формулою:

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

за умов:


Задача 2
F(X) = x1 - 3x2 + x3
x1 + 2x2 - x3≥2
2x2 + 4x3≤7
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≤) вводим базисную переменную x5.
1x1 + 2x2-1x3-1x4 + 0x5 = 2
0x1 + 2x2 + 4x3 + 0x4 + 1x5 = 7
Введем искусственные переменные x: в 1-м равенстве вводим переменную x6;
1x1 + 2x2-1x3-1x4 + 0x5 + 1x6 = 2
0x1 + 2x2 + 4x3 + 0x4 + 1x5 + 0x6 = 7
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = x1-3x2+x3+Mx6 → min
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 min
x6 2 1 2 -1 -1 0 1 1
x5 7 0 2 4 0 1 0 31/2
F(X1) 2M -1+1M 3+2M -1-1M -1M 0 0 0
Базис B x1 x2 x3 x4 x5 x6 min
x2 1 1/2 1 -1/2 -1/2 0 1/2 -
x5 5 -1 0 5 1 1 -1 5
F(X2) -3 -21/2 0 1/2 11/2 0 -11/2-1M 0
Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5 x6
x2 31/2 0 1 2 0 1/2 0
x4 5 -1 0 5 1 1 -1
F(X3) -101/2 -1 0 -7 0 -11/2 -1M
Оптимальный план можно записать так:
x2 = 31/2
x4 = 5
F(X) = -3•31/2 = -101/2
БИЛЕТ №15
Задача 1
F(X) = - x1 - x2 + 3x3
x1 - x2 + 2x3≤2
2x1 + x2 + 3x3≤8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5.
1x1-1x2 + 2x3 + 1x4 + 0x5 = 2
2x1 + 1x2 + 3x3 + 0x4 + 1x5 = 8
Базис B x1 x2 x3 x4 x5
x4 2 1 -1 2 1 0
x5 8 2 1 3 0 1
F(X0) 0 1 1 -3 0 0
Базис B x1 x2 x3 x4 x5 min
x4 2 1 -1 2 1 0 1
x5 8 2 1 3 0 1 22/3
F(X1) 0 1 1 -3 0 0 0
Базис B x1 x2 x3 x4 x5 min
x3 1 1/2 -1/2 1 1/2 0 -
x5 5 1/2 21/2 0 -11/2 1 2
F(X2) 3 21/2 -1/2 0 11/2 0 0
Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5
x3 2 3/5 0 1 1/5 1/5
x2 2 1/5 1 0 -3/5 2/5
F(X3) 4 23/5 0 0 11/5 1/5
Оптимальный план можно записать так:
x3 = 2
x2 = 2
F(X) = 3•2 + -1•2 = 4
Білет №20
1.Стандартом передбачається, що октанове число бензину А-76 має бути не нижчим 76, а вміст сірки – не більшим, ніж 0,3 %. Для виготовлення такого бензину на заводі використовуються чотири компоненти. Дані про обсяги запасів компонентів, які змішуються, їх вартості, октанові числа та вміст сірки наведені в табл. 1:
Таблиця 1 – Техніко-економічні показники компонент бензину
Показник Компонента бензину
№ 1 № 2 № 3 №4
Октанове число 68 72 80 90
Вміст сірки, % 0,35 0,35 0,30 0,20
Наявний обсяг, т 700 600 500 300
Вартість, грош. од./т 40 45 60 90
Необхідно визначити, скільки тонн кожного компонента потрібно використати для того, щоб отримати 1000 т бензину А-76 з мінімальною собівартістю.
Побудувати економіко-математичну модель задачі.
Побудова економіко-математичної моделі.
Позначимо через хj кількість j-го компонента в суміші (т), j = 1,2,3,4.
Перше обмеження забезпечує потрібне значення октанового числа в суміші:
.
Вміст сірки в суміші має не перевищувати 0,3 %:
,
а загальна маса утвореної суміші має дорівнювати 1000 т:
.
Використання кожного компонента має не перевищувати його наявного обсягу:

Собівартість суміші визначається за формулою:
.
Загалом, економіко-математична модель задачі має вигляд:

за умов:

.
Розв’язавши цю задачу симплексним методом отримуємо оптимальний план: х1=0, х2=500, х3=500, х4=0. Цільова функція дорівнює:
min F = 40*0+45*500+60*500+90*0 = 52500 (грош. од.)
Отже, для того, щоб отримати 1000 т бензину А-76 з мінімальною собівартістю у 52500 грош. од. потрібно використати 500 тонн 2 компоненту та 500 тонн третього компоненту.
2. Симплексним методом знайти розв’язок задачі лінійного програмування
2577465566674000
Розв’язання
Застосуємо алгоритм симплекс-методу:
1. min Z = – x1 -2x2 + 2x3 + 0x4;

2. Векторна форма запису системи обмежень має вигляд:
,
де , , , , .
У цій задачі х3 та х4 — базисні змінні, а х1, х2 — вільні. Нехай х1 = х2 = 0, тоді х3 = 10; х4 = 2.
Перший опорний план задачі:
X0 = (0; 0; 10; 2), Z0 = 20.
4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці:
Базис Сбаз План -1 -2 2 0
х1 х2 х3 х4 х3 2 10 2 1 1 0 5
х4 0 2 1 -1 0 1 2
Zj – сj 0 20 5 4 0 0  
24765010922000х3 2 6 0 3 1 -2 2
3838575696595002136140-60515500х1 -1 2 1 -1 0 1 -2
Zj – сj 0 10 0 9 0 -5  
х2 -2 2 0 1 0,33 -0,67 -3
2476501060450039325553175000х1 -1 4 1 0 0,33 0,33 12
Zj – сj 0 -8 0 0 -3 1  
х2 -2 10 2 1 1 0  
х4 0 12 3 0 1 1  
Zj – сj 0 -20 -3 0 -4 0  
Оскільки всі , то з останньої симплекс-таблиці оптимальним планом задачі є вектор:
Х* = (0; 10; 0; 12; 0),

1884045-234823000Білет №21
1. Учасник експедиції складає рюкзак, і йому необхідно розв’язати питання про те, які взяти продукти. У розпорядженні є м’ясо, борошно, сухе молоко, цукор. У рюкзаку залишилось для продуктів лише 45 дм3 об’єму, до того ж необхідно, щоб загальна маса продуктів не перевищувала 35 кг. Лікар експедиції рекомендував, щоб м’яса (за масою) було більше, ніж борошна принаймні удвічі, борошна не менше, ніж молока, а молока хоча б у вісім разів більше, ніж цукру. Скільки і яких продуктів потрібно покласти в рюкзак, щоб сумарна калорійність продуктів була найбільшою? Характеристики продуктів наведені в табл. 1.
Таблиця 1 – Характеристики продуктів
Показники Продукт
м’ясо борошно молоко цукор
Об’єм (дм3/кг) 1 1,5 2 1
Калорійність (ккал/кг) 1500 5000 5000 4000
Побудувати економіко-математичну модель задачі.
Побудова економіко-математичної моделі.
Позначимо через х1, х2, х3, х4 масу (в кг) м’яса, борошна, молока і цукру відповідно.
Сумарна маса продуктів має не перевищувати 35 кг:
,
а об’єм, який вони мають займати, — не більше 45 дм3:
.
Крім того, мають виконуватися співвідношення стосовно пропорцій за масою продуктів:
а) м’яса принаймні удвічі більше, ніж борошна, отже:
;
б) борошна не менше, ніж молока: ;
в) молока хоча б у вісім разів більше, ніж цукру: .
Калорійність всього набору продуктів можна визначити так:
.
Отже, економіко-математична модель задачі має вигляд:

за умов:

.
Розв’язуючи задачу отримуємо такий оптимальний план: х1=16, х2=8, х3=8, х4=1. Цільова функція дорівнює:
max F = 1500*16+5000*8+5000*8+4000*1 = 108000 (ккал/кг)
Отже, для того, щоб сумарна калорійність продуктів була найбільшою, складала 108000 ккал/кг до рюкзаку треба покласти 16 кг мяса, 8 кг борошна, 8 л молока та 1 кг цукру.
2. Симплексним методом знайти розв’язок задачі лінійного програмування

Розв’язання
Застосуємо алгоритм симплекс-методу:
1. min Z = x1 +5x2 + 3x3 -Мx4;

2. Векторна форма запису системи обмежень має вигляд:
,
де , , , , .
У цій задачі х3 та х4 — базисні змінні, а х1, х2 — вільні. Нехай х1 = х2 = 0, тоді х3 = 3; х4 = 4.
Перший опорний план задачі:
X0 = (0; 0; 3; 4), Z0 = 9-4М.
4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці: Zj – сj
0Сбаз
Базис Сбаз План 1 5 3 -М
х1 х2 х3 х4 Х4 -М 4 2 1 0 1 2
Х3 3 3 1 2 1 0 3
Zj – сj 0 -4М -2М -М 0 0  
24765010922000х1 1 2 1 1/2 0 1/2 1925955-605155002136140-79184500х3 3 1 0 1,5 1 1/2 Zj – сj 0 5 0 0 0 2  
Оскільки всі , то з останньої симплекс-таблиці оптимальним планом задачі є вектор:
Х* = (2; 0; 3; 0),

Білет №22
Фермерське господарство спеціалізується на вирощуванні озимої пшениці і має три ділянки землі площею S1 = 40 га, S2 = 90 га, S3 = 55 га. Враховуючи наявну кількість посівного матеріалу, є можливість засіяти всю площу озимою пшеницею трьох сортів. Кількість пшениці сорту «Миронівська-808» забезпечить посів на 80 га, «Безоста-1» – 60 га та «Одеська-51» – 45 га. Урожайність сорту «Миронівська-808» на даних ділянках становить відповідно 41 ц/га, 40 ц/га, 46 ц/га. Аналогічно для сорту «Безоста-1» маємо: 38 ц/га, 41 ц/га, 45 ц/га, а для «Одеської-51» – 30 ц/га, 28 ц/га, 40 ц/га. Необхідно розподілити посівний матеріал за земельними ділянками так, щоб отримати максимальний урожай (валовий збір) озимої пшениці. Побудувати економіко-математичну модель задачі.
Побудова економіко-математичної моделі.
Позначимо через хij площу (га) і-ої земельної ділянки, що буде засіяна j-м сортом озимої пшениці (сорти «Миронівська-808», «Безоста-1», «Одеська-51» відповідатимуть номерам 1, 2, 3), (і = 1, 2, 3), (j = 1, 2, 3).
Тоді використання земельних угідь описуватиме така система обмежень:
;
;
.
Використання посівного матеріалу формально можна описати так:
;
;
.
Валовий збір зерна розраховується як сума добутків урожайностей відповідних сортів пшениці на їх посівні площі, тобто:

Отже, економіко-математична модель задачі загалом буде мати вигляд:

за умов:

Оптимальний розподіл посівного матеріалу за земельними ділянками:
Земельна ділянка x1 x2 x3 площа, га
Сорт насіння c1 40 0 0 40
c2 30 60 0 90
c3 10 0 45 55
посівний матеріал, га 80 60 45  
Цільова функція, тобто максимальний урожай (валовий збір) озимої пшениці за даного розподілу посівного матеріалу за ділянками дорівнює:
max F = 40*41+30*40+10*46+60*41+45*40 = 7560 (ц/га)
2. Побудувати двоїсту задачу до заданої задачі лінійного програмування. Визначити оптимальні плани прямої та двоїстої задач.

Розв’язання:
Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак «». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:


Тепер за відповідними правилами складемо двоїсту задачу:


Оскільки записані задачі симетричні, то будь-яку з них можна розв’язати симплекс-методом. Наприклад, визначимо спочатку оптимальний план прямої задачі. Для цього застосуємо алгоритм симплекс-методу.
1. max Z = – 30x1 + 10x2 + 0x3 + 0x4+0 x5 +10;

2. Векторна форма запису системи обмежень має вигляд:
,
де , , , , , .
У системі векторів для утворення початкового одиничного базису відсутній один вектор. Тому введемо штучну змінну в перше обмеження.
3. Розширена задача лінійного програмування буде такою:
max Z = – 30x1 + 10x2 + 0x3 + 0x4+0 x5 – Мx6+10;

У цій задачі х6 та х5 — базисні змінні, а х1, х2, х3 х4— вільні. Нехай х1 = х2 = х3 = х4= 0, тоді х6 = -2; х5 = -3.
Перший опорний план задачі:
X0 = (0; 0; 0; 0; -3; -2), Z0 = – M+10.
4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці:
Білет №23
1. Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два види збірних книжкових полиць – А та В. Полиці обох видів виготовляють на верстатах 1 та 2. Тривалість обробки деталей однієї полиці кожної моделі подано в табл. 1.
Таблиця 1 – Тривалість виготовлення книжкових полиць
Верстат Тривалість обробки полиці моделі, хв. Ресурс робочого часу верстатів, год. на тиждень
А В 1 30 15 40
2 12 26 36
Прибуток фірми від реалізації однієї полиці моделі А дорівнює 50 у. о., а моделі В – 30 у. о. Вивчення ринку збуту показало, що тижневий попит на книжкові полиці моделі А ніколи не перевищує попиту на модель В більш як на 30 одиниць, а продаж полиць моделі В не перевищує 80 одиниць на тиждень.
Необхідно визначити обсяги виробництва книжкових полиць цих двох моделей, що максимізують прибуток фірми. Для цього слід побудувати економіко-математичну модель поставленої задачі.
Побудувати економіко-математичну модель задачі.
Побудова математичної моделі. Змінними в моделі є тижневі обсяги виробництва книжкових полиць моделей А та В. Нехай х1 — кількість полиць моделі А, виготовлених фірмою за тиждень, а х2 — кількість полиць моделі В. Цільова функція задачі — максимум прибутку фірми від реалізації продукції. Математично вона подається так:
.
Обмеження задачі враховують тривалість роботи верстатів 1 та 2 для виготовлення продукції та попит на полиці різних моделей.
Обмеження на тривалість роботи верстатів 1 та 2 мають вид:
для верстата 1:
30х1 + 15х2 ≤ 2400 (хв);
для верстата 2:
12х1 + 26х2 ≤ 2160 (хв).
Обмеження на попит записуються так:
х1 – х2 ≤ 30 та х2 ≤ 80.
Загалом економіко-математичну модель цієї задачі можна записати так:
max Z = 50х1 + 30х2
за умов:

Ця економіко-математична модель є моделлю задачі лінійного програмування, що містить лише дві змінні, і тому може бути розв’язана графічно.
Розв’язання. Перший крок згідно з графічним методом полягає в геометричному зображенні допустимих планів задачі, тобто у визначенні такої області, де водночас виконуються всі обмеження моделі. Замінимо знаки нерівностей на знаки строгих рівностей і побудуємо графіки відповідних прямих. Кожна з побудованих прямих поділяє площину системи координат на дві півплощини. Координати точок однієї з півплощин задовольняють розглядувану нерівність, а іншої — ні. Щоб визначити необхідну півплощину, потрібно взяти будь-яку точку і перевірити, чи задовольняють її координати зазначене обмеження. Якщо задовольняють, то півплощина, в якій міститься вибрана точка, є геометричним зображенням нерівності. Інакше таким зображенням є інша півплощина.

Умова невід’ємності змінних х1 ≥ 0, х2 ≥ 0 обмежує область допустимих планів задачі першим квадрантом системи координат. Переріз усіх півплощин визначає область допустимих планів задачі — шестикутник OABCDE. Координати будь-якої його точки задовольняють систему обмежень задачі та умову невід’ємності змінних. Тому поставлену задачу буде розв’язано, якщо ми зможемо відшукати таку точку багатокутника OABCDE, в якій цільова функція Z набирає найбільшого значення.
Для цього побудуємо вектор , координатами якого є коефіцієнти при змінних у цільовій функції задачі. Вектор завжди виходить із початку координат і напрямлений до точки з координатами (х1 = с1; х2 = с2). У нашій задачі вектор . Він задає напрям збільшення значень цільової функції Z, а вектор, протилежний йому, — напрям їх зменшення.
Побудуємо лінію, що відповідає, наприклад, значенню Z = 0. Це буде пряма 50х1 + 30х2 = 0, яка перпендикулярна до вектора і проходить через початок координат. Оскільки в даному прикладі необхідно визначити найбільше значення цільової функції, то пересуватимемо пряму 50х1 + 30х2 = 0 паралельно самій собі згідно з напрямом вектора доти, доки не визначимо вершину багатокутника, яка відповідає оптимальному плану задачі.
Із рис. 2.14 видно, що останньою спільною точкою прямої цільової функції та багатокутника OABCDE є точка С. Координати цієї точки є оптимальним планом задачі, тобто такими обсягами виробництва книжкових полиць видів А та В, що забезпечують максимум прибутку від їх реалізації за даних умов.
Координати точки С є розв’язком системи рівнянь:

звідси маємо: х1 = 50; х2 = 60.
Отже, Х* = (50; 60);
Це означає, що коли фірма щотижня виготовлятиме 50 збірних книжкових полиць моделі А та 60 — моделі В, то вона отримає максимальний прибуток — 4300 у. о. Це потребуватиме повного використання тижневих ресурсів робочого часу верстатів 1 та 2.
2. Розв’язати задачу опуклого програмування.

2253615444500
.
Розв’язання. Оскільки цільова функція виражена сумою лінійної функції та квадратичної форми , а система обмежень є лінійною, то маємо задачу квадратичного програмування.
Визначимо вид квадратичної форми , для чого відшукаємо корені характеристичного рівняння, що відповідає матриці, складеній з коефіцієнтів при змінних даної функції:
.
Характеристичним рівнянням для матриці С буде:


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

Вводимо додаткові змінні для зведення нерівностей до рівнянь:

Для зведення задачі до канонічної форми помножимо кожне рівняння на (–1):

Очевидно, що в даному разі штучні змінні необхідно вводити в перші три рівняння. У четвертому та п’ятому рівняннях базисними змінними будуть ,. Маємо таку задачу лінійного програмування:
,

.
Розв’язавши її симплексним методом, отримаємо:
Білет №24
1. Для невеликої птахоферми потрібно розрахувати оптимальний кормовий раціон на 1000 курчат, яких вирощують з 4-х до 8-тижневого віку. Нехтуючи тим, що потижневі витрати кормів для курчат залежать від їхнього віку, вважатимемо, що за 4 тижні курча споживає не менше 500 г суміші. Крім цього, кормовий раціон курчат має задовольняти певні вимоги щодо поживності. Сформулюємо ці вимоги у спрощеному вигляді, беручи до уваги лише дві поживні речовини: білок і клітковину, що містяться у кормах двох видів – зерні та соєвих бобах. Вміст поживних речовин у кожному кормі та їх вартість маємо у табл. 1.
Таблиця 1 – Поживність та вартість кормів
Корм Вміст поживних речовин в 1 кг корму, % Вартість 1 кг корму, у. о.
білку клітковини Зерно 10 2 0,40
Соєві боби 50 8 0,90
Готова кормова суміш має містити не менше як 20 % білка і не більш як 5 % клітковини. Визначити масу кожного з двох видів кормів, що утворюють кормову суміш мінімальної вартості, водночас задовольняючи вимоги до загальної маси кормової суміші та її поживності. Для цього слід побудувати економіко-математичну модель поставленої задачі.
Побудова економіко-математичної моделі. Нехай х1 — маса зерна, а х2 — соєвих бобів (в кг) у готовій кормовій суміші.
Загальна кількість суміші х1 + х2 має становити понад 500 кг, тобто
х1 + х2 ≥ 500.
Розглянемо обмеження щодо поживності кормової суміші.
Суміш має містити не менш як 20 % білка:
10х1 + 50х2 ≥ 20 (х1 + х2),
а також не більше як 5 % клітковини:
2х1 + 8х2 ≤ 5 (х1 + х2).
Загалом математична модель задачі оптимізації кормового раціону має такий вигляд:
min Z = 0,40х1 + 0,90х2(2.26)
за умов:

(2.30)
Розв’язання. Графічну інтерпретацію задачі подано на рисунку:

Множина допустимих її розв’язків необмежена. Для вектора = (0,4; 0,9) можна змінити масштаб, наприклад, = (200; 450). Найменшого значення цільова функція Z досягає в точці А, що лежить на перетині граничних прямих, які відповідають обмеженням (2.27) та (2.28). Визначимо її координати:

Отже, Х* = (375; 125); min Z = 0,4 · 375 + 0,9 · 125 = 262,5.
Згідно з відшуканим оптимальним планом задачі для того, щоб отримати 500 кг кормової суміші мінімальної вартості (262,50 у. о.), потрібно взяти 375 кг зерна та 125 кг соєвих бобів. За такого співвідношення компонентів кормової суміші вимоги до її поживності виконуватимуться:
0,10 · 375 + 0,50 · 125 = 100 кг білка, що становить рівно 20 % загальної маси суміші;
0,02 · 375 + 0,08 · 125 = 17,5 кг клітковини в кормовій суміші, що становить 3,5% її маси і не перевищує 5%.
2. На підприємстві встановлено нове обладнання. Залежність продуктивності цього обладнання від часу користування ним підприємством, а також залежність витрат на його утримання та ремонт при різному часі його використання наведені в таблиці.
Показник Час, протягом якого використовується обладнання
0 1 2 3 4 5
Річний випуск продукції у вартісному вираженні (тис. грн) 80 75 65 60 60 55
Щорічні витрати, пов’язані з утриманням та ремонтом обладнання (тис. грн) 20 25 30 35 45 55
Знаючи, що витрати, які пов’язані з купівлею та установкою нового обладнання, ідентичного з встановленим, складають 40 тис. грн., а обладнання, що замінюється, списується, скласти такий план заміни обладнання протягом 5 років, при якому загальний прибуток за даний період часу максимальний.
Білет №25
1. Продукція чотирьох видів А, В, С і D проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду наведена в табл. 1.
Таблиця 1 – Тривалість обробки продукції на верстатах, год.
Верстат Тривалість обробки одиниці продукції
А В С D
1 2 3 4 2
2 3 2 1 2
Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-години становить 10 грн для верстата 1 і 15 грн – для верстата 2. Тривалість використання верстатів обмежена: для верстата 1 вона становить 450 машино-годин, а для верстата 2 – 380 машино-годин.
Ціна одиниці продукції видів А, В, С і D дорівнює відповідно 73, 70, 55 та 45 грн.
Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний прибуток.
Розв’язати задачу лінійного програмування симплексним методом.
Побудова математичної моделі.
Нехай Хj— план виробництва продукціїу-го виду, де у може набувати значень від 1 до 4.
Умовами задачі будуть обмеження на час використання верстатів для виробництва продукції всіх видів:
для верстата 1 (машино-год);
для верстата 2
Цільова функція задачі визначається як загальний чистий прибуток від реалізації готової продукції і складається з різниці між ціною та собівартістю виготовлення продукції кожного виду:

Отже, математична модель поставленої задачі має такий вигляд:

Розв'язування. Розв'яжемо задачу симплекс-методом згідно з розглянутим алгоритмом.
Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х5 та х6.
249679-796600
Ці додаткові змінні за економічним змістом означають можливий, але не використаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:

Канонічну систему обмежень задачі запишемо у векторній формі:

де
Оскільки вектори А5 и А6 та одиничні та лінійно незалежні, саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі х5 та х6 , що відповідають одиничним базисним векторам, називають базисними, а решту вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:

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

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

Складемо симплексну таблицю для першого опорного плану задачі.

У цій задачі в оцінковому рядку дві оцінки та суперечать умові оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі.
Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення і вибираємо найменше значення. Згідно з даними симплексної таблиці бачимо, що min
і тому з базису виключаємо змінну х5, а число а12= 3 називатимемо розв'язувальним елементом. Подальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана—Гаусса.
Друга симплексна таблиця має такий вигляд:

Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності для другого опорного плану. Цей план також неоптимальний, оскільки . Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:

В оцінковому рядку третьої симплексної таблиці немає від'ємних чисел, тобто всі і задовольняють умову оптимальності. Це означає, Що знайдено оптимальний план задачі:

2. Визначити, чи є оптимальними такі плани сформульованої задачі лінійного програмування:
min Z = 12x1 – 4x2 + 2x3;

а) Х = (8/7; 3/7; 0);
б) Х = (0; 1/5; 8/5);
в) Х = (1/3; 0; 1/3).
Розв’язання. Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та, допускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій будуть однаковими за величиною, то припущення правильне. Протилежне можна висновувати в таких випадках:
1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.
2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.
3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює значенню функції Z, тобто не виконується умова першої теореми двоїстості.
Запишемо двоїсту задачу до прямої задачі лінійного програмування:
max F = y1 + 2y2;


Перевіримо запропоновані плани на оптимальність.
1. Х = (8/7; 3/7; 0). Підставимо його в систему обмежень прямої задачі:

Обидва обмеження виконуються, і тому Х = (8/7; 3/7; 0) є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової функції: Z = 12 х 8/7 – 4 х 3/7 + 2 х 0 = 12.
Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x1 = 8/7 > 0; x2 = 3/7 > 0, то згідно з другою частиною другої теореми двоїстості можна записати перше та друге обмеження як рівняння і визначити у1 та у2:

Підставимо ці значення в третє обмеження системи двоїстої задачі:
;
.
Для визначених значень у1 = 4; у2 = 4 це обмеження не виконується, і тому відповідний план у = (4; 4) є недопустимим планом двоїстої задачі. Внаслідок цього наше допущення, що Х = (8/7; 3/7; 0) є оптимальним планом прямої задачі, виявилося помилковим.
2. Х = (0; 1/5; 8/5). Підставимо цей план у систему обмежень прямої задачі:

План допустимий, і для нього Z = 12 х 0 – 4 х 1/5 + 2 х 8/5 = 12/5.
Визначимо відповідний план двоїстої задачі. Оскільки компоненти x2 та x3 додатні, то друге і третє обмеження двоїстої задачі можна записати як рівняння:

Перевіримо, чи виконується перше обмеження двоїстої задачі для визначених значень у1 та у2: 2 х 8/5 + 2/5 = 18/5 < 12. Отже, перше обмеження виконується, і тому у = (8/5; 2/5) є допустимим планом двоїстої задачі. Для нього
F = 8/5 + 2 х 2/5 = 12/5 = Z.
З огляду на викладене можна висновувати, що Y* = (8/5; 2/5) є оптимальним планом двоїстої задачі, а X* = (0; 1/5; 8/5) — оптимальним планом прямої задачі.
Наше припущення відносно запропонованого плану виявилося правильним.
3. Х = (1/3; 0; 1/3). Для цього плану обмеження прямої задачі виконуються так:

Оскільки Х = (1/3; 0; 1/3) є недопустимим планом, то він не може бути також оптимальним планом прямої задачі.
Отже, перевірка запропонованих планів на оптимальність дала такі результати: а) ні; б) так, Х* = (0; 1/5; 8/5), min Z = 12/5; в) ні.

Приложенные файлы

  • docx 18451183
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий