• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Форми запису задач ЛП

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

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

Таблиця 1.1

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

Розв’язок. Складемо математичну модель задачі. Припустимо, що для отримання найбільшого прибутку майстерня виготовить х₁ виробів виду А₁ і виробів виду . Кількість виробів невід’ємна: . Оскільки запаси кожного виду металів і обмежені, то при відомих питомих витратах на одиницю виробу (див. таб. 1.1) змінні х₁ і х₂ повинні задовольняти наступним умовам:

(1.1)

Вартість реалізованих виробів виразимо цільовою функцією .

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

Розглядувана нами задача (приклад 1.1) є так званою задачею ЛП (ЗЛП). (До ЗЛП відносять такі, в яких всі функції і – лінійні відносно змінних. Якщо принаймні одна з функцій або нелінійна, то відповідну задачу називають нелінійною).

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

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

В залежності від виду обмежень і критерію оптимальності розрізняють наступні форми запису ЗЛП:

a) загальна форма;

б) симетрична форма;

в) канонічна форма.

Визначення 1.1. Загальною ЗЛП називають задачу, в якій потрібно знайти найбільше (найменше) значення цільової функції

при обмеженнях

, ,

де – задані дійсні числа.

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

при обмеженнях

.

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

при обмеженнях

, .

З’ясуємо тепер питання про взаємозв’язок між різними формами ЗЛП. Насамперед покажемо, що канонічну задачу можна перевести в симетричну і навпаки. Справді, рівняння рівносильне системі нерівностей

Тому, якщо кожне рівняння канонічної задачі замінити вище наведеною системою нерівностей, то отримуємо ЗЛП в симетричній формі.

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

Отже, якщо кожну нерівність в системі обмежень симетричної задачі замінити рівносильним їй рівнянням, то симетрична задача набуде вигляду канонічної.

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

При необхідності задачу максимізації можна замінити задачею мінімізації і навпаки.

Рис. 1.1

Зауваження 1.1. Як відомо, задача знаходження екстремальних точок функції розв’язується методами диференціального числення, які дозволяють визначати тільки такі екстремальні точки, які знаходяться всередині розглядуваної області, а не на її границі. В ЗЛП оптимальні значення цільової функції досягаються завжди на границі многокутника розв’язків. Тому для дослідження таких задач потрібно використовувати спеціальні математичні методи.

Читайте також:

1. А) Відносини власності і форми господарювання в сільському господарстві
2. А) Заробітна плата її форми та системи.
3. А) Заробітна плата, її форми та системи.
4. А/. Форми здійснення народовладдя та види виборчих систем.
5. Автоматизовані форми та системи обліку.
6. Аграрні реформи та розвиток сільського госпо- дарства в 60-х роках XIX ст. — на початку XX ст.
7. Акредитив та його форми
8. Активні форми участі територіальної громади у вирішенні питань ММС
9. Алгоритм розв’язання задачі
10. Алгоритм розв’язання розподільної задачі
11. Алгоритм розв’язування задачі
12. Алгоритм розв’язування задачі

Переглядів: 1998