Побудова економіко-математичної моделі

БИЛЕТ№1!!!!!!!!!!!!!!!

ЗАДАЧА №1

Розв’язати наступну задачу: компанія контролює три фабрики А₁, А₂, А₃, здатні виготовляти 150, 60 та 80 тис.од. продукції щотижня. Компанія уклала договір з чотирма замовниками В₁, В₂, В₃, В₄, яким потрібно щотижня відповідно 110, 40, 60 та 80 тис.од. продукції. Вартість виробництва та транспортування 1000 од. продукції замовниками з кожної фабрики наведено в таблиці.

Фабрика	Вартість виробництва і транспортування 1000 од. продукції за замовниками
Фабрика	В₁	В₂	В₃	В₄
А₁	4	4	2	5
А₂	5	3	1	2
А₃	2	1	4	2

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

Відповідь: Z₃ = 720 (ум. од.), .

Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-ї фабрики до j-го замовника . Оскільки транспортна задача за умовою є збалансованою, закритою , то математична модель задачі матиме вигляд

Економічний зміст записаних обмежень полягає ось у чому: уся вироблена на фабриках продукція має вивозитися до замовників повністю.
Аналогічні обмеження можна записати відносно замовників: продукція, що надходить до споживача, має повністю задовольняти його попит. Математично це записується так:

Загальні витрати, пов’язані з виробництвом і транспортуванням продукції, складаються як добуток обсягу перевезеної продукції та питомої вартості перевезень за відповідним маршрутом і за умовою задачі мають бути мінімальними. Тому
Z = 4 x11 + 4 x12 + 2 x13 + 5 x14 + 5x21+3x22 + x23+2x24+2x31+x32+4x3+2 x34®min.
У цілому математичну модель поставленої задачі можна записати так:
Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24+ 2x31+x32+4x33+2x34®min

Розв’язування.Розв’язування задачі подамо в таблицях, які назвемо транспортними. Перший опорний план задачі побудуємо методом мінімальної вартості.

Aj	Bj				ui
Aj	B1= 110	B2= 40	B3= 60	B4= 80	ui
A1= 150	4 110	4	2 2 +	5 40–	u1= 5
A2= 60	5	3	1 –60	2 0+	u2= 2
A3= 80	2	1 40	4	2 40	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
Aj	B1= 110	B2= 40	B3= 60	B4= 80	ui
A1= 150	4 –110	4	2 40+	5	u1= 0
A2= 60	5	3	1 –20	2 40+	u2= –1
A3= 80	2 1 +	1 40	4	2 40–	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
Aj	B1= 110	B2= 40	B3= 60	B4= 80	ui
A1= 150	4 90	4	2 60	5	u1= 2
A2= 60	5	3	1	2 60	u2= 0
A3= 80	2 20	1 40	4	2 20	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 постачальників в обсягах a_i ( ) необхідно поставити n споживачам в обсягах b_j ( ). Відомі с_ij ; ) – вартості перевезення одиниці вантажу від кожного i-го постачальника до кожного j-го споживача. Необхідно скласти такий план перевезень, при якому запаси усіх постачальників вивозяться повністю й сумарні витрати на перевезення усього вантажу мінімальні. Побудувати опорний план транспортної задачі методами мінімальної вартості, північно-західного кута.

a = (30; 50; 20);

b = (15; 15; 40; 30);

Розв’язування.Розв’язування задачі подамо в таблицях, які назвемо транспортними. Опорний план задачі побудуємо методом мінімальної вартості.

Aj	Bj
Aj	B1= 15	B2= 15	B3=40	B4= 30
A1= 30	1 15	8	2 15	3
A2= 50	4	7	5 20	1 30
A3= 20	5	3 15	4 5	4

Опорний план задачі побудуємо методом північно-західного кута.

Aj	Bj
Aj	B1= 15	B2= 15	B3=40	B4= 30
A1= 30	1 15	8 15	2	3
A2= 50	4	7	5 40	1 10
A3= 20	5	3	4	4 20

!!!!!!!!!!!!!!!БИЛЕТ№3!!!!!!!!!!!!!!!!!

ЗАДАЧА №1

a = (40; 30; 35); b = (20; 34; 16; 10; 25);

Розв’язування.Розв’язування задачі подамо в таблицях, які назвемо транспортними. Опорний план задачі побудуємо методом мінімальної вартості.

