Учись Учиться

Лабораторная работа
MS Word (информатика)
16 February 2012

Лабораторная работа Двухэтапный симплекс-метод

Star InactiveStar InactiveStar InactiveStar InactiveStar Inactive
 
    Tags:
  • Лабораторная работа
  • Двухэтапный симплекс-метод
  • Алгоритм двухэтапного
  • Привести задачу к стандартному виду
  • целевую функцию
  • каноническим
  • Ведущий элемент

Лабораторная работа Двухэтапный симплекс-метод 

Двухэтапный симплекс-метод применяется к задачам, заданным не в канонической форме.

 Алгоритм двухэтапного симплекс-метода

1 шаг. Привести задачу к стандартному виду. Если он является каноническим – решать одноэтапным симплекс-методом (иди к шагу 5)

2 шаг. Составить вспомогательную задачу (см. лекцию). Решить ее симплекс-методом.

3 шаг. Если вспомогательная задача не имеет решения или по окончании решения получены ненулевые (положительные) коэффициенты в целевой функции вспомогательной задачи, то исходная задача не имеет решения, иначе иди к 4 шагу.

4 шаг. Отбросить вспомогательную целевую функцию, выписать начальное допустимое базисное решение.

5 шаг. Решить полученную каноническую задачу одноэтапным симплекс-методом.

 Пример

Решить симплекс-методом

Найти

При ограничениях

 

Решение.

Задача записана не в стандартном виде. Приведем ее к стандартному виду. Изменим знаки в целевой функции и введем дополнительную переменную, чтобы избавиться от неравенства.

 

Это стандартный вид, не являющийся каноническим. Поэтому будем решать двухэтапным симплекс-методом.

Составим целевую функцию вспомогательной задачи

 

Построим симплекс-таблицу

    |  x1   x2   x3   x4  |своб

---------------------------------

    |  1    1    -3   1   |7

    |  1    3     1   0   |15

---------------------------------

 F  | -1    1     3   0   |0

 F1 | -2   -4     2   -1  |-22

 

Ведущий столбец – 2 (т.к. минимальный отрицательный -4)

Ведущая строка – 2 (т.к 15/3 меньше, чем 7/1)

Ведущий элемент равен 3.

Проведем шаг симплекс-метода. Получим таблицу

    |  x1   x2   x3   x4  |своб

---------------------------------

    | 2/3   0  -10/3  1   |2

 х2 | 1/3   1    1/3  0   |5

---------------------------------

 F  |-4/3   0    8/3  0   |-5

 F1 |-2/3   0   10/3 -1   |-2

Ведущий столбец – 4 (т.к. минимальный отрицательный -1)

Ведущая строка – 1

Ведущий элемент равен 1.

 

Проведем шаг симплекс-метода. Получим таблицу

    |  x1   x2   x3   x4  |своб

---------------------------------

 х4 | 2/3   0  -10/3  1   |2

 х2 | 1/3   1    1/3  0   |5

---------------------------------

 F  |-4/3   0    8/3  0   |-5

 F1 |  0    0    0    0   |0

 

В строке вспомогательной целевой функции получены нули, значит, приведение к каноническому виду завершено. Выпишем начальное допустимое базисное решение: Х = (0, 5, 0, 2), F=5

 

Отбросим вспомогательную целевую функцию, получим таблицу

    |  x1   x2   x3   x4  |своб

---------------------------------

 х4 | 2/3   0  -10/3  1   |2

 х2 | 1/3   1    1/3  0   |5

---------------------------------

 F  |-4/3   0    8/3  0   |-5

 

Продолжим решение одноэтапным симплекс-методом, получим ответ

 hmax = 7 при Х = (13, 0, 2)

 

Задание 1 (выполнить на занятии, показать преподавателю)

Решить задачу линейного программирования симплекс-методом


Задание 2 (индивидуальное)

Решить задачу 2 своего варианта лабораторной работы «Переборный метод»

 

Задание 3 (домашнее)

Написать программу, реализующую двухэтапный симплекс-метод. Задачу задавать в стандартном виде, чтение данных осуществлять из файла. Программа должна выдавать симплекс-таблицы и находить оптимальное решение задачи (минимум f и значения х), или выводить сообщения: «Область допустимых решений – пустое множество» или «Целевая функция не ограничена».

    Tags:
  • Лабораторная работа
  • Двухэтапный симплекс-метод
  • Алгоритм двухэтапного
  • Привести задачу к стандартному виду
  • целевую функцию
  • каноническим
  • Ведущий элемент
