Реферат: Задачі математичного програмування

Завдання 2

Записати двоїстузадачу до поставленої задачі лінійного програмування. Розв’язати одну із задачсимплексним методом і визначити оптимальний план іншої задачі. Оптимальнірезультати перевірити графічно.

/>

/>

Розв’язок

Розв’яжемо задачулінійного програмування симплексним методом.

Визначимомінімальне значення цільової функції F(X) = 4x1+2x2 при наступнихумовах-обмежень.

x1-x2≤4

x1+3x2≤6

x1+2x2≥2

Для побудовипершого опорного плану систему нерівностей приведемо до системи рівнянь шляхомвведення додаткових змінних.

Оскільки маємозмішані умови-обмеження, то введемо штучні змінні x.

1x1-1x2 + 1x3 +0x4 + 0x5 = 4

1x1 + 3x2 + 0x3+ 1x4 + 0x5 = 6

1x1 + 2x2 + 0x3+ 0x4-1x5 = 2

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

F(X)= 4x1+2x2 — Mx6 => max

Вважаючи, щовільні змінні рівні 0, отримаємо перший опорний план:

План Базис В x1 x2 x3 x4 x5 х6 х3 4 1 -1 1 x4 6 1 3 1 х6 2 1 2 -1 1 Індексний рядок F(X0)

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

План Базис В x1 x2 x3 x4 x5 x6 min 1 x3 4 1 -1 1 x4 6 1 3 1 2 x6 2 1 2 -1 1 1 Індексний рядок F(X1)

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

План Базис В x1 x2 x3 x4 x5 x6 min 2 x3 5 1.5 1 -0.5 0.5 3.33 х4 3 -0.5 1 1.5 -1.5 x2 1 0.5 1 -0.5 0.5 2 Індексний рядок F(X2)

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

План  Базис  В  x1  x2  x3  x4  x5  x6  min 3  x3 2 -3 1 1 -1 2    X4 4 1 1 1 -1 4    X1 2 1 2 -1 1  Індексний рядок  F(X3) План Базис В x1 x2 x3 x4 x5 x6 min 4 х5 2 -3 1 1 -1 X4 2 4 -1 1 0.5 X1 4 1 -1 1 Індексний рядок F(X4) План Базис В x1 x2 x3 x4 x5 х6 5 х5 3.5 0.25 0.75 1 -1 х2 0.5 1 -0.25 0.25 х1 4.5 1 0.75 0.25 Індексний рядок F(X5) /> /> /> /> /> /> /> /> /> /> /> /> /> /> />

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

x5 = 3.5

x2 = 0.5

x1 = 4.5

F(X) = 4*4.5 +2*0.5 = 19

Складемо двоїстузадачу до поставленої задачі лінійного програмування.

y1+y2+y3≥4

-y1+3y2+2y3≥2

4y1+6y2+2y3=> min

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

Рішення двоїстоїзадачі дає оптимальну оцінок ресурсів. Використовуючи останню інтиграцію прямоїзадачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує,що Y = C*A-1.

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

<p/>

Визначившиобернену матрицю А-1 через алгебраїчне доповнення, отримаємо:

<p/>

Як видно із останньогоплану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додатковихзмінних.

Тоді Y = C*A-1 =

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

y1 = 2.5

y2 = 1.5

y3 = 0

Z(Y) =4*2.5+6*1.5+2*0 = 19

Завдання 3

Розвязатитранспортну задачц.

1 2 4 1 5 200 1 2 1 3 1 120 2 1 3 3 1 150 100 90 200 30 80

Розв’язок

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

/>

/>

/>У нашомувипадку робиться це введенням фіктивного постачальника, оскільки />. Зуведенням фіктивного постачальникав транспортній таблиці додатково заявляється n робочих клітинок (додатковийрядок).

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

Занесемовихідні дані у таблицю.