Aj	Bj
Aj	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
Aj	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) = 2x₁ + 3x₂ при следующих условиях-ограничений.

2x₁ + 3x₂≤30

x₁ + 2x₂≥10

x₁ - x₂≥0

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≥) вводим базисную переменную x₄ со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус.

2x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ = 30

1x₁ + 2x₂ + 0x₃-1x₄ + 0x₅ = 10

1x₁-1x₂ + 0x₃ + 0x₄-1x₅ = 0

Введем искусственные переменные x: в 2-м равенстве вводим переменную x₆; в 3-м равенстве вводим переменную x₇;

2x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ = 30

1x₁ + 2x₂ + 0x₃-1x₄ + 0x₅ + 1x₆ + 0x₇ = 10

1x₁-1x₂ + 0x₃ + 0x₄-1x₅ + 0x₆ + 1x₇ = 0

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = 2x₁+3x₂+Mx₆+Mx₇ → min

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

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.

Из уравнений выражаем искусственные переменные:

x₆ = 10-x₁-2x₂+x₄

x₇ = 0-x₁+x₂+x₅

которые подставим в целевую функцию:

F(X) = 2x₁ + 3x₂ + M(10-x₁-2x₂+x₄) + M(0-x₁+x₂+x₅) → min

или

F(X) = (2-2M)x₁+(3-1M)x₂+(1M)x₄+(1M)x₅+(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

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных:

x₃, x₆, x₇,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,30,0,0,10,0)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₃	30	2	3	1	0	0	0	0
x₆	10	1	2	0	-1	0	1	0
x₇	0	1	-1	0	0	-1	0	1
F(X0)	10M	-2+2M	-3+1M	0	-1M	-1M	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент .

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

min (30 : 2 , 10 : 1 , 0 : 1 ) = 0

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	min
x₃	30	2	3	1	0	0	0	0	15
x₆	10	1	2	0	-1	0	1	0	10
x₇	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 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 1, получена в результате деления всех элементов строки x₇ плана 0 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₁ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₁ и столбец x₁.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x ₁	x ₂	x ₃	x ₄	x ₅	x ₆	x ₇
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	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₃	30	0	5	1	0	2	0	-2
x₆	10	0	3	0	-1	1	1	-1
x₁	0	1	-1	0	0	-1	0	1
F(X1)	10M	0	-5+3M	0	-1M	-2+1M	0	2-2M

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент .

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (30 : 5 , 10 : 3 , - ) = 3¹/₃

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	min
x₃	30	0	5	1	0	2	0	-2	6
x₆	10	0	3	0	-1	1	1	-1	3¹/₃
x₁	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 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₆ плана 1 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x ₁	x ₂	x ₃	x ₄	x ₅	x ₆	x ₇
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	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₃	13¹/₃	0	0	1	1²/₃	¹/₃	-1²/₃	^-1/₃
x₂	3¹/₃	0	1	0	^-1/₃	¹/₃	¹/₃	^-1/₃
x₁	3¹/₃	1	0	0	^-1/₃	^-2/₃	¹/₃	²/₃
F(X2)	16²/₃	0	0	0	-1²/₃	^-1/₃	1²/₃-1M	¹/₃-1M

1. Проверка критерия оптимальности.

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇
x₃	13¹/₃	0	0	1	1²/₃	¹/₃	-1²/₃	^-1/₃
x₂	3¹/₃	0	1	0	^-1/₃	¹/₃	¹/₃	^-1/₃
x₁	3¹/₃	1	0	0	^-1/₃	^-2/₃	¹/₃	²/₃
F(X3)	16²/₃	0	0	0	-1²/₃	^-1/₃	1²/₃-1M	¹/₃-1M

Оптимальный план можно записать так:

x₃ = 13¹/₃

x₂ = 3¹/₃

x₁ = 3¹/₃

F(X) = 3•3¹/₃ + 2•3¹/₃ = 16²/₃

Составим двойственную задачу к прямой задаче.

2y₁ + y₂ + y₃≤2

3y₁ + 2y₂ - y₃≤3

30y₁ + 10y₂ → max

y₁ ≤ 0

y₂ ≥ 0

y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = 1²/₃

y₃ = ¹/₃

Z(Y) = 30*0+10*1²/₃+0*¹/₃ = 16²/₃