Rating:
( 0 Rating )
  • Дипломная работа
    • Дипломы по физике
    • по психологии
  • Курсовая работа
  • Реферат
  • доклад
  • Статьи
  • Педагогика
  • Конспект лекций
  • Аннотация
  • Лабораторная работа
  • контрольная
  • Иследования
  • конспект урока

Недавно добавили

Тест Айзенка (характер, эмоциональная устойчивость, тип личности) 08 May 2012
Развитие крупной моторики 09 February 2011
Методы компьютерной обработки визуальной информации УЗ-сканеров 25 January 2014
ЭКСПЕРИМЕНТ. ОБЩАЯ ХАРАКТЕРИСТИКА ПСИХОЛОГИЧЕСКОГО ЭКСПЕРИМЕНТА 13 February 2012
Проблема использования средств информационных технологий 12 January 2011
Круглый стол "Студенческие научные общества - проблемы и перспективы" 29 October 2011
Разработка, расчет и изготовление низковольтного регулируемого источника тока 12 January 2011
ВЛИЯНИЕ ФАКТОРОВ СРЕДЫ ОБИТАНИЯ НА СОСТОЯНИЕ ЗДОРОВЬЯ НАСЕЛЕНИЯ (на примере г. Орехово-Зуево) 29 October 2011
ШТУР - Школьный тест умственного развития 25 February 2012
ФОРМИРОВАНИЕ ЭКОЛОГИЧЕСКОЙ КУЛЬТУРЫ У МЛАДШИХ ШКОЛЬНИКОВ 04 March 2012

Самое читаемое

  • Методика «Счет по Крепелину»
  • Характеристика На ученика 8а класса
  • Психолого-педагогическая характеристика на ученика 7«В» класса
  • Корректурная проба
  • Психологическая диагностика и коррекция агрессивного поведения детей и подростков
  • Понятие и виды преступности несовершеннолетних.
  • Список литературы по менеджменту
  • Лекция 11. Научные методы исследования. Правила выбора методов в соответствии с темой и задачами. Виды методов для различных направлений исследования.
  • Лекция 3. Планирование научного исследования. Формулировка целей и задач.
  • Отчет по производственной практике

Последние новости

Создание и исследование компьютерного электрокардиографа 02 February 2014
Оценка загрязнения продуктов питания на примере кисло-молочной продукции региональных производителей 02 February 2014
Дистанционная ударноволновая литотрипсия 01 February 2014
Исследование возможностей использования шумомера 01 February 2014
Методы компьютерной обработки визуальной информации УЗ-сканеров 25 January 2014
Правовое регулирование медиации в России 19 January 2014
Психологическая диагностика и коррекция агрессивного поведения детей и подростков 19 January 2014
Итоговое игровое профориентационное занятие «Как устроиться на работу» 19 January 2014
Участие населения в правотворческом процессе муниципальных образований: реальность или фикция? 18 January 2014
Хрематонимы города Кирова: опыт комплексного анализа 18 January 2014

Сейчас читают

Равнодушие в школе 08 May 2011
Тема 1. Общие положения земельного права Вопрос 1. Земельное право: понятие, предмет, метод.Вопрос 2. Принципы земельного права 01 March 2011
Тема 6. Международная коммуникационная политика 1. Маркетинговые средства коммуникации 2. Коммуникативные стратегии 14 January 2011
СПС ГАРАНТ. Работа со списками. 27 May 2012
НЕКОТОРЫЕ ПОКАЗАТЕЛИ ИНДИВИДУАЛЬНОГО РАЗВИТИЯ ДЕТЕЙ ПРОМЫШЛЕННОГО ГОРОДА 29 October 2011
СОВРЕМЕННЫЕ ОСОБЕННОСТИ МОРФОФУНКЦИОНАЛЬНОГО СОСТОЯНИЯ СЕЛЬСКИХ И ГОРОДСКИХ ДЕТЕЙ МЛАДШЕГО ШКОЛЬНОГО ВОЗРАСТА 29 October 2011
Рождество в России и Великобритании 29 October 2011
Тема 5. Сетевые протоколы и модели. 14 January 2011
Список литературы по менеджменту 03 May 2011
современные методы и инструменты финансового менеджмента 14 January 2011
  • Дипломная работа
    • Дипломы по физике
    • по психологии
  • Курсовая работа
  • Реферат
  • доклад
  • Статьи
  • Педагогика
  • Конспект лекций
  • Аннотация
  • Лабораторная работа
  • контрольная
  • Иследования
  • конспект урока