Xreferat.com » Рефераты по экономико-математическому моделированию » Стандартна задача лінійного програмування

Стандартна задача лінійного програмування

з одиницею замість розв'язувального елемента.

3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.

4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.

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

Щоб визначити будь-який елемент нової таблиці за цим правилом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами:;

1 — розв'язувальний елемент;

2 — число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати;

3 та 4 — елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.

Необхідний елемент нової симплекс-таблиці визначають так:


Стандартна задача лінійного програмування


Наприклад, визначимо елемент Стандартна задача лінійного програмування, який розміщується в новій таблиці в другому рядку стовпчика «Х4». Складемо умовний прямокутник:


Стандартна задача лінійного програмування


Тоді Стандартна задача лінійного програмування = (3-2-2-2):3 = 2/3. Це значення записуємо в стовпчик «Стандартна задача лінійного програмування» другого рядка другої симплексної таблиці.

Аналогічно розраховують усі елементи нової симплексної таблиці, у тому числі елементи стовпчика «План» та оцінкового рядка. Наявність двох способів визначення оцінок опорного плану (за правилом прямокутника та за відповідною формулою) дає змогу контролювати правильність арифметичних обчислень на кожному кроці симплекс-методу.

Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності Стандартна задача лінійного програмування для другого опорного плану. Цей план також неоптимальний, оскільки Стандартна задача лінійного програмування. Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:


Стандартна задача лінійного програмування


В оцінковому рядку третьої симплексної таблиці немає від'ємних чисел, тобто всі Стандартна задача лінійного програмування і задовольняють умову оптимальності. Це означає, Що знайдено оптимальний план задачі:


Стандартна задача лінійного програмування


Або


Стандартна задача лінійного програмування


Отже, план виробництва продукції, що передбачає випуск 48 одиниць продукції А та 118 од. продукції В, оптимальний і дає найбільший прибуток 1564 дол. При цьому час роботи верстатів використовується повністю (х5 = х6 = 0).

Задачу можна розв'язати симплекс-методом, узявши не три симплексні таблиці, а одну, в якій послідовно записувати всі ітерації.

Задача 2.42.

Розв'язати задачу 2.41 із додатковою умовою: продукція С має виготовлятися в кількості не менш як 9 одиниць.

Розв'язування. Математичну модель сформульованої задачі запишемо так:


Стандартна задача лінійного програмування


Застосовуючи для розв’язування поставленої задачі симплекс-метод, спочатку записуємо систему обмежень у канонічній формі, а далі — у векторній:


Стандартна задача лінійного програмування


Зауважимо, що нерівність типу «>» у рівняння перетворюємо введенням у ліву частину обмеження додаткової змінної зі знаком «-».

Векторна форма запису:


Стандартна задача лінійного програмування

Серед записаних векторів є лише Два одиничні — Стандартна задача лінійного програмування та Стандартна задача лінійного програмування, а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з коефіцієнтом +1 штучну змінну х8 якій відповідатиме одиничний вектор


Стандартна задача лінійного програмування


Тепер можемо розглянути розширену задачу лінійного програмування:


Стандартна задача лінійного програмування


На відміну від додаткових змінних штучна змінна Стандартна задача лінійного програмування має в цільовій функції Z коефіцієнт +М (для задачі на min) або -М (для задачі на max), де М— досить велике додатне число.

У розширеній задачі базисними змінними є x5, х6, х8, а решта змінних вільні. Початковий опорний план задачі:


Стандартна задача лінійного програмування


Складемо першу симплексну таблицю задачі:


Стандартна задача лінійного програмування

Розраховуючи оцінки першого опорного плану, дістаємо z0 = 0 - 9М, Z1 – С1 = -8, Z2 – С2 = -10, Z3 - С3 = 0 - М і т. д. Як бачимо, значення оцінок складаються з двох частин, одна з яких містить М, а інша — просто число. Тому для зручності розбиваємо оцінковий рядок на два. У перший оцінковий рядок записуємо просто число, а в другий — число з коефіцієнтом М.

Оцінки першого плану не задовольняють умову оптимальності, і тому він є неоптимальним. Згідно з алгоритмом, розглянутим у задачі 2.41, виконуємо перехід до наступного опорного плану задачі.

Подальше розв'язування задачі наведене у вигляді таблиці:


Стандартна задача лінійного програмування


Оптимальним планом задачі є вектор


Стандартна задача лінійного програмування


Отже, оптимальним є виробництво 57 одиниць продукції А, 100 одиниць продукції В і 9 одиниць продукції С. Тоді прибуток буде найбільшим і становитиме 1456 дол.

Висновок


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

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

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

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


Література


Цегелик Г.Г. Лінійне програмування. – Львів, 1995.

Акулич. Математичне програмування в прикладах і задачах. – Москва, 1986.

Математичне програмування. Навч.-метод. Посібник для самостійного вивчення дисципліни / В.В. Вітлінський, С.І. Наконечний, Т.О. Терещенко. М-во освіти і науки України. КНЕУ. – К.: КНЕУ, 2001.

Математичне програмування [Текст] навч. посібник для студ. вищ. закладів, І.Ю. Іванченко. – К.: ЦУЛ, 2007.

Математическое программирование и моделирование экономических процессов: Учеб. для студ. лесотехн. вузов. – Санкт-Петербург, гос. лесотехн. акад. СПб: Изд-во ДНК, 2003.

Математичне програмування. Навч. посібник для студентів напрямів «Економіка і підприємство», «Менеджмент» / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка та ін.; М-во освіти і науки України. Нац. Ун-т «Львів. політехніка». – Л.: Інтелект-Захід, 2004.

Математичне програмування: Навч. посібник / С.І. Наконечний, С.С. Савіна; М-во освіти і науки України. КНЕУ. – К.: КНЕУ, 2003.

Гасс С. Линейное программирование (методы и приложения). Пер. с англ. Гольштейна Е.П. и Сушкевича М.И. Под ред. Юдина Д.Б. – М.: Физат гиз, 1961.

Математичне програмування: Навч. посібник / В.М.Дякон, Л.Є.Ковальов; за заг. ред. В.М. Міхайленка. – К.: Вид-во Європ. ун-ту, 2007.

Мазаракі А.А., Толбатов Ю.А. Математичне програмування. Excel: Навч. посіб. для студ. екон. спеціал. вузів. – К.: Четверта хвиля, 1998.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: