Навигация
Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування – задача для якої:
1. потрібно визначити максимальне значення ф-ції
2. всі обмеження записані в вигляді рівностей
3. для всіх змінних виконується умова невідємності
Якщо обмеження має вид нерівності зі знаком >=, то шляхом множення його на (-1) переходять до нерівності зі знаком <=.
Від обмежень нерівностей необхідно перейти до обмежень рівностей. Такий перехід виконується шляхом введення в ліву частину кожної нерівності додаткових незалежних невідємних змінних. При цьому знак нерівності міняють на знак рівності.
Вихідне завдання:
F = 5х1 +6х2 max
-10x1 - 6x2 ³-60
-4x1 + 9x2 £ 36
4x1 - 2x2 £ 8
x1,x2³0 x1,x2-цілі числа
Основна задача:
F = 5х1 +6х2 max
10x1 + 6x2 + х3 =60
-4x1 + 9x2 +х4= 36
4x1 - 2x2 +х5 = 8
x1,x2,x3,x4,x5 ³0 x1,x2-цілі числа
Кожній змінній в системі відповідає свій вектор – стовпець. Вектор – стовпець Ро складається із значень правих частин рівнянь і називається вектором вільних членів.
Виходячи з основного завдання, складаєм симплекс-таблицю.
| № рядка | Базис | Сб | Р0 | Р1 | Р2 | Р3 | Р4 | Р5 |
| 1 | Р3 | 0 | 60 | 10 |
| 1 | 0 | 0 |
| 2 | Р4 | 0 | 36 | -4 | 9 | 0 | 1 | 0 |
| 3 | Р5 | 0 | 8 | 4 | -2 | 0 | 0 | 1 |
| 4 | F | 0 | -5 | -6 | 0 | 0 | 0 |
6Таблиця № 1 – Вихідна симплекс-таблиця
 | |||
 | |||
Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи:
1. За вихідною с-т знаходять опорне рішення
Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змінних в основній задачі.
Кожній змінній в симплекс таблиці відповідає свій вектор. Змінній x1—вектор Р1 і т.д.
Вектор Р0 складений із вільних членів рівнянь. Кожний рядок симплекс-таблиці – рівняння відповідно. Четвертий рядок—рядок оцінок в ньому записують коефіцієнти при змінних в цільовій ф-ції з протилежним знаком і визначається розв’язуємий стовпець, беруться модулі від’ємних чисел з цієї строки. В векторі Х кожній змінній відповідає певна компонента. Змінній х1 перша компонента змінній х2—друга. Значення компонент визначають слідуючим чином, якщо вектор базисний, то компонента дорівнює значенню компоненти вектора стовпця Р0 з того рідка де в базисі стоїть 1.
У вихідній таблиці вектори Р1, Р2 – не базісні, тобто в Х – перша и друга компоненти = 0
Х=(0;0;60;36;8)
Похожие работы
... в данной курсовой работе. В данном курсовом проекте рассматриваются цель: определить минимальную стоимость комплекса производственных работ при заданной продолжительности его выполнения и других указанных условиях. 1. ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА Сетевой график - экономико-компьютерная модель, отражающая комплекс работ (операций) и событий, связанных с реализацией некоторого проекта ( ...
... замедлителя, хотя и имеют небольшие изменения по величине, однако, изменяют свой знак (- на +), что в соответствии с российскими нормами вообще для ВВЭР недопустимо (в критическом состоянии), и требуется введение выгорающего поглотителя в топливо. Третьи параметры заметно изменяют численные значения (например, температуры двуокиси в центре таблеток), и, хотя они остаются приемлемыми для ...
... . По строкам 070,080,090 организация проставила прочерки. Образец заполнения декларации представлен в Приложении 1. Глава III. Основные направления совершенствования развития оптимизации налогового бремени в РФ 3.1 Недостатки и преимущества применения упрощенной системы налогообложения ООО «Сфинкс» В условиях экономического кризиса важным инструментом стимулирования развития экономики и ...
... и опасных факторов на человека при высокой производительности труда, создать комфортные условия для работы людей. Темой данной дипломной работы является методика оптимизации структуры и параметров библиотечной автоматизированной системы обеспечения информационными услугами. Работа проводилась на территории НТУ «ХПИ» в корпусе «У2». Рабочее помещение расположено на пятом этаже семиэтажного здания. ...
0 комментариев