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

При этом методе на каждом шаге построения опорного плана первой заполняется клетка оставшейся части таблицы, которая имеет наименьшее расстояние. Если такая клетка не единственная, то заполняется любая из них, но с большим запросом. линейный программирование стоимость

В данном случае заполнение таблицы начинаем с клетки с координатами 2IV, для которой мы имеем значение стоимости С 2IV=1. Ставим в эту клетку 30 и тем самым выполняем полностью заявки четвертого района, и исключаем из рассмотрения четвертый столбец. У АТС 4 все номера использованы, поэтому эту строку мы исключаем из дальнейшего рассмотрения. Отыскиваем наименьшее расстояние в таблице, заполняем соответствующую клетку (1I,25 номеров) и исключаем из рассмотрения первую строку, т. к. на АТС 1 свободных номер больше нет. У первого района осталось не удовлетворенными 5 заявок. Отыскиваем в первом столбце наименьшее из оставшихся расстояний (клетка 4I). В первом районе все заявки выполнены, исключаем первый столбец из рассмотрения. Отыскиваем наименьшее расстояние в оставшихся клетках таблицы, заполняем соответствующую клетку (3II,25 номеров). У второго района все заявки удовлетворены, исключаем второй столбец из рассмотрения. У АТС 3 осталось еще 15 свободных номеров. Отыскиваем наименьшее расстояние в оставшихся клетках строки, заполняем соответствующую клетку (3II,15 номеров). Исключаем третью строку из рассмотрения. На АТС 4 осталось 50 свободных номеров. III району нужны еще 30 номеров, заполняем оставшуюся клетку 4III на 30 номеров и остальные 20 номеров записываем в клетке 4V. В пятом районе остались не удовлетворенными 15 заявок, которые мы присваиваем фиктивной строке в клетку 5V. Число базисных переменных должно быть 9, а у нас их 8. Поэтому в одну из клеток добавим 0 номеров, например, в 2II.

Таблица 3

Телефонные станции	Районы	Свободные номера
I	II	III	IV	V
1	1 25	2	6	3	2	25
2	6	2 0	2	1 30	3	30
3	2	1 25	2 15	1	3	40
4	2 5	5	6 30	4	6 20	55
5	0	0	0	0	0 15
Заявки	30	25	45	30	35

Стоимость плана:

S=1*25+2*0+1*30+1*25+2*15+2*5+6*30+6*20+0*15=420

Похожие статьи

• Принцип построения опорных планов, Метод северо-западного угла - Транспортная задача линейного проектирования

  Существует несколько способов построения опорного плана. Это метод северо-западного угла, метод наименьшей стоимости, приближенный метод Фогеля. Суть...

• Постановка задачи, Случаи вырождения и способы их преодоления - Транспортная задача линейного проектирования

  Цель работы. В городе имеется четыре АТС со свободной номерной емкостью (1,2,3,4). Известно количество свободных телефонных номеров на каждой станции....

• Исследование найденного опорного плана на оптимальность (2-й шаг метода) - Транспортная задача и ее решение методом потенциалов

  Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...

• Определение нового, улучшенного опорного решения транспортной задачи (3-й шаг метода) - Транспортная задача и ее решение методом потенциалов

  Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть...

• Методы отыскания исходного опорного плана перевозок транспортной задачи (первый шаг метода) - Транспортная задача и ее решение методом потенциалов

  Ранг системы ограничений T. З. равен (m + n - 1), следовательно, невырожденный опорный план Т-задачи содержит (m + n - 1) положительных компонент или...

• Пересчет симплекс-таблицы. - Транспортная задача

  Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 1,...

• Введение - Транспортная задача линейного проектирования

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

• Условия оптимальности плана перевозок транспортной задачи. - Транспортная задача и ее решение методом потенциалов

  Признак оптимальности плана перевозок T. З. устанавливает теорема. Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным,...

• Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование

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

• Геометрический метод, Двойственная задача - Линейное программирование

  Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...

