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

Лабораторная работа
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 )
  • Дипломная работа
    • Дипломы по физике
    • по психологии
  • Курсовая работа
  • Реферат
  • доклад
  • Статьи
  • Педагогика
  • Конспект лекций
  • Аннотация
  • Лабораторная работа
  • контрольная
  • Иследования
  • конспект урока

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

ВЛИЯНИЕ ЭКОЛОГИИ СОВРЕМЕННОГО МЕГАПОЛИСА НА РОСТОВЫЕ ПРОЦЕССЫ ДОШКОЛЬНИКОВ 29 October 2011
ШКАЛА СУБЪЕКТИВНОГО БЛАГОПОЛУЧИЯ (ШСБ) 26 February 2012
Оценка переключения внимания 02 February 2011
ИСТОРИЯ ПРИМИРИТЕЛЬНЫХ ПРОЦЕДУР В РОССИИ 25 March 2012
ПСИХОСЕМАНТИЧЕСКИЕ МЕТОДЫ 12 February 2012
Тема 5. Сетевые протоколы и модели. 14 January 2011
Принцип Дирихле 07 April 2012
Что такое музыка. Как и когда она появилась и почему не потеряла своих позиций в жизни человека? 26 March 2012
ГОСУДАРСТВЕННОЕ РЕГУЛИРОВАНИЕ ЭКОНОМИКИ 13 January 2011
Лекция 3. Планирование научного исследования. Формулировка целей и задач. 14 January 2011

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

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

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

Создание и исследование компьютерного электрокардиографа 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

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

Тема 15. Управление трудовыми ресурсами. 03 May 2011
Кредитно‑денежная система и рынок ценных бумаг в современных условиях 10 May 2012
МЕХАНИЗМ ФУНКЦИОНИРОВАНИЯ РЫНКА В УСЛОВИЯХ СОВЕРШЕННОЙ КОНКУРЕНЦИИ 10 May 2012
Шпаргалка по анатомии на тему "Ткань" "Мозг" 04 November 2013
Организация и средства информационных технологий обеспечения управленческой деятельности Информационная безопасность IT-службы предприятия 16 February 2012
Лекция 7. Изучение научного стиля письма 14 January 2011
Тема 8. Вопрос 2. Земли природоохранного назначения. Вопрос 3. Земли рекреационного назначения 02 March 2011
Лекция 4. Структура и содержание научно-исследовательской работы 29 October 2011
Игры в автобусе 11 January 2011
Выявление зависимости предрасположенностей людей к различным заболеваниям от химического состава плазмы крови разных групп 25 October 2013
  • Дипломная работа
    • Дипломы по физике
    • по психологии
  • Курсовая работа
  • Реферат
  • доклад
  • Статьи
  • Педагогика
  • Конспект лекций
  • Аннотация
  • Лабораторная работа
  • контрольная
  • Иследования
  • конспект урока