!!!!БИЛЕТ№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.

Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x₁ = 3 > 0; x₃ = 1 > 0; x₄ = 3 > 0 то згідно з другою частиною другої теореми двоїстості можна записати обмеження як рівняння і визначити у₁ у₂у₃:

Підставимо ці значення в друге обмеження системи двоїстої задачі:

- ;

F = 2*-0,66+6*-0,33+2*0,66 = -2 =Z

Для визначених значень це обмеження виконується, і тому відповідний план у = (-0,66; -0,33;0,66) є допустимим планом двоїстої задачі. Внаслідок цього наше допущення, що
є оптимальним планом прямої задачі, виявилося вірним.

!!!!!!!!!!!!!БИЛЕТ№5!!!!!!!!!!!!!!!!!!!!!!

ЗАДАЧА №1

ЗАДАЧА №2

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

1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.

2. Якщо визначений план двоїстої задачі недопустимий, тобто не задовольняє всі обмеження двоїстої задачі.

Запишемо двоїсту задачу до прямої задачі лінійного програмування:

;

Перевіримо запропонований план на оптимальність.

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

Підставимо ці значення в друге обмеження системи двоїстої задачі:

- ; .

План опт.

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

Остання симплекс-таблиця, що містить оптимальний план задачі, має такий вигляд

Базис	С_б	А₀	9	10	16	0	0	0
Базис	С_б	А₀	X₁	X₂	X₃	X₄	X₅	X₆
X₂ X₅ X₃	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

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

Розв’язання

Мат. Модель має вигляд:

Оптимальный план можно записать так:

x₂ = 82

x₅ = 80

x₃ = 16

Х0 =(0;82;16;0;80)

F(X) = 14•82 + 12•16 = 1340

Составим двойственную задачу к прямой задаче.

4y₁ + 3y₂ + y₃≥10

2y₁ + y₂ + 2y₃≥14

y₁ + 3y₂ + 5y₃≥12

180y₁ + 210y₂ + 244y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 5³/₄

y₂ = 0

y₃ = 1¹/₄

Y0 = ( 23/4 ; 0 ; 5/4)

Z(Y) = 180*5³/₄+210*0+244*1¹/₄ = 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-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).

2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0.

Неиспользованный экономический резерв ресурса 2 составляет 80 (210-130).

Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₃>0).

Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.

Обоснование эффективности оптимального плана. ( рентабельность)

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

4*5³/₄ + 3*0 + 1*1¹/₄ = 24¹/₄ > 10

2*5³/₄ + 1*0 + 2*1¹/₄ = 14 = 14

1*5³/₄ + 3*0 + 5*1¹/₄ = 12 = 12

1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₁ = 0.

Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.

При этом разница между ценами (24¹/₄ - 10 = 14¹/₄) показывает величину изменения целевой функции F(x) при введении дополнительной единицы x_i.

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).

3-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₃>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м², маючи для цього 100 тис.грн. і можливість придбати устаткування двох типів А і В. Техніко-економічну інформацію про ці два види устаткування подано в таблиці:

Техніко-економічний показник	Устаткування		Ресурс
Техніко-економічний показник	А	В	Ресурс
Вартість, тис. грн.	25	10	100
Необхідна виробнича площа, м²	40	20	190
Потужність, тис. грн./рік	350	150	-

Розв'язування. Нехай і — кількість комплектів устатку вання відповідно типу А і В.

Запишемо економіко-математичну модель:

і - цілі.

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

	План	350	150	0	0
	План
350	1	1	0
150		0	1
	1475	0	0	10

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

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

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

Розв'язуючи наведену задачу, остаточно знаходимо цілочисловий оптимальний план:

ЗАДАЧА №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

На основі умовно-оптимального плану цілочисельної задачі побудувати допоміжне обмеження Гоморі, приєднати його до умовно-оптимального плану, показаного у наведений нижче таблиці, і знайти цілі значення змінних задачі лінійного програмування

І	Базис	С_б	А₀	1	-1	3	4	2
І	Базис	С_б	А₀	А₁	А₂	А₃	А₄	А₅
1	Х₁	1	14/3	1	-2/3	0	5/3	1/3
2	Х₃	3	11/3	0	1/3	1	7/3	1
			47/3	0	4/3	0	14/3	11/3

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

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