• Транспортная задача и ее решение методом потенциалов, Постановка задачи и ее математическая модель - Транспортная задача и ее решение методом потенциалов

  Транспортная задача (Т. З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее...

• Транспортная задача - Линейное программирование

  Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...

• Методика решения задач ЛП графическим методом - Линейное программирование

  I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...

• Расчет диаметра сети - Проектирование учебной локальной вычислительной сети

  Методика определения диаметра сети может быть оформлена в виде таблицы. Номера строк и столбцов в ней соответствуют индиентификаторам рабочих станций на...

• Решение задач линейного программирования - Основы информатики

  Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...

• Условие задачи на выполнение курсовой работы, Выбор наиболее эффективного метода и решение задачи - Математические модели информационных процессов управления

  Вариант №1 1. Выбрать и обосновать наиболее эффективный метод решения задачи. 2. Разработать алгоритм и программу для решения задачи в общем виде. 3....

• Условие разрешимости транспортной задачи, Особенности ограничений транспортной задачи - Транспортная задача и ее решение методом потенциалов

  Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...

• Транспортная задача - Транспортная задача

  Сформулировать линейную производственную задачу и составить ее математическую модель, взяв исходные данные из приложения 1, где технологическая матрица А...

• Расчет числа исполнителей, Расчет сметной стоимости разработки проекта методом оценки трудоемкости на основании типовых этапов - Сеть абонентского доступа

  Среднее число исполнителей Чu, участвующих в разработке рассчитывается по формуле: Чu= , (10) Где Fд - полезный (действительный фонд времени одного...

• Проектирование приложений, Выбор среды программирования - Высокоуровневые методы информатики и программирования

  Выбор среды программирования Delphi - это попытка фирмы borland объединить лучшее, что было создано на тему визуального программирования, в единый...

• Проектирование модели данных - Создание аналога системной утилиты "Диспетчер задач"

  При проектировании модели данных разработаем диаграмму вариантов использования, диаграмму деятельности. Диаграмма вариантов использования представляет...

• Постановка задачи, Проектирование, Обоснование выбора среды разработки - Создание аналога системной утилиты "Диспетчер задач"

  Разработать и создать аналог системной утилиты "Диспетчер задач" по дисциплине "Системное программирование". "Диспетчер задач" должен содержать следующие...

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

  Задача поведенческой сегментации, формирование портретов клиентов по поведению Одними из основных задач анализа являлись: поведенческая сегментация...

• Общее представление задачи интеграции, Методы интеграции данных - Метод интеграции сторонних систем анализа и обработки данных в существующую ИС-архитектуру компании

  Для того, чтобы разработать оптимальный метод интеграции сторонних систем в существующую ИТ-инфраструктуру систем компании, требуется точно поставить...

• Метод представления знаний при проектировании модели - Искусственный интеллект

  Предлагаемая модель ИИ основывается на когнитивных картах - некотором базовом знании о мире. Ключевые идеи, положенные в основу этой концепции, сходны с...

• Необходимые алгоритмы реализации метода конечных элементов, Теоретические аспекты поставленной задачи - Реализация метода конечных элементов для расчета ферменных конструкций под ОС Android

  Теоретические аспекты поставленной задачи В этой части проекта будут объяснены этапы применения МКЭ для плоской фермы. В первой главе было рассмотрено...

• Метод аннотированного суффиксного дерева - Сравнение моделей представления слов в задаче очистки текста от обесцененной лексики

  Шестой метод - построение суффиксных деревьев. Среди большого количества методов анализа текста метод аннотированного суффиксного дерева выделяется тем,...

• Расчет стоимости сырья и материалов - Разработка сайта для компании

  Прежде, чем приступить к вычислению себестоимости созданного программного обеспечения, необходимо определить время, затраченное на реализацию проекта,...

• Проектирование пользовательского интерфейса - Разработка мобильного приложения расчета и учета оплаты коммунальных услуг

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

• Линейные блоковые коды - Кодек каскадного кода Хэмминга

  Код называется групповым, если кодовые комбинации образуют некоторую подгруппу группы всех последовательностей длиной n Линейные коды задаются с помощью...

• ОЦЕНКА ЭФФЕКТИВНОСТИ ВНЕДРЕНИЯ ЗАДАЧИ - Проектирование и разработка веб-представительства фирмы по продаже спортивных товаров и футбольной атрибутики

  Расчет экономической эффективности внедрения информационной системы произведем на основе метода "потоков платежей" ("Cash Flow") с использованием...

• Проектирование задачи, Требования к приложению - Разработка программного приложения "Калькулятор коммунальных услуг"

  Требования к приложению Результатом дипломного проекта "Калькулятор коммунальных услуг" должно служить достижение и решение поставленных задач: -...

• Введение, Объектно-ориентированный анализ и проектирование системы, Организационная сущность задачи - Разработка программного приложения "Калькулятор коммунальных услуг"

  Целью дипломного проекта "Калькулятор коммунальных услуг" является разработка программного средства "Calculation. exe". Для достижения цели дипломного...

• Принцип метода линейного предсказания - Вокодеры с линейным предсказанием

  Вокодер информация кодирование синтезатор В вокодерах с линейным предсказанием при анализе речевого сигнала в передающем устройстве определяются...

• Разработка программной поддержки деятельности службы доставки заказов, Постановка задач на проектирование - Концепция электронного здравоохранения

  Постановка задач на проектирование Мотивация: В настоящее время есть возможность улучшить эффективность управлением временем и коммуникацией между...

• Решение систем линейных уравнений, Метод исключений Гаусса - Составление программы для решения системы уравнений

  Дана система линейных уравнений (СЛУ) с n неизвестными: В матричной форме записи система (1) имеет вид: (2) Где : n - порядок системы; - матрица...

• Математические основы решения задачи линейного программирования графическим способом, Математический аппарат - Линейное программирование

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

• ЛАБОРАТОРНАЯ РАБОТА, "РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL", Цель работы, Порядок выполнения работы, Инструкция по использованию microsoft excel для решения задач лп - Решение задач линейного программирования с использованием Microsoft Excel

  "РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...

• Постановка задачи дипломного проектирования, Анализ предпроектной ситуации - Исследование и модернизация локальной вычислительной сети

  Методы разработки вычислительной сети: 1. Экспериментальный метод - персонал предприятия закупает "новинки" рынка компьютерной техники. Такой метод -...

• Постановка задачи динамической интерпретации метаинформации - Метод интеграции сторонних систем анализа и обработки данных в существующую ИС-архитектуру компании

  Построение модели предметной области с помощью описания структур данных и программного кода является классическим подходом в разработке ИС. Зачастую...

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

Предыдущая | Следующая