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



ЗНАЕТЕ ЛИ ВЫ?

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

Поиск

(1)

(2)

(3)

Тут x 1 i x 2 – площа, відведена під першу і другу культуру відповідно; c1 i c2 – прибуток з 1 гектара культури відповідно першого і другого типу; aij – затрати ресурсів і -го типу на 1 гектар культури j - го типу; bi – кількість виділених ресурсів для і - ої культури.

Приклад

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

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

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

Позначимо x 1 – площа під культурою 1, x 2 – площа під культурою 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. Постановка задачі:

Для відгодівлі тварин фермер використовує чотири види корму P1, P2, P3, P4, кожен з яких містить поживні речовини B1, B2, B3. Добова потреба тварини у поживних речовинах дорівнює b1, b2 i b3 відповідно. Ціна корму становить відповідно c1, c2, c3, c4. Вміст поживних речовин у одиниці маси кожного корму відомий і становить a11, a12, a13, a14, a21, a22, a23, a24, a31, a32, a33, a34 (тут перший індекс позначає номер поживної речовини, а другий – номер корму). Необхідно побудувати харчовий раціон (вказати щоденну кількість кожного корму), вартість якого мінімальна.

 

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

(12)

(13)

(14)

Тут xj – кількість корму j - го типу; cj – ціна корму j - го типу; aij – вміст поживної речовини i – го типу у одиниці маси корму j -ого типу; bi – добова потреба у i –ій поживній речовині.

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

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

  P1 P2 P3 P4 Норма
B1          
B2   - -    
B3          
Ціна          


Поделиться:


Последнее изменение этой страницы: 2016-04-08; просмотров: 193; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.147.126.199 (0.008 с.)