28485

Алгоритм симплексного методу

Доклад

Математика и математический анализ

Заповнення початкової симплекстаблиці перша ітерація Таблиця 1 В рядках 1 3 записані відповідні рівняння системи 12 при цьому спочатку права частина в стовпці опорний план а потім коефіцієнти при відповідних змінних. Отже з початкової таблиці безпосередньо виписується початковий опорний план: Х1 оп = 0; 0; 182; 316; 238. В нульовому рядку міститься інформація про цільову функцію: для зручності функція 11 розглядається формалізовано як рівняння z 18х1 16х2 = О...

Украинкский

2013-08-20

23.31 KB

2 чел.

13. Алгоритм симплексного методу.

Сформулюємо алгоритм симплексного методу, використовуючи основну теорему про покращення опорного плану. При цьому компактність записів досягатиметься за рахунок роботи з так званими симплекc-таблицями по аналогії із формалізованою реалізацією методу Жордана-Гауса. Економістів цікавлять практичні рекомендації внаслідок проведеного аналізу. Тому в якості модельного прикладу візьмемо конкретну задачу про оптимальне використання сировини, числові дані якої наведені в таблиці.

Складемо математичну модель задачі:

Зведемо її до канонічної форми

де змінні  х3, х4, х5  —  кількість одиниць невикористаної сировини S1, S2,, S3 -  відповідно внаслідок випуску x 1 одиниць продукції П1, і  х 2одиниць продукції П2. 

Заповнення початкової симплекс-таблиці (перша ітерація)

Таблиця 1

              

В рядках 1—3 записані відповідні рівняння системи (12), при цьому спочатку права частина (в стовпці опорний план), а потім коефіцієнти при відповідних змінних. Така перестановка зумовлена зручністю виписування опорного плану безпосередньо із таблиці. В стовпці базисні невідомі (рядки 1—3) записані відповідні базисні змінні ху х4, ху тому решта змінних (х1, х2 ) — вільні. Отже, з початкової таблиці безпосередньо виписується початковий опорний план: Х(1) оп = (0; 0; 182; 316; 238). В нульовому рядку міститься інформація про цільову функцію: для зручності функція (11) розглядається формалізовано як рівняння z - 18х1 - 16х2 = О                                                                                                                                                             

Вмістиме клітинки "опорний план" в нульовому рядку — це значення, яке   набуває цільова функція на відповідному опорному плані. В даному випадку z(X(1))on) =18 ∙ 0+16 · 0 = 0. Надалі в наступних ітераціях необхідно слідкувати за цим значенням. Початковому опорному плану відповідає вершина многогранника допустимих розв'язків, а саме в одній з них цільова функція (11) набуває оптимального значення. Очевидно, що Х(1) оп не може бути оптимальним планом (проаналізуйте!). Цей якісний висновок узгоджується з таким твердженням, що є наслідком основної теореми. Критерій оптимальності опорного плану по симплекс-таблиці: Якщо цільова функція максимізується (мінімізується) і в нульовому рядку відсутні від'ємні (додатні) числа, за винятком стовпчика "опорний план", то опорний план є оптимальним. Аналогічні міркування приводяться і у випадку мінімізації цільової функції. Перш ніж покращувати опорний план, тобто переходити до іншого, на якому цільова функція    набере більшого (меншого) значення,  необхідно виключити випадок нерозв'язаності задачі (Z(max       = оо  ,Z min     = оо).  v   max '    mm .


 

А также другие работы, которые могут Вас заинтересовать

17781. ФІЗІОЛОГІЯ КРОВІ 756 KB
  фізіологія крові. 1. Загальна характеристика системи крові. Склад і функції крові. Поняття про гомеостаз. Кров циркулююча – знаходиться в стані активно...
17782. ФІЗІОЛОГІЯ КРОВООБІГУ 2.43 MB
  фізіологія кровообігу. 1. Загальна характеристика системи кровообігу. Фактори які забезпечують рух крові по судинах його спрямованість та безперервність. В залежності від потреби
17783. Фізіологія дихання, енергетичного обміну, терморегуляції 1.28 MB
  фізіологія дихання енергетичного обміну терморегуляції. Загальна характеристика системи дихання. Основні етапи дихання. Біомеханіка вдиху і видиху. Дихання – процес обміну газів О2 та СО2 між атмосферним повітрям та тканинами організму. ...
17784. Фізіологія виділення 124 KB
  Нирки являються основним органом системи виділення, так як тільки він виділяючи з організму в великій кількості продукти азотистого обміну, підтримують їх концентрацію в крові на певному рівні. Участь в цьому процесі шкіри, травного каналу та їх залоз недостатньо.
17785. Применение Excel для обработки данных 48 KB
  Лабораторная работа № 1 Применение Excel для обработки данных Зависимость представлена квадратической параболой .1 Самостоятельно сформировать тестовый пример задав коэффициенты для уравнения 1 в виде произвольных констант. Заполнить след...
17786. Координатна вісь, або одновимірний простір 2.03 MB
  ЛЕКЦІЯ 1 Координатна вісь або одновимірний простір Візьмемо пряму лінію і задамо на ній додатний напрям звичайно його показують стрілкою. Тоді протилежний напрям буде від'ємним. Напрямлена пряма називається віссю. Якщо на осі вибрати довільну точку обліку О і масшт...
17787. Визначник і мінори матриці 78.8 KB
  Визначник і мінори матриці Розглянемо квадратну матрицю А = Квадратній матриц і можна поставити у відповідність певне число яке називається детермінантом або визначником матриці. Детермінант матриці позначається так: det A= Детермінант так само як і матриці має ...
17788. Символы и строки в ANSI C 531.4 KB
  Целью данной лабораторной работы является изучение на практике строк языка ANSI C, операции над строками, функций стандартной библиотеки по работе со строками.
17789. Лінійний простір 5.92 MB
  Лекція 2. Лінійний простір Векторний простір називається лінійним якщо у ньому визначено операції над векторами – додавання і множення на число. Проте лінійний простір може бути утворений об’єктами будьякої природи. Нехай Е дана множина і x y z її елементи; К – мно