Лінійне програмування знайти оптимальне рішення. Розв'язання задач лінійного програмування графічним методом

Лінійне програмування

Лінійне програмування- математична дисципліна, присвячена теорії та методам вирішення екстремальних завдань на множинах -мірного векторного простору, що задаються системами лінійних рівняньта нерівностей.

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

Багато властивостей задач лінійного програмування можна інтерпретувати також як властивості багатогранників і таким чином геометрично формулювати та доводити їх.

Історія

Метод внутрішніх точок був уперше згаданий І. І. Дікіним у 1967 році.

Завдання

Основним (стандартним) завданням лінійного програмування називається завдання знаходження мінімуму лінійної цільової функції ( лінійної форми) виду :

за умов

, .

Завдання лінійного програмування матиме канонічний вигляд якщо в основному завданні замість першої системи нерівностей має місце система рівнянь:

Основне завдання можна звести до канонічного шляху запровадження додаткових змінних.

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

Легко помітити, що завдання знаходження максимуму можна замінити завданням знаходження мінімуму, взявши коефіцієнти зі зворотним знаком.

Приклади завдань

Максимальне паросполучення

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

Введемо змінні , які відповідають парі з того юнака і тієї дівчини і задовольняють обмеженням:

з цільовою функцією. Можна показати, що серед оптимальних рішень цього завдання знайдеться ціле. Змінні, рівні 1, будуть відповідати парам, які слід одружити.

Максимальний потік