І	Базис	С_б	А₀	1	-1	3	4	2	0
І	Базис	С_б	А₀	А₁	А₂	А₃	А₄	А₅	А6
1	Х₁	1	14/3	1	-2/3	0	5/3	1/3	0	14/5
2	Х₃	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	-

І	Базис	С_б	А₀	1	-1	3	4	2	0
І	Базис	С_б	А₀	А₁	А₂	А₃	А₄	А₅	А6
1	Х₁	1	6	1	0	0	3	1	2
2	Х₃	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

І	Базис	С_б	А₀	-4	1	2	0	3
І	Базис	С_б	А₀	А₁	А₂	А₃	А₄	А₅
1	Х₁	-4	7/2	1	-5/2	0	5/2	-3/2
2	Х₃	2	5/2	0	1/2	1	31/2	11/2
			-9	0	10	0	21	14

Наприклад, для , ;

для , .

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

І	Базис	С_б	А₀	-4	1	2	0	3	0
І	Базис	С_б	А₀	А₁	А₂	А₃	А₄	А₅	А6
1	Х₁	-4	7/2	1	-5/2	0	5/2	-3/2	0
2	Х₃	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	-

І	Базис	С_б	А₀	1	-1	3	4	2	0
І	Базис	С_б	А₀	А₁	А₂	А₃	А₄	А₅	А6
1	Х₁	-4	6	1	0	0	5	1	5
2	Х₃	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 %.

Вважатимемо, що кредити надаються першого числа кожного місяця і погашаються також першого числа відповідного місяця.

Побудова економіко-математичної моделі.

Кредити терміном на один місяць можна надавати кожного місяця протягом кварталу, тому позначимо через х₁₁ суму кредиту, що надано на один місяць з 1.01, аналогічно х₁₂,х₁₃ — суми одномісячних кредитів, що надані відповідно в другому та у третьому місяцях.

Кредити терміном на два місяці протягом першого кварталу можна надавати лише в першому і другому місяцях, тому позначимо через х₂₁ суму кредиту, що надано на два місяці в січні, х₂₂ — суму кредиту, що надана в лютому на два місяці. Нарешті, кредит на три місяці можна надати лише один раз із 1.01, його позначимо через х₃₁.

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

Наявні кошти в кінці місяця (окрім резерву) визначаються за формулою:

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

а наприкінці лютого обсяг наявних коштів становитиме:

Аналогічно запишемо використання коштів у березні:

Загальна сума коштів, отриманих як проценти за надані кредити, дорівнюватиме:

Загалом математична модель цієї задачі має вигляд:

за умов:

Задача 2

F(X) = x₁ - 3x₂ + x₃

x₁ + 2x₂ - x₃≥2

2x₂ + 4x₃≤7

В 1-м неравенстве смысла (≥) вводим базисную переменную x₄ со знаком минус. В 2-м неравенстве смысла (≤) вводим базисную переменную x₅.

1x₁ + 2x₂-1x₃-1x₄ + 0x₅ = 2

0x₁ + 2x₂ + 4x₃ + 0x₄ + 1x₅ = 7

Введем искусственные переменные x: в 1-м равенстве вводим переменную x₆;

1x₁ + 2x₂-1x₃-1x₄ + 0x₅ + 1x₆ = 2

0x₁ + 2x₂ + 4x₃ + 0x₄ + 1x₅ + 0x₆ = 7

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = x₁-3x₂+x₃+Mx₆ → min

Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	min
x₆	2	1	2	-1	-1	0	1	1
x₅	7	0	2	4	0	1	0	3¹/₂
F(X1)	2M	-1+1M	3+2M	-1-1M	-1M	0	0	0

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	min
x₂	1	¹/₂	1	^-1/₂	^-1/₂	0	¹/₂	-
x₅	5	-1	0	5	1	1	-1	5
F(X2)	-3	-2¹/₂	0	¹/₂	1¹/₂	0	-1¹/₂-1M	0

Окончательный вариант симплекс-таблицы:

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆
x₂	3¹/₂	0	1	2	0	¹/₂	0
x₄	5	-1	0	5	1	1	-1
F(X3)	-10¹/₂	-1	0	-7	0	-1¹/₂	-1M

Оптимальный план можно записать так:

x₂ = 3¹/₂

x₄ = 5

F(X) = -3•3¹/₂ = -10¹/₂

!!!!!!!!!!!БИЛЕТ №15!!!!!!!!!!!!!!!

Задача 1

