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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

Приклад 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. Алгоритм розв’язування задачі

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