Нехай є граф (з орієнтованими ребрами), в якому для кожного ребра вказано його пропускна здатність. І задані дві вершини: стік та виток. Потрібно вказати для кожного ребра, скільки через нього протікатиме рідини (не більше його пропускної здатності) так, щоб максимізувати сумарний потік з витоку в стік (рідина не може з'являтися або зникати у всіх вершинах, крім стоку та витоку).

Візьмемо в якості змінних - кількість рідини, що протікають через те ребро. Тоді

де - пропускна здатність-того ребра. Ці нерівності треба доповнити рівністю кількості рідини, що втікає і витікає, для кожної вершини, крім стоку і витоку. Як функцію природно взяти різницю між кількістю витікаючої і рідини, що витікає, у витоку.

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

Ці завдання можна вирішити швидше, ніж загальними алгоритмами розв'язання задач лінійного програмування, рахунок особливої структури рівнянь і нерівностей.

Транспортне завдання

Є якийсь однорідний вантаж, який необхідно перевести зі складів на заводів. Для кожного складу відомо, скільки в ньому знаходиться вантажу, а для кожного заводу відома його потреба у вантажі. Вартість перевезення пропорційна відстані від складу до заводу (всі відстані від складу до заводу відомі). Потрібно скласти найбільш дешевий планперевезення.

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

Цільова функція має вигляд: , яку треба мінімізувати.

Гра з нульовою сумою

Є матриця розміру. Перший гравець вибирає число від 1 до, другий - від 1 до. Потім вони звіряють числа і перший гравець отримує очок, а другий - (число, обране першим гравцем, - другим). Потрібно знайти оптимальну стратегію першого гравця.

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

, , (),

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

Алгоритми рішення

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

Перший поліноміальний алгоритм, метод еліпсоїдів, був запропонований у 1979 році радянським математиком Л. Хачіяном, вирішивши таким чином проблему, довгий часневирішеною. Спосіб еліпсоїдів має зовсім іншу, некомбінаторну, природу, ніж симплекс-метод. Однак у обчислювальному плані цей метод виявився неперспективним. Проте сам факт поліноміальної складності завдань призвів до створення цілого класу ефективних алгоритмівЛП - методів внутрішньої точкиПершим з яких був алгоритм Н. Кармаркара, запропонований у 1984 році. Алгоритми цього типу використовують безперервне трактування задачі ЛП, коли замість перебору вершин багатогранника розв'язання задачі ЛП здійснюється пошук вздовж траєкторій у просторі змінних завдання, що не проходять через вершини багатогранника. Метод внутрішніх точок, який, на відміну від симплекс-метода, обходить точки із внутрішньої частини області допустимих значень, використовує методи логарифмічних бар'єрних функцій нелінійного програмування, розроблені у 1960-х роках Фіако (Fiacco) та МакКорміком (McCormick).

Див. також

Графічний метод розв'язання задачі лінійного програмування

Примітки

Література

Томас Х. Кормен та ін.Глава 29. Лінійне програмування // Алгоритми: побудова та аналіз = INTRODUCTION TO ALGORITHMS. - 2-ге вид. – М.: «Вільямс», 2006. – С. 1296. – ISBN 5-8459-0857-4
Акуліч І.Л.Глава 1. Завдання лінійного програмування, Глава 2. Спеціальні завдання лінійного програмування // Математичне програмування прикладах і задачах. – М.: Вища школа, 1986. – 319 с. - ISBN 5-06-002663-9
Карманов В. Г.Математичне програмування. - 3-тє видання. – М.: Наука, 1986. – 288 с.
Данциг Джордж Бернард «Спогади про початок лінійного програмування»

Посилання

- Безкоштовний оптимізаційний пакет, призначений для вирішення задач лінійного, цілісного та цільового програмування.
Вершик А. М. «О Л. В. Канторовичу та лінійному програмуванні»
Большакова І. У., Кураленко М. У. «Лінійне програмування. Навчально-методичний посібник до контрольної роботи».
Барсов А. С. «Що таке лінійне програмування», Популярні лекції з математики, Гостехіздат, 1959.
М. Н. МлявийЛінійні нерівності та комбінаторика. - МЦНМО, 2003.

Wikimedia Foundation.

2010 .
Зальтен, Фелікс

Глагов, Мартіна

Дивитись що таке "Лінійне програмування" в інших словниках:лінійне програмування - — лінійне програмування Область математичного програмування, присвячена теорії та методам вирішення екстремальних завдань, що характеризуютьсялінійною залежністю між… …

Лінійне програмування

Лінійне програмуванняДовідник технічного перекладача - сфера математичного програмування, присвячена теорії та методам вирішення екстремальних завдань, що характеризуються лінійною залежністю між змінними. В самомузагальному вигляді Завдання Л.п. можна записати так. Дані… …

Економіко-математичний словник Лінійне програмування є одним з найбільшзначних розділів математики, де здійснюється вивчення теоретичних та методичних засад вирішення певних завдань. Ця математична дисципліна широко використовується вОстанніми роками у різноманітних економічних та технічних галузях, де не остання роль відведена математичному плануванню та використаннюавтоматичних систем обчислення. Цей розділ науки присвячено вивченню лінійних оптимізаційних моделей. Тобто лінійне програмування присвячене числам. Впершеданий термін був запропонований Т. Купмансом у 1951 році. Оптимальний план кожноїлінійної програми необхідно автоматично пов'язувати зоптимальним рівнем

цін, тобто з об'єктивно обумовленими оцінками.

Лінійне програмування: методи За допомогою методики вдається вирішити чималу кількість екстремальних завдань, що пов'язані з економікою. У цьому випадку зазвичай потрібно знайти крайні значення деяких функцій змінної величини. Як основу лінійного програмування виражено рішення системи перетворюваних на рівняння та нерівності.Цей вид програмування характеризується математичним формулюваннямзмінних величин , послідовністю та певним порядком розрахунків, а такожлогічним аналізом

Якщо є математична визначеність і кількісна обмеженість між факторами, що вивчаються, і змінними величинами;

Якщо є взаємозамінність факторів завдяки послідовності розрахунків;

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

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

У сільське господарство з допомогою цього методу визначається мінімальна вартість раціону годівлі з урахуванням наявної кількості корма. При цьому враховуються види та вміст у них певних корисних речовин.

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

Лінійне програмування: завдання

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

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

Лінійне програмування в Excel

У процесі вирішення таких завдань для початку необхідно скласти модель, що передбачає формулювання умов на математичною мовою. Після цього етапу можна знайти рішення у вигляді графічного методу. Для цього в програмі Excelіснує спеціальна функція"Пошук рішення".

Як відомо з вищесказаного, лінійне програмування має дуже велику сферу застосування.

Лінійне програмування

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

Історія

Метод внутрішніх точок був уперше згаданий І. І. Дікіним у 1967 році.

Завдання

за умов

, .

Основне завдання можна звести до канонічного шляху запровадження додаткових змінних.

Приклади завдань

Максимальне паросполучення

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

Введемо змінні , які відповідають парі з того юнака і тієї дівчини і задовольняють обмеженням:

Максимальний потік

Нехай є граф (з орієнтованими ребрами), у якому кожному ребра зазначено його пропускну здатність. І задані дві вершини: стік та виток. Потрібно вказати для кожного ребра, скільки через нього протікатиме рідини (не більше його пропускної здатності) так, щоб максимізувати сумарний потік з витоку в стік (рідина не може з'являтися або зникати у всіх вершинах, крім стоку та витоку).

Візьмемо в якості змінних - кількість рідини, що протікають через те ребро. Тоді

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

Транспортне завдання

Є певний однорідний вантаж, який необхідно перевести зі складів на заводів. Для кожного складу відомо, скільки в ньому знаходиться вантажу, а для кожного заводу відома його потреба у вантажі. Вартість перевезення пропорційна відстані від складу до заводу (всі відстані від -го складу до -го заводу відомі). Потрібно скласти найдешевший план перевезення.

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

Цільова функція має вигляд: , яку треба мінімізувати.

Гра з нульовою сумою

, , (),

Алгоритми рішення

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

Перший поліноміальний алгоритм, метод еліпсоїдів, був запропонований в 1979 році радянським математиком Л. Хачіяном, вирішивши таким чином проблему, що тривалий час залишалася невирішеною. Спосіб еліпсоїдів має зовсім іншу, некомбінаторну, природу, ніж симплекс-метод. Однак у обчислювальному плані цей метод виявився неперспективним. Проте сам факт поліноміальної складності завдань призвів до створення цілого класу ефективних алгоритмів ЛП. методів внутрішньої точкиПершим з яких був алгоритм Н. Кармаркара, запропонований у 1984 році. Алгоритми цього використовують безперервну трактування завдання ЛП, коли замість перебору вершин багатогранника розв'язання задачі ЛП здійснюється пошук вздовж траєкторій у просторі змінних завдання, які проходять через вершини багатогранника. Метод внутрішніх точок, який, на відміну від симплекс-метода, обходить точки із внутрішньої частини області допустимих значень, використовує методи логарифмічних бар'єрних функцій нелінійного програмування, розроблені у 1960-х роках Фіако (Fiacco) та Маккормік (McCormick).

Див. також

Графічний метод розв'язання задачі лінійного програмування

Примітки

Література

Томас Х. Кормен та ін.Глава 29. Лінійне програмування // Алгоритми: побудова та аналіз = INTRODUCTION TO ALGORITHMS. - 2-ге вид. – М.: «Вільямс», 2006. – С. 1296. – ISBN 5-8459-0857-4
Акуліч І.Л.Глава 1. Завдання лінійного програмування, Глава 2. Спеціальні завдання лінійного програмування // Математичне програмування прикладах і задачах. – М.: Вища школа, 1986. – 319 с. - ISBN 5-06-002663-9
Карманов В. Г.Математичне програмування. - 3-тє видання. – М.: Наука, 1986. – 288 с.
Данциг Джордж Бернард «Спогади про початок лінійного програмування»

Посилання

- Безкоштовний оптимізаційний пакет, призначений для вирішення задач лінійного, цілісного та цільового програмування.
Вершик А. М. «О Л. В. Канторовичу та лінійному програмуванні»
Большакова І. У., Кураленко М. У. «Лінійне програмування. Навчально-методичний посібник до контрольної роботи».
Барсов А. С. «Що таке лінійне програмування», Популярні лекції з математики, Гостехіздат, 1959.
М. Н. МлявийЛінійні нерівності та комбінаторика. - МЦНМО, 2003.

Wikimedia Foundation.

2010 .
Зальтен, Фелікс

Глагов, Мартіна

Дивитись що таке "Лінійне програмування" в інших словниках:- - Лінійне програмування Область математичного програмування, присвячена теорії та методам вирішення екстремальних завдань, що характеризуються лінійною залежністю між ... між… …

Лінійне програмування

Лінійне програмування- сфера математичного програмування, присвячена теорії та методам вирішення екстремальних завдань, що характеризуються лінійною залежністю між змінними. У найзагальнішому вигляді завдання Л.П. можна записати так. Дані… … Завдання Л.п. можна записати так. Дані… …

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

1. Поняття математичного програмування

- Це математична дисципліна, в якій розробляються методи відшукання екстремальних значень цільової функції серед багатьох її можливих значень, що визначаються обмеженнями.

Наявність обмежень робить завдання принципово відмінними від класичних завдань математичного аналізу пошуку екстремальних значень функції. Методи математичного аналізу для пошуку екстремуму функціїу завданнях математичного програмуваннявиявляються непридатними.

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

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

Залежно від властивостей цільової функції та функції обмежень усі завдання математичного програмуванняділяться на два основні класи:

задачі лінійного програмування,
завдання нелінійного програмування.

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

2. Поняття лінійного програмування. Види завдань лінійного програмування

Лінійне програмування(ЛП) – один із перших та найбільш докладно вивчених розділів математичного програмування. Саме лінійне програмуваннястало тим розділом, з якого і почала розвиватися сама дисципліна. математичне програмування". Термін "програмування" в назві дисципліни нічого спільного з терміном "програмування (тобто складання програми) для ЕОМ" не має, тому що дисципліна" лінійне програмування"виникла ще до того часу, коли ЕОМ стали широко застосовуватися для вирішення математичних, інженерних, економічних та ін задач.

Термін " лінійне програмування"виник у результаті неточного перекладу англійської "linear programming". Одне зі значень слова "programming" - складання планів, планування. правильним перекладоманглійської "linear programming" було б не лінійне програмування", а "лінійне планування", що більш точно відображає зміст дисципліни. Однак, терміни лінійне програмування, нелінійне програмування, математичне програмуванняі т.д. у нашій літературі стали загальноприйнятими і тому буде збережено.

Отже, лінійне програмуваннявиникло після Другої світової війни і стало швидко розвиватися, привертаючи увагу математиків, економістів та інженерів завдяки можливості широкого практичного застосування, а також математичної стрункості.

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

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

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

Загальна формазавдання має вигляд: знайти за умов

Поряд із загальною формою широко використовуються також канонічнаі стандартнаформи. Як у канонічній, так і у стандартній формі

Тобто. всі змінні в будь-якому допустимому розв'язанні задачі повинні набувати невід'ємних значень (такі змінні прийнято називати невід'ємніна відміну від так званих вільнихзмінних, область значень яких подібне обмеження не накладається). Відмінність між цими формами у тому, що у одному випадку I 2 = 0 , а іншому - I 1 = 0 .

Завдання ЛП у канонічній формі.

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

Основний зміст симплексного методу полягає в наступному:

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

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

Для того, щоб вирішити задачу симплексним методомнеобхідно виконати таке:

Привести завдання до канонічного вигляду
Знайти початкове опорне рішення з " одиничним базисом " (якщо опорне рішення відсутня, то завдання немає рішення через несумісності системи обмежень)
Обчислити оцінки розкладів векторів за базисом опорного рішення та заповнити таблицю симплексного методу
Якщо виконується ознака єдиності оптимального розв'язання, то розв'язання задачі закінчується
Якщо виконується умова існування безлічі оптимальних рішень, то шляхом простого перебору знаходять усі оптимальні рішення

Приклад розв'язання задачі симплексним методом

Приклад 26.1

Розв'язати симплексним методом завдання:

Рішення:

Наводимо завдання до канонічного вигляду.

Для цього в ліву частинупершого обмеження-нерівності вводимо додаткову змінну x 6 з коефіцієнтом +1. У цільову функцію змінна x 6 входить із коефіцієнтом нуль (тобто. не входить).

Отримуємо:

Знаходимо початкове опорне рішення. Для цього вільні (невирішені) змінні прирівнюємо до нуля х1 = х2 = х3 = 0.

Отримуємо опорне рішенняХ1 = (0,0,0,24,30,6) з одиничним базисом Б1 = (А4, А5, А6).

Обчислюємо оцінки розкладів векторівумов за базисом опорного рішення за формулою:

Δ k = C б X k - c k

C б = (з 1, з 2, ..., з m) - вектор коефіцієнтів цільової функції при базисних змінних
X k = (x 1k , x 2k , ... , x mk) — вектор розкладання відповідного вектора А до базису опорного рішення
С к - коефіцієнт цільової функції при змінній х до.

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

Зверху над таблицею зручності обчислень оцінок записуються коефіцієнти цільової функції. У першому стовпці "Б" записуються вектори, що входять до бази опорного рішення. Порядок запису цих векторів відповідає номерам дозволених невідомих рівнянь обмеження. У другому стовпці таблиці " З б " записуються коефіцієнти цільової функції при базисних змінних у тому порядку. При правильному розташуваннікоефіцієнтів цільової функції в стовпці "З б" оцінки одиничних векторів, що входять до базису, завжди рівних нулю.

У останньому рядкутаблиці з оцінками k в стовпці "А 0 " записуються значення цільової функції на опорному рішенні Z(X 1).

Початкове опорне рішення не є оптимальним, оскільки в задачі на максимум оцінки 1 = -2, 3 = -9 для векторів А 1 і А 3 негативні.

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

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

Приріст цільової функції знаходиться за формулою: .

Обчислюємо значення параметра 01 для першого і третього стовпців за формулою:

Отримуємо θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблиця 26.1).

Знаходимо збільшення цільової функції при введенні в базис першого вектора Z 1 = - 6 * (-2) = 12, і третього вектора Z 3 = - 3 * (- 9) = 27.

Отже, для більш швидкого наближення до оптимального рішення необхідно ввести базис опорного рішення вектор А3 замість першого вектора базису А6, оскільки мінімум параметра θ 03 досягається в першому рядку (l = 1).

Проводимо перетворення Жордана з елементом Х13 = 2, отримуємо друге опорне рішення Х2 = (0,0,3,21,42,0) з базисом Б2 = (А3, А4, А5). (Таблиця 26.2)

Це рішення не є оптимальним, тому що вектор А2 має негативну оцінку Δ2 = - 6. Для покращення рішення необхідно ввести вектор А2 в базис опорного рішення.

Визначаємо номер вектора, який виводиться з базису. Для цього обчислюємо параметр 02 для другого стовпця, він дорівнює 7 при l = 2. Отже, з базису виводимо другий вектор базису А4. Здійснюємо перетворення Жордана з елементом х 22 = 3, отримуємо третє опорне рішення Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблиця 26.3).

Це рішення є єдиним оптимальним, так як для всіх векторів, що не входять до базис оцінки позитивні

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Відповідь: max Z(X) = 201 при Х = (0,7,10,0,63).

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

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

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

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

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

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

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

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

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

Нелінійне програмування спирається на нелінійний характер цільової функції чи обмежень, або й того й іншого. Форми цільової функції та нерівностей обмежень у цих умовах можуть бути різними.

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

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

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