F(X) = - x₁ - x₂ + 3x₃

x₁ - x₂ + 2x₃≤2

2x₁ + x₂ + 3x₃≤8

В 1-м неравенстве смысла (≤) вводим базисную переменную x₄. В 2-м неравенстве смысла (≤) вводим базисную переменную x₅.

1x₁-1x₂ + 2x₃ + 1x₄ + 0x₅ = 2

2x₁ + 1x₂ + 3x₃ + 0x₄ + 1x₅ = 8

Базис	B	x₁	x₂	x₃	x₄	x₅
x₄	2	1	-1	2	1	0
x₅	8	2	1	3	0	1
F(X0)	0	1	1	-3	0	0

Базис	B	x₁	x₂	x₃	x₄	x₅	min
x₄	2	1	-1	2	1	0	1
x₅	8	2	1	3	0	1	2²/₃
F(X1)	0	1	1	-3	0	0	0

Базис	B	x₁	x₂	x₃	x₄	x₅	min
x₃	1	¹/₂	^-1/₂	1	¹/₂	0	-
x₅	5	¹/₂	2¹/₂	0	-1¹/₂	1	2
F(X2)	3	2¹/₂	^-1/₂	0	1¹/₂	0	0

Окончательный вариант симплекс-таблицы:

Базис	B	x₁	x₂	x₃	x₄	x₅
x₃	2	³/₅	0	1	¹/₅	¹/₅
x₂	2	¹/₅	1	0	^-3/₅	²/₅
F(X3)	4	2³/₅	0	0	1¹/₅	¹/₅

Оптимальный план можно записать так:

x₃ = 2

x₂ = 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. Симплексним методом знайти розв’язок задачі лінійного програмування

Розв’язання

Застосуємо алгоритм симплекс-методу:

1. min Z = – x₁ -2x₂ + 2x₃ + 0x₄;

2. Векторна форма запису системи обмежень має вигляд:

де , , , , .

У цій задачі х₃ та х₄ — базисні змінні, а х₁, х₂ — вільні. Нехай х₁ = х₂ = 0, тоді х₃ = 10; х₄ = 2.

Перший опорний план задачі:

X₀ = (0; 0; 10; 2), Z₀ = 20.

4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці:

Базис	С_баз		План	-1	-2	2	0	q
Базис	С_баз		План	х1	х2	х3	х4	q
х3	2		10	2	1	1	0	5
х4	0		2	1	-1	0	1	2
Z_j – с_j ³ 0			20	5	4	0	0
х3	2		6	0	3	1	-2	2
х1	-1		2	1	-1	0	1	-2
Z_j – с_j ³ 0			10	0	9	0	-5
х2		-2	2	0	1	0,33	-0,67	-3
х1		-1	4	1	0	0,33	0,33	12
Z_j – с_j ³ 0			-8	0	0	-3	1
х2		-2	10	2	1	1	0
х4		0	12	3	0	1	1
Z_j – с_j ³ 0			-20	-3	0	-4	0

Оскільки всі , то з останньої симплекс-таблиці оптимальним планом задачі є вектор:

Х^* = (0; 10; 0; 12; 0),

!!!!!!!!!!!!! Білет №21!!!!!!!!!!!!!!!

1. Учасник експедиції складає рюкзак, і йому необхідно розв’язати питання про те, які взяти продукти. У розпорядженні є м’ясо, борошно, сухе молоко, цукор. У рюкзаку залишилось для продуктів лише 45 дм3 об’єму, до того ж необхідно, щоб загальна маса продуктів не перевищувала 35 кг. Лікар експедиції рекомендував, щоб м’яса (за масою) було більше, ніж борошна принаймні удвічі, борошна не менше, ніж молока, а молока хоча б у вісім разів більше, ніж цукру. Скільки і яких продуктів потрібно покласти в рюкзак, щоб сумарна калорійність продуктів була найбільшою? Характеристики продуктів наведені в табл. 1.

Таблиця 1 – Характеристики продуктів

Показники	Продукт
Показники	м’ясо	борошно	молоко	цукор
Об’єм (дм³/кг)	1	1,5	2	1
Калорійність (ккал/кг)	1500	5000	5000	4000

Побудувати економіко-математичну модель задачі.

Дата добавления: 2018-04-05; просмотров: 475; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 Следующая ⇒

Мы поможем в написании ваших работ!