Математична модель задачі у загальному вигляді

(1)

(2)

(3)

Тут x ₁ i x ₂ – площа, відведена під першу і другу культуру відповідно; c₁ i c₂ – прибуток з 1 гектара культури відповідно першого і другого типу; a_ij – затрати ресурсів і -го типу на 1 гектар культури j - го типу; b_i – кількість виділених ресурсів для і - ої культури.

Приклад

Таблиця 1. Технологічна матриця (затрати ресурсів на 1 га площі)

Ресурси	Культура 1	Культура 2	Запаси ресурсів
Роб. сила
Фін. ресурси
Рух. склад
Прибуток (тис. грн. з 1 га)

Математична модель задачі 9.4

Позначимо x ₁ – площа під культурою 1, x ₂ – площа під культурою 2. Тоді отримаємо:

(4)

(5)

(6)

Геометричний спосіб розв’язування

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

А лінія 2-а лінія 3-я лінія

Знайдемо координати вершин симплекса. Координати вершин O, A, D вже відомі і становлять: O(0;0), A(0;4), D(6;0). Для знаходження координат вершини B необхідно розв’язати систему двох лінійних рівнянь, які відповідають першій і третій лінії:

В результаті отримаємо B(3.46; 2.62).

Для знаходження координат вершини С необхідно розв’язати систему двох лінійних рівнянь, які відповідають другій і третій лінії:

В результаті отримаємо С(5.40; 1.00).

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

Отримаємо F(O)=0.00; F(A)=4; F(B)=9.54; F(C)=11.8; F(D)=12.00.

Отже оптимальний розв’язок відповідає вершині D симплекса і має вигляд:

Табличний симплекс-метод

Канонічна форма задачі

Введемо нові невід’ємні змінні . Отримаємо систему недоозначених рівнянь (3 рівняння, 5 невідомих).

(7)

(8)

(9)

Складаємо симплекс – таблицю 1

симплекс-таблиця 1

Базис	Ci	P0	P1	P2	P3	P4	P5
P3
P4
P5
D j			-2	-1

Тут - оцінка невідомого

(10)

Вибір розв’язуючого елемента

1. Розв’язуючий елемент повинен бути додатнім!

2. Розв’язуючий стовпець P1 знаходимо з умови min . min (-2;-1)=-2.

3. Розв’язуючий рядок – P4 знаходимо з умови min (P0/aij), тут i – номер розв’язуючого рядка. min (20/2; 30/5; 33/5) = 30/5.

4. Вектор P4 виходить з базису, Вектор P1 входить у базис.

5. Розв’язуючий елемент – число 5 – знаходиться на перетині розв’язуючого рядка P4 і розв’язуючого стовпця P1.

Алгоритм звичайного симплекс-методу

1. Розв’язуючий рядок P4 ділимо на розв’язуючий елемент – число 5;

2. Базисні стовпці P1, P3 i P5 повинні бути одиничними векторами;

3. Усі інші елементи таблиці (стовпці P0, P2, P4 крім рядка P4) перераховуються згідно правила прямокутника:

. (11)

Тут розв’язуючий елемент; елемент, який перераховується.

симплекс-таблиця 2

Базис	Ci	P0	P1	P2	P3	P4	P5
P3				3.8		-0.4
P1				0.6		0.2
P5						-1
				0.2		0.4

4. Оскільки всі ³ 0, отримано оптимальний розв’язок задачі. Оптимальні значення параметрів x3, x1 i x5 знаходимо у стовпчику P0. Невідомі x2 i x4 яких немає у базисі є вільними і дорівнюють нулю. Якби серед оцінок були б від’ємні, довелось би будувати ще одну симплекс таблицю

Відповідь. Оптимальний розподіл земельних ресурсів має вигляд: x1 (площа під першу культуру) = 6 га; x2 (площа під другу культуру) = 0 га; x3 = 8; x4 = 0; x5 = 3; Fmax (прибуток) = 12 тис. грн.

 

Таблиця 2. В а р і а н т и з а в д а н ь д о т е м и 9

варіант	a11	a12	b1	a21	a22	b2	a31	a32	b3	c1	c2

 

 

Тема 10

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

10.1. Завдання. Побудувати математичну модель задачі лінійного програмування (задача на мінімум). Звести задачу до канонічної форми. Розв’язати задачу двоїстим симплекс-методом.

10.2. Постановка задачі:

Для відгодівлі тварин фермер використовує чотири види корму P₁, P₂, P₃, P₄, кожен з яких містить поживні речовини B₁, B₂, B₃. Добова потреба тварини у поживних речовинах дорівнює b₁, b₂ i b₃ відповідно. Ціна корму становить відповідно c₁, c₂, c₃, c₄. Вміст поживних речовин у одиниці маси кожного корму відомий і становить a₁₁, a₁₂, a₁₃, a₁₄, a₂₁, a₂₂, a₂₃, a₂₄, a₃₁, a₃₂, a₃₃, a₃₄ (тут перший індекс позначає номер поживної речовини, а другий – номер корму). Необхідно побудувати харчовий раціон (вказати щоденну кількість кожного корму), вартість якого мінімальна.

 

Математична модель задачі (для загального випадку)

(12)

(13)

(14)

Тут x_j – кількість корму j - го типу; c_j – ціна корму j - го типу; a_ij – вміст поживної речовини i – го типу у одиниці маси корму j -ого типу; b_i – добова потреба у i –ій поживній речовині.

Приклад. Технологічна матриця задачі про оптимальний харчовий раціон

Таблиця 3. Технологічна матриця